[자료구조] 연결리스트 - List

선수지식 (자료구조 overview)

https://microelectronics.tistory.com/85

[자료구조] 선형 자료구조와 비선형 자료구조

 

예제 코드

#include <iostream>
#include <list>

using namespace std;


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

 

결과

0
1
2
3
4
6
7
8

 

list class 내부의 iterator 클래스를 사용하여, 한번 탐색한 부분의 위치를 저장할 수 있고,

이를 이용하여 중간 삽입을 수행하였다.

또한 pop_back 을 이용하여 끝 부분의 삭제도  수행하였다.

 

구현

Node

후술할 자료구조에서 기본이 되는 class 로 , 여기에서는 양방향 연결리스트를 위해 _prev, _next 멤버 변수가 존재한다.

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

 

Iterator

이 클래스는 노드를 순차적으로 탐색하는 역할을 하며, 다양한 연산자 오버로딩을 통해 포인터처럼 사용할 수 있도록 하는 필수적인 클래스이다.

Iterator 는 그 자체로 Node 포인터 멤버 변수를 가진다. 따라서 탐색한 노드의 주소를 저장하여 활용할 수 있게 한다.

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

 

List

양방향 연결리스트를 구현한 클래스로,  생성자를 사용해 첫번째 요소와 맨 마지막 요소를 _head 멤버 변수, _tail 멤버변수로 초기화 한다. 그리고 이 둘을 prev 와 next 로 설정한다.

template<typename T>
class List
{
public:
	List() : _size(0)
	{
		// dummy node for easy management
		// [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);
	}

	int size() { return _size; }

private:
	// [head] <-> [1] <-> [prevNode] <-> [before] <-> [tail]
	// [head] <-> [1] <-> [prevNode] <-> [newNode] <-> [before] <-> [tail]
	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;
	}

	// [head] <-> [prevNode] <-> [node] <-> [nextNode] <-> [tail]
	// [head] <-> [prevNode] <-> [nextNode] <-> [tail]
	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: 
	using iterator = Iterator<T>;
	iterator begin() { return iterator(_head->_next); }
	iterator end() { return iterator(_tail); }

	// iterator 바로 앞에다가 추가하는 특징
	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>* _head;
	Node<T>* _tail;
	int _size;
};

 

이후 main 함수의 list 부분을 List 로 변경하면 결과는 동일하게 나온다.