선형 구조 자료 - 연결 리스트

 이번 시간에는 연결 리스트에 관하여 이야기 해보도록 하겠습니다.

 

 연결 리스트는 말 그대로 연결되어있는 리스트를 의미합니다. 각각의 정보값을 지닌 노드들끼리 연결되어 있는 모습을 하고 있습니다. "연결"되어 있다는 말처럼, 배열과는 달리 연결 리스트의 노드끼리의 물리적 거리는 떨어져 있을 수 있다는 특징이 있습니다. 그렇기 때문에 연결되어있는 노드끼리 삽입/삭제 또한 용이하다는 장점이 있습니다. 하지만, 리스트 또한 단점이 존재하는데 그 것은 "탐색이 느리다" 라는 것입니다. 물리적 거리가 떨어져서 존재하기 때문에 배열처럼 계산을 통해 원하는 원소의 위치값을 찾을 수 있는 것이 아니라 연결부를 따라서 원하는 위치까지 이동해야 한다는 번거로움이 존재하기 때문입니다. 

 

 우선 연결 리스트의 구조를 깊게 보기 전에 , 노드의 구조를 확인해보도록 하겠습니다.

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

	}

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

	}

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

 해당 코드는  C++를 이용하여 작성한 노드의 구조입니다. 노드의 특징으로는 데이터를 담고있는 _data와 각각 이전/다음 노드를 가르킬 수 있는 포인터 변수인 _prev/_next로 이루어져 있다는 점입니다. 연속되게 저장되어있는 배열과 다르게 노드끼리의 연결이 필요하기 때문에 이처럼 추가적인 변수가 필요하게 되었습니다.

 

template<typename T>
class List
{
public:
	List() :_size(0)
	{
		// [head] <-> ... <-> [tail]
		_head = new Node<T>();
		_tail = new Node<T>();

		_head->_next = _tail;
		_tail->_prev = _head;
	}

	~List()
	{
		while (_size > 0)
			pop_back();

		delete _head;
		delete _tail;
	}

	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;

		// 새로운 노드를 before와 prevNode사이에 생성
		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;

		delete node;

		_size--;

		return nextNode;
	}

	int size() const { return _size; }

public:
	using iterator = Iterator<T>;

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

	// it '앞'에 추가
	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;
};

 다음으로 바로 리스트의 구조로 넘어가도록 하겠습니다. 우선 변수부터 확인해보도록 하겠습니다. _head와 _tail은 단어의 뜻 그대로 리스트의 머리와 꼬리의 역할을 하는 부분입니다. 필수적인 요소는 아니지만 노드의 구조상 양쪽에 연결되어 있는 노드의 주소값을 지녀야 하는데, 비어있는 리스트의 경우에는 가르킬 수 있는 노드가 존재하지 않기 때문에 리스트 구조를 짜는데에 있어서 불편함이 생기게 됩니다. 이를 방지하기 위해서 비어있는 노드에서도 가르킬 수 있는 노드인 _head와 _tail을 만들어서 사용하게 되고, 리스트에서 제공하는 기능인 push_back, pop_back등 과 같은 기능을 구현할 때에도 유용하게 사용하게 됩니다. 

 

 리스트에서 노드를 추가하게 되면 노드의 양 방향이 가르키는 노드들을 지정(연결)해주는 방식으로 새로운 노드를 추가하고, 삭제의 경우에는 반대로 해당 노드가 연결되어있던 두 노드를 서로 연결시킴으로써 삭제를 하게 됩니다. 그렇기 때문에 연속된 자료구조인 배열에 비해서 삽입/삭제에서 더 좋은 성능을 기대할 수있습니다. 

 

 하지만, 이는 반은 맞고 반은 틀린 말이 됩니다. 왜냐하면 삽입/삭제에서 더 좋은 성능을 기대할 수 있는 경우는 삽입/삭제하고자 하는 위치를 알고 있는 경우에만 한정되기 때문입니다. 원하는 위치값을 찾기 위해서 노드를 여러번 타고가는 계산을 하게 된다면 그 것은 좋지 않은 성능을 발휘할 것이기 때문입니다.

 

List에서는 Iterator. 즉 반복자를 이용하여 리스트 노드들에 접근해 삽입, 삭제 등을 할 수 있게끔 지원해주고 있습니다. 이를 위해서는 Iterator또한 필요할 것입니다. 

 

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

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

Iterator를 이용하여 노드->next , 노드->prev 등에 계속해서 접근하여 노드의 위치를 찾고, 해당 위치에 있는 노드를 삭제하거나 해당 위치에 새로운 노드를 추가하는 등 여러 기능을 사용할 수 있게 됩니다. 

 

이렇게 연결 리스트에 대한 소개를 마치도록 하겠습니다. 포바~!