[자료구조] 이중 연결 리스트 (Doubly Linked List)

[자료구조] 이중 연결 리스트 (Doubly Linked List)

---

이중 연결 리스트는 단일 연결 리스트와는 다르게 Next뿐만 아니라 Previos도 연결되어있는 양방향 리스트이다.

이 연결 리스트의 장점은 양방향으로 연결이 되어있기 때문에 탐색에 유리하다는 점이다. 즉, 단일 연결리스트는 단방향 탐색이지만 이중 연결 리스트는 양방향 탐색이 가능하다는 것입니다. 하지만 그만큼 양방향을 위해 변수를 추가해서 구조가 복잡해지고 메모리를 더 차지한다는 단점을 가지고 있습니다.

소스코드 구현 (C++)

#include <iostream>
using namespace std;

struct Node
{
	Node(int data)
	{
		Data = data;
		Prev = Next = NULL;
	}

	void Destroy()
	{
		delete this;
	}
	Node* Prev;
	int Data;
	Node* Next;
};

class DoublyLinkedList
{
public:
	DoublyLinkedList()
	{
		Head = Tail = NULL;
		Size = 0;
	}
	//맨뒤에 삽입
	void Push_back(Node* node)
	{
		//Head가 비었을 경우
		if (Head == NULL)
		{
			Head = node;
			Tail = node;
			Size++;
		}
		//그 외
		else
		{
			Node* n = Head;
			while (n->Next != NULL)
			{
				n = n->Next;
			}
			n->Next = node;
			node->Prev = n;
			Tail = node;
			Size++;
		}
	}
	//원하는 노드 뒤에 삽입 (cur) -> (node) -> (cur->Next)
	void Insert(Node* cur, Node* node)
	{
		node->Next = cur->Next;
		node->Prev = cur;

		if (cur->Next != NULL)
		{
			cur->Next->Prev = node;
		}
		cur->Next = node;

		Size++;
	}
	//제거
	void Remove(Node* node)
	{
		if (node == Head)
		{
			Head = Head->Next;
			node->Destroy();
		}
		else
		{
			Node* n = Head;
			while (n != node)
			{
				n = n->Next;
			}
			if (n == Tail)
			{
				Tail = n->Prev;
				Tail->Next = NULL;
				node->Destroy();
			}
			else
			{
				n->Prev->Next = n->Next;
				n->Next->Prev = n->Prev;
				node->Destroy();
			}
		}
		Size--;
	}
	int Search(Node* node)
	{
		Node* n = Head;
		int count = 0;
		while (n->Next != NULL)
		{
			if (n == node)
			{
				return count;
			}
			count++;
			n = n->Next;
		}
		return -1;
	}
	int GetSize()
	{
		return Size;
	}
	void PrintAll()
	{
		if (Size == 0) std::cout << "List is empty!!" << std::endl;
		else
		{
			std::cout << "Head[" << Head->Data << "],Tail[" << Tail->Data << "], Size[" << GetSize() << "] [";
			Node* head = Head;
			while (head)
			{
				std::cout << head->Data;
				if (head->Next != NULL)
				{
					std::cout << " - ";
				}
				head = head->Next;
			}
			std::cout << "]" << std::endl;
		}
	}
public:
	Node* Head;
	Node* Tail;
	int Size;
};

int main()
{
	DoublyLinkedList DL;
	//Create Node
	Node* node0 = new Node(0);
	DL.Push_back(node0);
	Node* node1 = new Node(1);
	DL.Push_back(node1);
	Node* node2 = new Node(2);
	DL.Push_back(node2);
	Node* node3 = new Node(3);
	DL.Push_back(node3);
	Node* node4 = new Node(4);
	DL.Push_back(node4);
	Node* node5 = new Node(5);
	DL.Push_back(node5);
	Node* node6 = new Node(6);
	DL.Push_back(node6);

	DL.PrintAll();
   	return 0;
};

출력 결과

---

https://doanhan.tistory.com/52

[자료구조] 연결 리스트 (Linked List)

기존 단일 연결 리스트에서는 지우는 과정에서 지워지는 노드의 전 노드를 가져오는 과정이 역참조를 불러내어 경고가 발생하는 문제가 있었다. 이중 연결 리스트는 이런 문제가 해결이 되었다. 하지만 삽입과 삭제를 하는 과정에서 Prev와 Next를 연결해야하는 공정이 늘어서 조금 더 복잡한 느낌이 들었다.