[알고리즘] C++ forward_list::STL(단일연결리스트) & Hacker Rank Single Linkedlist

감자코딩입니다. 이번에 살펴볼 내용은 C++ STL중 하나인 forward_list 입니다. 

single linked list(단일 연결 리스트) 자료구조를 이용하여 만든 시퀀스 컨테이너이며, std:list기준으로 작성된 컨테이너다.

std::forward_list 특징

std:list는 양방향 std::forward_list 단방향 Flow
std::list보다 삽입/삭제 속도가 빠름
std::list 양방향인 std::list에 비해 메모리를 적게 사용

삽입과 삭제는 지정한 요소의 다음 요소만 가능
구현의 복잡성과 성능 문제 때문에 std::list에서 제공하는 insert와 erase를 제공하지 않음.

Single Linked List는 STL로 forward_list 로 구현되어있고, C+11 버전부터 지원을 하기 시작하였습니다.

 

일단, 관련 문제를 풀기전 forward_list 형식 이름과 멤버함수를 정리하고 들어가겠습니다.

형식 이름설명

allocator_type	정방향 목록 개체의 할당자 클래스를 나타내는 형식입니다.
const_iterator	정방향 목록에 대한 상수 반복기를 제공하는 형식입니다.
const_pointer	에 대 한 포인터를 제공 하는 형식에 const 정방향 목록의 요소입니다.
const_reference	정방향 목록의 요소에 대한 상수 참조를 제공하는 형식입니다.
difference_type	반복기가 가리키는 요소 사이의 범위에 있는 정방향 목록의 요소 수를 나타내는 데 사용할 수 있는 부호 있는 정수 형식입니다.
iterator	정방향 목록에 대한 반복기를 제공하는 형식입니다.
pointer	정방향 목록의 요소에 대한 포인터를 제공하는 형식입니다.
reference	정방향 목록의 요소에 대한 참조를 제공하는 형식입니다.
size_type	두 요소 사이의 부호가 없는 거리를 나타내는 형식입니다.
value_type	정방향 목록에 저장된 요소의 형식을 나타내는 형식입니다.

멤버 함수설명

assign	정방향 목록에서 요소를 삭제하고 대상 정방향 목록에서 요소의 새 집합을 복사합니다.
before_begin	정방향 목록에서 첫 번째 요소 앞의 위치에 주소를 지정하는 반복기를 반환합니다.
begin	정방향 목록에서 첫 번째 요소의 주소를 지정하는 반복기를 반환합니다.
cbefore_begin	정방향 목록에서 첫 번째 요소 앞의 위치에 주소를 지정하는 const 반복기를 반환합니다.
cbegin	정방향 목록에서 첫 번째 요소의 주소를 지정하는 const 반복기를 반환합니다.
cend	정방향 목록에서 마지막 요소 다음에 나오는 위치의 주소를 지정하는 const 반복기를 반환합니다.
clear	정방향 목록의 모든 요소를 지웁니다.
emplace_after	이동 후 지정된 위치 뒤에 새 요소를 생성합니다.
emplace_front	생성된 요소를 목록 시작 부분에 추가합니다.
empty	정방향 목록이 비어 있는지 테스트합니다.
end	정방향 목록에서 마지막 요소 다음에 나오는 위치의 주소를 지정하는 반복기를 반환합니다.
erase_after	정방향 목록의 지정된 위치 뒤에서 요소를 제거합니다.
front	정방향 목록의 첫 번째 요소에 대한 참조를 반환합니다.
get_allocator	정방향 목록을 생성하는 데 사용되는 할당자 개체의 복사본을 반환합니다.
insert_after	정방향 목록의 지정된 위치 뒤에 요소를 추가합니다.
max_size	정방향 목록의 최대 길이를 반환합니다.
merge	요소를 인수 목록에서 제거하고 대상 정방향 목록에 삽입한 다음 새로 조합된 요소 집합을 오름차순 또는 기타 지정된 순서로 정렬합니다.
pop_front	정방향 목록의 시작 부분에 있는 요소를 삭제합니다.
push_front	정방향 목록의 시작 부분에 요소를 추가합니다.
remove	정방향 목록에서 지정된 값과 일치하는 요소를 지웁니다.
remove_if	지정된 조건자를 충족하는 요소를 정방향 목록에서 지웁니다.
resize	정방향 목록의 새 크기를 지정합니다.
reverse	정방향 목록에 요소가 나타나는 순서를 반대로 바꿉니다.
sort	오름차순 또는 조건자를 통해 지정된 순서로 요소를 정렬합니다.
splice_after	노드 간의 연결을 다시 붙입니다.
swap	두 정방향 목록의 요소를 교환합니다.
unique	지정된 테스트를 통과하는 인접 요소를 제거합니다.

엄청나게 많은 멤버함수가 있지만, 실제로 구현되는 CRUD 과정에서는 멤버함수를 많이쓰진 않을것 같습니다.

그러면 바로 여기 관련된 문제를 풀어보도록 하겠습니다.

[Hacker Rank - Insert a node at a specific position in a linked list] 

---

This challenge is part of a tutorial track by MyCodeSchool and is accompanied by a video lesson.

You’re given the pointer to the head node of a linked list, an integer to add to the list and the position at which the integer must be inserted. Create a new node with the given integer, insert this node at the desired position and return the head node.

A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is empty.

As an example, if your list starts as  and you want to insert a node at position  with , your new list should be 

Function Description Complete the function insertNodeAtPosition in the editor below. It must return a reference to the head node of your finished list.

insertNodeAtPosition has the following parameters:

• head: a SinglyLinkedListNode pointer to the head of the list
• data: an integer value to insert as data in your new node
• position: an integer position to insert the new node, zero based indexing

Input Format

The first line contains an integer , the number of elements in the linked list. 
Each of the next  lines contains an integer SinglyLinkedListNode[i].data. 
The last line contains an integer .

Constraints

•  
• , where  is the  element of the linked list.
• .

Output Format

Return a reference to the list head. Locked code prints the list for you.

Sample Input

3 16 13 7 1 2

Sample Output

16 13 1 7

Explanation

The initial linked list is 16 13 7. We have to insert  at the position  which currently has  in it. The updated linked list will be 16 13 1 7

 

---

문제 요약

실제로는 C++로 구현을 하여야하나, STL 활용을 위하여 forward_list:: 를 사용하였습니다.

입력부분에는 총 리스트를 구성 할 노드의 data의 개수를 입력하고, 그 data를 입력을 받습니다.

data의 입력이 끝나면 list 노드에 원하는 값을 집어넣기위한 삽입연산을 진행합니다. 그리고 전체 리스트를 순회하면서 모든 데이터들을 출력하게 되는 문제입니다.

실제로 구현하였으면, 시간이 오래걸렸을텐데 STL 덕분에 빠르게 진행 할 수 있었습니다.

 

 

 

//
//  linked list.cpp
//  beakjoon_algorithm
//
//  Created by kgh on 02/07/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <forward_list>
using namespace std;

int main(void){
    
    forward_list <int> f_list;
    auto iter = f_list.before_begin();
    // 정방향 목록에서 첫 번째 요소 앞의 위치에 주소를 지정하는 이터레이터 반환합니다.
    int n;  // 리스트를 구성 할 노드의 개수
    cin >> n;
    
    int data;   // 리스트에 넣을 값
    int position;
    
    for(int i=0; i<n; i++){
        cin >> data;
        iter = f_list.insert_after(iter,data);
            // 이터레이터 현재위치에서 data값 삽입
            // 이터레이터의 position이 초기화되는 것이 아니다.
    }
    
    cin >> data;        // 삽입할 데이터 입력
    cin >> position;    // 삽입 위치 입력

    iter = f_list.begin(); // 리스트의 첫번째 이터레이터 위치 반환
    
    // 해당 포지션까지 이터레이터 위치 변경
    for(int i=0; i<position-1; i++){
        *iter++;
    }
    // 이터레이터 데이터 삽입
    iter = f_list.insert_after(iter,data);
    
    // 모든 리스트를 순회하면서 출력하기
    for(iter = f_list.begin(); iter != f_list.end(); iter++){
        cout << *iter <<
        "\n";
    }
    return 0;
}

3
1
2
3
4
2
1
2
4
3
Program ended with exit code: 0

이상 std:forward_list STL에 대한 정리와 hacker rank문제까지 풀어보도록 하였습니다.