연결리스트

연결리스트

• 리스트에는 원소를 갖는 노드들이 속해져 있고, 서로 앞, 뒤로 있는 노드 끼리 연결되어져 있는 형태의 자료구조.
• 중간에 원소를 삽입/삭제하는 경우 삽입/삭제할 공간의 앞, 뒤 노드만 연결 상태를 변경해주면 되기 때문에 효율적이다.
• 단 임의 접근은 비효율적이기 때문에 사용하지 않는다.

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

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

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

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

	}

	// ++it
	Iterator& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	//it++
	Iterator operator++(int)
	{
		Iterator<T> temp = *this;
		_node = _node->_next;
		return temp;
	}
	// --it
	Iterator& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	//it--
	Iterator operator--(int)
	{
		Iterator<T> temp = *this;
		_node = _node->_prev;
		return temp;
	}

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

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

public:
	Node<T>* _node;
};

template<typename T>
class List
{
public:
	List() :_size(0)
	{
		_head = new Node<T>();
		_tail = new Node<T>();
		_head->_next = _tail;
		_tail->_prev = _head;
	}
	~List()
	{
		while (_size > 0)
			pop_back();
		delete _head;
		delete _tail;
	}

public:
	void push_back(const T& value)
	{
		AddNode(_tail, value);
	}
	void pop_back()
	{
		RemoveNode(_tail->_prev);
	}


private:
	Node<T>* AddNode(Node<T>* before, const T& value)
	{
		Node<T>* newNode = new Node<T>(value);
		Node<T>* prevNode = before->_prev;
		prevNode->_next = newNode;
		newNode->_prev = prevNode;

		newNode->_next = before;
		before->_prev = newNode;

		_size++;

		return newNode;
	}

	Node<T>* RemoveNode(Node<T>* node)
	{
		Node<T>* prevNode = node->_prev;
		Node<T>* nextNode = node->_next;
		prevNode->_next = nextNode;
		nextNode->_prev = prevNode;


		_size--;
		delete node;

		return nextNode;
	}

	int size() { return _size; }

public:
	using iterator = Iterator<T>;

	iterator begin() { return iterator(_head->_next); }
	iterator end() { return iterator(_tail); }
	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);
		return iterator(node);
	}

public:

	Node<T>*	_head;
	Node<T>*	_tail;
	int			_size;
};

• 노드에 대한 삽입/삭제가 이뤄질 경우 해당 노드의 앞, 뒤에 위치한 노드들의 연결 상태를 적절하게 변경 처리를 한다.