[C++ STL 만들기] list 구현

이번에는 C++에서 제공하는 Standart Template Library의 <list>를 구현해보았다. list는 linked list(연결리스트)를 구현한 것이며 특징으로는 iterator를 제공하고 양방향 연결리스트라는 것이다. cplusplus.com에 검색하면 나오는 list의 모든 메소드들을 구현하지는 못하였고 많이 쓰이는 메소드 몇 가지만 구현하였다. 소스코드는 아래의 링크에서 확인할 수 있다.

https://github.com/Seo-sang/Cpp-_Standard_Template_Library/blob/master/mylist.cpp

GitHub - Seo-sang/Cpp-_Standard_Template_Library: make C++ STL myself

연결리스트는 컴퓨터 전공생이면 1학년부터 C언어에서 포인터를 배우며 누구나 구현해보았을 것이다. 양방향 연결리스트도 이전노드와 연결해주는 것만 포함하면 전혀 다를 것이 없이 쉽게 구현할 수 있다. 따라서 이 구현에서 새로웠던 점은 iterator구현이다. list의 iterator 구현을 위한 특징이 하나 있다. 아래는 mylist의 멤버 변수이다.

 

멤버변수

public:
    node* head; //시작 노드
    node* tail; //마지막 노드
    node* fin; //end 노드
    int num; //노드 수

head와 tail은 첫 번째 노드와 마지막 노드를 가리킨다. iterator에서는 end가 존재한다. end는 연결리스트의 노드가 아니며 마지막만을 나타내는 기능을 제공한다. 즉 데이터가 들어있지 않다. 따라서 list에 아무것도 들어있지 않았어도 end를 가리키는 fin노드는 존재하여 유지시켰다.

 

iterator

class myiterator {
        node* current;
    public:
        myiterator(node* node = 0) : current(node) {};

        myiterator& operator++() {
            current = current->next;
            return *this;
        }
        
        myiterator& operator--() {
            current = current->prev;
            return *this;
        }

        node* operator&() {
            return current;
        }

        T& operator*() {
            return current->data;
        }

        bool operator !=(const myiterator& cmp) {
            return (current != cmp.current);
        }

        bool operator ==(const myiterator& cmp) {
            return (current == cmp.current);
        }
    };

iterator는 vector를 구현했을 때와 비슷하다. 연산자는 ++, --, *, !=, ==를 구현하였고 &연산자는 iterator로부터 포인터 값을 얻기 위해 내가 따로 만들었다. 물론 사용자도 사용할 수 있다. ++와 --는 각각 다음 노드, 이전 노드로 이동하는 연산자이다. iterator를 이용한 연결리스트를 순회할 때 굉장히 유용하게 사용할 수 있다. * 연산자는 현재 노드의 데이터 값을 얻어오는 연산자이다. ==와 !=는 각각 두 iterator변수가 같은 노드를 가리키는지 다른 노드를 가리키는지를 판단하는 연산자이다.

 

methods

 

구현한 메소드를 나열해보면

size, empty, front, back, push_back, pop_back, push_front, pop_front, insert, erase, begin, end로 총 12가지이다. 메소드는 모두 cplusplus.com에서 list를 검색했을 때 나오는 메소드와 똑같이 동작한다. 아래에서 실제 실행 결과로 보여주겠다. 코드가 길어 소스코드는 위의 링크에서 확인할 수 있다.

 

실행결과

 

실행 코드

이 코드는 아래와 같이 동작한다.

    1. 1부터 10까지 push_back을 한 다음 출력

    2. 3번 pop_back()을 한 다음 출력

    3. 100부터 3번 push_front한 다음 출력

    4. 6번 pop_front한 다음 출력

 

실행 결과는 다음과 같이 올바르게 나오는 것을 알 수 있다. iterator를 이용하여 모든 노드의 데이터를 출력하는 것도 올바르게 동작하는 것을 확인할 수 있다.

실행 결과

이번에는 insert와 erase를 사용해보겠다.

실행 코드

이 코드는 다음과 같이 동작한다.

    1. 1부터 10까지 push_back하고 출력

    2. begin부터 2번 다음 노드로 이동 후 100 insert 하고 출력

    3. 그 다음 3번 다음 노드로 이동 후 erase하고 출력

 

결과는 다음과 같다.

실행 결과

실행 결과 begin부터 2번 이동한 3번 위치에서 insert를 수행할 경우 3번 위치에 100을 삽입하고 3부터는 뒤로 밀리는 것을 알 수 있다. 그 다음 3번 위치부터 3번 이동한 6번 노드에서 erase연산을 수행하여 6번 노드가 사라진 최종 결과가 정확히 나왔음을 확인할 수 있다.

 

이렇게 C++ STL의 list의 일부를 직접 구현해보았다. 연결리스트를 직접 구현할 경우 예상치 못한 널포인터로 segmentation fault가 발생하는 것을 자주 접할 수 있다. 글쓴이 역시 list를 구현하며 몇 번의 segmentation fault를 보았다. 하지만 포인터 관리만 잘해주면 오류를 쉽게 찾고 고칠 수 있기 때문에 이렇게 직접 구현해보며 실수를 깨달을 수 있었다.