9-5. STL - List 구현하기(실습)

1. 노드 구현하기

template<typename T>
class Node
{
public:
    Node() : _next(nullptr), _prev(nullptr), _data(T())
    {

    }

    Node(const T& value) : _next(nullptr), _prev(nullptr), _data(value)
    {

    }

public:
    Node*   _next; // 다음 노드의 주소를 담은 포인터, 노드 다음에는 노드가 있음(Node 형)
    Node*   _prev; // 이전 노드의 주소를 담은 포인터
    T       _data; // 각 노드의 값

};

 

2. 리스트 구현하기

template<typename T>
class List
{
public:
    List() : _size(0)
    {
        _header = new Node<T>();
        _header->_next = _header;
        _header->_prev = _header;
    }

    ~List()
    {
        while (_size > 0)
            pop_back();
        
        delete _header;
    }

public:
    Node<T>* _header;
    int _size;    
};

 

 

3. insert와 push_back 구현을 위한 AddNode 함수 구현하기

    // [1] <-> [prevnode 2] <-> [node value] <-> [before 3] <-> [4] <-> [header] <->
    Node<T>* AddNode(Node<T>* before, const T& value) // 이전(before)의 노드를 찾고 node를 추가
    {
        Node<T>* node = new Node<T>(value); // T 형, value 값을 가진 노드를 생성

        Node<T>* prevnode = before->_prev;
        prevnode->_next = node; // 이전 노드의 다음을 value 값의 노드를 가리키게 함
        node->_prev = prevnode; // value 값의 노드의 prev를 이전 노드를 가리키게 함

        node->_next = before; // value 값의 노드의 next를 이동 전 이전의 노드를 가리키게 함
        before->_prev = node; // 이동 전 이전의 노드의 prev는 node를 가리키게 함

        _size++;

        return node;
    }

2와 3 사이에 새로운 노드를 추가한다.

- prevnode : 리스트의 두 번째 요소, 2

- before : 리스트에서 세 번째 요소였던 것, 3

- node : 새롭게 리스트에서 세 번째 요소가 되는 것, value

- header : 더미 값을 가지고 있는 헤더

 

4. push_back 구현하기

    void push_back(const T& value)
    {
        AddNode(_header, value);
    }

헤더를 before로 넣어주면 헤더의 다음과 이전은 자기 자신을 가리키고 있기 때문에 적절히 잘 작동하게 된다.

[prevnode] <-> [node] <-> [header]의 구조가 완성되었다.

 

5. pop_back과 erase 구현을 위한 RemoveNode 구현하기

    // pop_back과 erase 구현
    // [1] <-> [2] <-> [node] <-> [4] <-> [header]
    // [1] <-> [2] <-> [4] <-> [header]

    Node<T>* RemoveNode(Node<T>* node)
    {
        Node<T>* prevnode = node->_prev;
        Node<T>* nextnode = node->_next;

        prevnode->_next = nextnode; // 노드가 사라졌으므로 다음노드와 이전노드가
        nextnode->_prev = prevnode; // 서로를 가리키게 만듬

        delete node;

        _size--;

        return nextnode;
    }

 

6. pop_back 노드 구현

    int size() {return _size};


    void pop_back(const T& value)
    {
        RemoveNode(_header->_prev);
    }

 

7. 반복자 구현

template<typename T>
class Iterator
{
public:

    Iterator() : _node(nullptr)
    {

    }

    Iterator(Node<T>* node) : _node(node)
    {

    }
    
public:
    Node<T>* _node; // 어떤 노드를 가리키고 있는지 저장
};

 

(1) 증가 연산자 오버로딩

    Iterator<T>& operator++ () // 전위형
    {
        _node = _node->_next;
        return *this;
    }

    Iterator<T> operator++(int) // 후위형
    {
        Iterator<T> temp = *this; // 자신을 복사하여 임시 저장
        _node = _node->_next;
        return temp;
    }

    Iterator<T>& operator-- () // 전위형
    {
        _node = _node->_prev;
        return *this;
    }

    Iterator<T> operator--(int) // 후위형
    {
        Iterator<T> temp = *this; // 자신을 복사하여 임시 저장
        _node = _node->_prev;
        return temp;
    }

 

(2) 포인터 연산자 오버로딩

    T& operator*()
    {
        return _node->_data;
    }

 

(3) 비교 연산자 오버로딩

    bool operator==(const Iterator& right)
    {
        return _node == right._node;
    }

    bool operator!=(const Iterator& right)
    {
        return _node != right._node;
    }

 

8. begin, end, insert, erase 구현하기

이 코드들은 List 클래스 내부에서 작업한다.

public:

    typedef Iterator<T> iterator;

    iterator begin() { return iterator(_header->_next);}
    iterator end() { return iterator(_header);}

    iterator insert() (iterator it, const T& value)
    {
        Node<T>* node = AddNode(it._node, value);
        return iterator(node);
    }

    iterator erase() {iterator it}
    {
        Node<T>* node = RemoveNode(it._node);
    }