DataStructure] C++ 이중연결리스트(Double Linked List)

C언어로만 작성했던 것들을 C++로 작성하면서 C++과 자료구조 공부를 동시에 하려고 한다.

지난번에는 C++로 간단한 삽입, 삭제, 출력 기능만 넣은 단일 연결 리스트를 구현했다.

이번에 올리는 글은 이중 연결 리스트(Double Linked List)로,

다음 노드에 대한 포인터만 가지고 있는 단일 연결 리스트와는 달리 이전 노드에 대한 포인터도 가지고 있어,

노드 간의 이동을 양방향으로 할 수 있게 구현하는 자료구조를 뜻한다.

 

 

 

#include <iostream>
using namespace std;
class Node
{
	friend class List;
private:
	Node* next;
	Node* prev;
	int value;
	Node(Node* n, Node* p, int v)
	{
		next = n;
		prev = p;
		value = v;
	}
	Node(int v)
	{
		next = nullptr;
		prev = nullptr;
		value = v;
	}
};
class  List
{
private:
	Node* head;
	Node* tail;
	int size;
	
public:
	List(int);
	void insertHead(int);
	void insertTail(int);
	void insert(int, int);
	void deleteHead();
	void print();
	~List();
};
List::List(int value)
{
	tail = head = new Node(value);
	size = 1;
}
void List::insertHead(int value)
{
	Node* newNode = new Node(value);
	if (head == nullptr)
	{
		tail = head;
	}
	else
	{
		newNode->next = head;
		head->prev = newNode;
	}
	head = newNode;
	size++;
}
void List::insertTail(int value)
{
	Node* newNode = new Node(value);
	if (tail == nullptr)
	{
		head = tail;
	}
	else
	{
		newNode->prev = tail;
		tail->next = newNode;
	}
	tail = newNode;
	size++;
}
void List::insert(int idx, int value)
{
	/* index : start 0 */
	if (idx < 0 || idx >= size)
	{
		cout << "인덱스 범위 초과" << endl;
		return;
	}
	else if (idx == 0)
	{
		insertHead(value);
	}
	else if (idx == size - 1)
	{
		insertTail(value);
	}
	else
	{
		Node* newNode = new Node(value);
		Node* cur = head;
		int i = 0;
		while (i < idx - 1)
		{
			cur = cur->next;
			i++;
		}
		newNode->prev = cur;
		newNode->next = cur->next;
		cur->next = newNode;
		cur->prev = newNode->prev;
	}
	size++;
}
void List::deleteHead()
{
	if (head != nullptr)
	{
		Node* remove = head;
		head = head->next;
		head->prev = nullptr;
		delete remove;
		size--;
	}
}
void List::print()
{
	Node* cur = head;
	while(cur != nullptr)
	{
		if (cur->next == nullptr)
		{
			cout << cur->value << endl;
		}
		else
		{
			cout << cur->value << " ↔ ";
		}
		cur = cur->next;
	}
}
List::~List()
{
	Node* cur = head;
	while (cur != nullptr)
	{
		deleteHead();
	}
}
int main(void)
{
	List* list = new List(1);
	for (int i = 3; i <= 6; i++)
	{
		list->insertHead(i);
	}
	list->print();
	list->deleteHead();
	for (int i = 10; i <= 13; i++) {
		list->insertTail(i);
	}
	list->print();
	list->insert(6, 77);
	list->insert(1, 88);
	list->print();
}