list 구현

list 특징

• 데이터가 연속적이지 않다.

• 임의 접근이 빠르지않다.

• 연속적이지 않아서 처음 끝 삽입 삭제가 매우 빠르다.

• stl list의 remove가 지원되는 이유는 list의 특징이 삽입 삭제가 빨라서 그렇다..

list 구현 소스

#include <iostream>
#include <list>

using namespace std;

//list : 연결리스트
// [1]        ->              [2]  -> [3] ->[4]   <->  Myhead[end()]

//capacity가 필요없는 이유는 -> 현재 데이터에서 이어붙이면되기때문이다.
//remove 삽입 삭제가 빠르니..


/*
* 데이터가 연속적이지 않다.
* 임의 접근이 빠르지않다
* 
* 그러나 연속적이지 않아서 처음 끝 삽입 삭제가 매우빠르다.
*/

template<typename T>
class Node;


template<typename T>
class Iteraotr
{
public:
    Iteraotr() : _node(nullptr)
    {

    }
    Iteraotr(Node<T>* node) : _node(node)
    {

    }
    //++it
    Iteraotr<T>& operator++()
    {
        _node = _node->_next;
        return *this;
    }
    //it++
    Iteraotr<T> operator++(int)
    {
        Iteraotr<T> tmp = *this;
        _node = _node->_next;
        return tmp;
    }
    bool operator==(const Iteraotr& right)
    {
        return _node = right._node;
    }
    bool operator!=(const Iteraotr& right)
    {
        return _node != right._node;
    }
public:
    Node<T>* _node;
};

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

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

    }
public:

    Node* _next;
    Node* _prev;
    T _data;
};

// <-> [header] <-> 
//어떠한 값도 없으면 header 의 prev와 next값을 자기자신으로 해주자.
template<typename T>
class List
{
public:
    List() : _size(0)
    {
        _header = new Node<T>();
        _header->_prev = _header;
        _header->_next = _header;
    }
    ~List()
    {
        while (_size > 0)
            pop_back();

        delete _header;
    }
    //header이전에 값을 밀어 넣는 과정 
    void push_back(const T& value)
    {
        AddNode(_header, value);
    }
    // [1] <-> [2] <-> [before] <-> [4] <-> [header] <->
    // [1] <-> [2] <-> value <-> [before] <-> [4] <-> [header] <->

    //insert같은 경우 값을 대입하고 해당 위치를 반환한다.
    Node<T>* AddNode(Node<T>* before , const T& value)
    {
        Node<T>* node = new Node<T>(value);

        //[2]가 prevNode
        Node<T>* prevNode = before->_prev;
        prevNode->_next = node;
        node->_prev = prevNode;

        before->_prev = node;
        node->_next = before;

        _size++;
    }

    void pop_back()
    {
        RemoveNode(_header->_prev);
    }
    // [1] <-> [2] <-> [node] <-> [4] <-> [header] <->
    // [1] <-> [2] <-> [4] <-> [header] <->
    Node<T>* RemoveNode(Node<T>* node)
    {
        Node<T>* prev = node->_prev;
        Node<T>* next = node->_next;

        prev->_next = next;
        next->_prev = prev;

        delete node;

        _size--;
        //제거한 위치 다음 노드를 반환 
        return next;
    }

    int size() { return _size; }
public:
    typedef Iteraotr<T> iterator;

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


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

int main()
{
    /*
    * 임의접근은 느린데 어떻게 중간 삽입 삭제는 빠른가? 
    * 정답 :iterator를 들고 있으면 가능하다.
    */

    list<int> li;
    list<int>::iterator itRemember;
    for (int i = 0; i < 10; i++)
    {
        if (i == 5)
        {
            itRemember = li.insert(li.end(), i);
        }
        else
        {
            li.push_back(i);
        }
    }

    li.erase(itRemember);
    return 0;
}