list 구현해보기

▶ 목표

ㆍ push_back , pop_back

ㆍ 다양한 자료형을 받기 위해 템플릿으로 구현

ㆍ insert, erase 

ㆍ 연산자 오버로딩 활용해서 실제 list처럼 보이게

ㆍ 이터레이터 구현

 

#Node

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* _prev;
    Node* _next;
    T _data;
};

ㆍ STL에서 list는 양방향 리스트기 때문에 노드 클래스를 이렇게 작성.

 

 

#List

// 리스트는 헤더가 필요하다 [1] <-> [2] <-> [3] <-> [header] <-> [첫번째]
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;
    }

    void push_back(const T& value)  //insert도 구현해야되니 묶자
    {
        AddNode(_header, value);
    }

    //[1] <-> [2] <-> [3] <-> [header]
    //[1] <-> [2] <-> [header]
    void pop_back()                 // erase도 구현해야 되니 묶자
    {
        RemoveNode(_header->_prev);
    }

    //[1] <-> [2] <-> [before] <-> [4] <-> [header] <-> 
    //[1] <->[2] <->[3] <->[header] <->[첫번째]
    Node<T>* AddNode(Node<T>* before, const T& value)
    {
        Node<T>* node = new Node<T>(value); 

        Node<T>* prevNode = before->_prev;
        prevNode->_next = node;
        node->_prev = prevNode;
        //이전노드와 삽입값을 연결

        node->_next = before;
        before->_prev = node;
        //넣은 노드의 다음부분을 before로 지정, before의 이전노드를 신규값으로 지정

        _size++;

        return node;
    }

    //[1] <-> [2] <-> [3] <-> [node] <->  [4] < - >  [header]
    //[1] <-> [2] <-> [3] <->[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;
    }

    int size() { return _size; }

public:
    typedef Iterator<T> iterator;
    
    iterator begin() { return iterator(_header->_next); }
    iterator end() { return iterator(_header); }

    iterator insert(iterator it, const T& value)
    {
       return iterator(AddNode(it._node, value));
    }

    iterator erase(iterator it)
    {
        Node<T>* node = RemoveNode(it._node);
        return iterator(node);
    }
public:
    Node<T>* _header; //메모리 까봤을때 봤던 그 더미
    int _size;
};

ㆍ 자세한 설명은 주석으로 대체

 

# iterator

template<typename T>
class Iterator
{
public:

    Iterator() : _node(nullptr)
    {

    }

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

    }

    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;
    }

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

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

public:
    Node<T>* _node;
};

ㆍ 실제 이터레이터 처럼 쓰여 보이기 위해 연산자 오버로딩

 

 

#메인함수

int main()
{
    List<int> li;

    List<int>::iterator eraseIt;

    for (int i = 0; i < 10; i++)
    {
        if (i == 5)
        {
            eraseIt = li.insert(li.end(), i);
        }
        else
        {
            li.push_back(i);
        }
    }

    li.pop_back();
    li.erase(eraseIt);

    for (List<int>::iterator it = li.begin(); it != li.end(); ++it)
    {
        cout << *it << endl;
    }
}

ㆍ 실제 list처럼 기능이 잘 작동한다.!

 

※ 개인적으로 vector보다 만들기 좀 더 헷갈렸다..