List

연결 리스트 구현.

List는 C#을 이용하며 친숙한 이름 중 하나이다. 하나의 노드를 연결시켜 사용하는 List는 친숙하면서 다른 알고리즘에서 참고가 되는 녀석이다. 

 

삽입과 중간 삭제가 쉬운 반면 직접 접근이 어려워 노드를 찾는데 시간비용이 든다. 보통 중간 삽입하는 과정은 별로 없기 때문에 C++에서는 Vector를 많이 사용한다.

 

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

int main()
{
	list<int> _list;

	list<int>::iterator eraselt;

	for (int i = 0; i < 10; i++)
	{
		if(i ==5)
		eraselt = _list.insert(_list.end(), i);

		_list.push_back(i);
	}

	_list.pop_back();

	_list.erase(eraselt);

	for (list<int>::iterator it = _list.begin(); it != _list.end(); it++)
	{
		cout << (*it) << endl;
	}
}

C++를 List를 공부하며 처음보는 값이 있는데 list<int>::iterator 이다.

뜻은 반복자라는데, _list.insert()값을 위에서 저장하는 걸 봐선, list 함수의 특정 값의 메모리 주소를 저장하는 기능인 것 같다.

for문을 참고로 보면 iterator it 이 _list의 처음의 주소를 저장하고, 그게 _list의 마지막 주소와 같지 않을 때, it이 해당되는 _list의 다음 주소로 이동하여 값을 출력한다. 출력도 주소값이기에 *it을 출력하는 것을 볼 수 있다. 

 

list를 구현하는데 기본 구조가 되는 Node를 만든다.

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

Node에는 Node의 이전 위치를 기억하는 _prev와 다음 위치를 기억하는 _next, 그리고 저장될 _data로 이루어져 있다.

기본적으로 생성자는 모두 null을 가리키지만 만약 Node(const T& value)가 들어갈 시 _data를 생성한다.

 

이 Node를 기초로 하여 List가 만들어지는데 

 

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

	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;

		delete node;

		_size--;

		return nextNode;
	}
	int size() { return _size; }
    
    private:
	Node* _head;
	Node* _tail;
	int _size;


};

 

List는 Node의 연결한 목록이라고 생각하면 된다. List의 처음과 끝의 위치를 기억하는 _head와 _tail이 존재하며, List의 길이를 기억하는 _size가 기본 원소이다. 생성자, 소멸자에서 _head와 _tail를 이어 nullptr를 방지해준다.

AddNode에서 value를 받아 새로운 Node를 만들고, 전 노드를 새로운 Node에 붙여준다. 그리고 새로운 Node에 before를 붙여주는데 List는 기본적으로 마지막에 새로운 노드를 생성하지만 끝은 항상 _tail값이 존재하므로 before값은 항상 _tail로 존재한다.

 

이렇게 _tail값을 계속 존재 시켜야 Remove를 할 때, List의 마지막을 상관하지 않고 Remove(Node)값을 지운뒤 이어 붙일 수 있다.

 

 

그리고 오늘 처음본 iterator

template<typename T>
class Iterator
{
	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& other)
	{
		return _node = other._node;
	}

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

public:
	Node<T>* _node;
};

머 그렇단다. 역시나 생각한데로 node의 메모리 주소를 기억하는 역할을 하고 있다.

이를 토대로 List에 iterator를 추가해준다.

 

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

여기서 중요한 점은 iterator이 특정 Node의 메모리 주소값을 기억하고 있기 때문에 삽입 및 삭제는 특정 Node와 앞, 뒤 노드의 연산만 하므로 효율이 뛰어나다. 굳이 이야기하면 O(3)인가? 그 이하 쯤 되지 않을까?

 

하지만 iterator이 없는 상태, 즉 Node의 메모리 주소를 모르는 상태에서 삽입 및 삭제할 경우 O(n)의 시간 복잡도를 가지게 된다. 말장난이지만 말장난 좋아하는 면접관은 이런걸 물어본단다.