[STL] list

노드 방식으로 작동. 이중 연결 리스트로 구현되어있다.

vector와 다르게 임의 접근을 허용하지 않는다.

삭제 자체는 O(1)이지만 원소에 접근하는 시간은 O(N)이다. 탐색과 삭제는 분리해서 봐야한다.

 

연속된 공간이 아닌 노드 단위로 관리되기 때문에 삽입 및 삭제는 큰 오버헤드 없이 수행할 수 있지만 이전, 다음 노드의 정보들만 가지고 있으므로 임의 접근은 매우 느리기 때문에 공식적으로 지원하는 메소드는 없다.

 

begin은 맨 처음 값이라서 prev가 없어야 정상이겠지만 실제로는 end를 가리키는 더미 노드 주소값이 들어가있다.

[1] <-> [2] <-> .. [5] <-> [_Myhead : end()] <-> [1] <-> ... 이런 구성으로 되어있다.

하지만 연결이 되어있다고 해서 실제로 begin에서 prev로 접근하면 크래시가 발생한다. 잘못된 코드를 잡아주기 위해 연결한 것이지 실제로 접근해도 되는 것은 아니다.

 

iterator의 증감 연산자는 사용이 가능하지만 iterator + 1 같은 형식은 사용이 불가능하다.

 

custom list 간단하게 구현

#include <iostream>
#include <list>
using namespace std;

// list (연결 리스트)
// - list의 동작 원리
// - 중간 삽입/삭제
// - 처음/끝 삽입/삭제
// - 임의 접근

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

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

	}

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

	}

	Iterator& operator++()
	{
		_node = _node->_next;
		return *this;
	}

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

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

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)
	{
		AddNode(_header, value);
	}

	void pop_back()
	{
		RemoveNode(_header->_prev);
	}

	int size() const { return _size; }

private:
	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;
		
		_size++;

		return node;
	}

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

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);
		return iterator(node);
	}


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

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;

	return 0;
}