[자료구조] Double Linked List

📌 양방향 연결 리스트

양방향 연결

단일 연결리스트와 다르게 양방향으로 접근이 가능하다

각 노드들은 포인터로 이어져있는 관계

🔒 private에 구조와 변수 정의

• 노드 크기를 판단한 size변수
  

• data -> 실제 저장하는 데이터 값

• *previous -> 현재의 이전 노드를 참조하는 포인터

• *next -> 현재의 다음 노드를 참조하는 포인터

• 노드의 처음 부분을 가리키는 head 포인터
  

• 노드의 마지막 부분을 가리키는 tail포인터
  

#include <iostream>

using namespace std;

template <typename T>

class DoubleLinkedList
{
private:
	int size;

	struct Node
	{
		T data;
		Node* previous;
		Node* next;
	};

	Node* head;
	Node* tail;

---

🔒 public 생성자에 값 초기화

• head = nullptr은 노드가 하나도 없다는 것
  
  
• tail = nullptr은 노드가 하나도 없다는 것

public:
	DoubleLinkedList()
	{
		size = 0;
		head = nullptr;
		tail = nullptr;
	}

---

✅ PushFront( )함수 (앞에 데이터 넣기)

노드가 하나도 없을때

• 1. newnode생성 (새 노드)
     
• 2. head와 tail이 서로 동일한 곳 가리킴
     

노드가 여러개일때

• 1. 맨 앞 노드를 head 가 가리킴
     
• 2. head의 previous 포인터가 새로 생긴 newnode를 가리킴
     
• 3. newnode의 next가 head를 가리키게 함
     
• 4. head의 위치를 newnode로 바꿔주면 삽입 성공
     
• 5. size++로 증가

// 앞에 데이터 넣기
void PushFront(T data)
{
	Node* newnode = new Node;

	newnode->data = data;
	newnode->next = nullptr;
	newnode->previous = nullptr;

	// 노드가 하나도 없을때
	if (head == nullptr)
	{
		head = newnode;
		tail = newnode;

	}
	else
	{
		head->previous = newnode;
		newnode->next = head;
		head = newnode;
	}
	size++;
}

---

✅ PopFront( )함수 (앞에 데이터 빼기)

노드가 하나도 없을 때

• 1. 더 이상 뺄 노드가 없기 때문에 문구 출력

노드가 하나 있을 때

• 2. head 와 tail이 같은 곳을 가리킬때
     
• 3. head와 tail을 nullptr로 가리키게 하고 deleteNode가 가리키는 곳을 delete 해주기
     
     

노드가 여러개 있을 때

• 1. deleteNode의 다음 노드가 가리키는 노드의 이전노드를 nullptr로
     
• 2. head를 head의 next로 이동
     
• 3. deleteNode를 delete시켜주기
     
• 4. size-- 까지 해주면 성공적으로 삭제 완료
     

void PopFront()
{
	if (head == nullptr)
	{
		cout << "DoubleLinkedList is Empty" << endl;
	}
	else
	{
		Node* deleteNode = head;

		// 노드가 하나 있으면
		if (head == tail)
		{
			head = nullptr;
			tail = nullptr;
		}
		else
		{
			deleteNode->next->previous = nullptr;

			head = head->next;
		}
		delete deleteNode;
		size--;
	}

}

---

✅ PushBack( )함수 (뒤에 데이터 넣기)

노드가 하나도 없을때

• 1. PushFront( )함수와 동일함
     

• -> newnode 생성 후 데이터 넣어준 뒤 head와 tail을 같은 노드에 가리키게 함
  

노드가 여러개 일때

• 1. newnode를 생성 후 tail의 next를 newnode에 가리키게 함
     
• 2. newnode의 previous를 tail로 가리키게 함
     
• 3. tail의 위치를 옮겨주고 size++ 까지 하면 성공
     

void PushBack(T data)
{
	Node* newnode = new Node;

	newnode->data = data;
	newnode->next = nullptr;
	newnode->previous = nullptr;

	// 하나도 없을 때
	if (head == nullptr)
	{
		head = newnode;
		tail = newnode;
	}
	else
	{
		tail->next = newnode;
		newnode->previous = tail;
		tail = newnode;
	}
	size++;
}

---

✅ PopBack( )함수 (뒤에 데이터 빼기)

노드가 하나도 없을때

• PopFront( )함수와 동일하게 메세지 출력(tail & head == nullptr)

노드가 하나 있을때

• PopFront( )함수와 동일하게 deleteNode가 tail을 가리키게 한뒤 head와 tail은 nullptr로 가리키게 한 뒤 delete
  

노드가 여러개 있을 때

void PopBack()
{
	// 노드 하나도 없을때
	if (tail == nullptr)
	{
		cout << "Double Linked List is Empty" << endl;
	}
	else
	{
		Node* deleteNode = tail;

		// 노드 하나일때
		if (head == tail)
		{
			head = nullptr;
			tail = nullptr;
		}
		// 노드 여러개일때
		else
		{
			tail->previous->next = nullptr;
			tail = tail->previous;
		}
		delete deleteNode;
		size--;
	}
}

✅ 데이터를 확인하기 위한 Show( )함수

• 노드를 순회하면서 데이터를 출력하는 데 필요한 currentNode 포인터 사용
  
  
• currentNode가 nullptr이 될때까지 출력

void Show()
{
	Node* currentNode = head;
	while (currentNode != nullptr)
	{
		cout << currentNode->data << " ";
		currentNode = currentNode->next;
	}
}

✅ 노드의 크기 반환 & 소멸자

const int & Size()
{
	return size;
}

~DoubleLinkedList()
{
	while (head != nullptr)
	{
		PopFront();
	}
}

---

📌 메인함수

• 메인함수에서 함수들을 사용해보기

int main()
{
	DoubleLinkedList <int> doubleLinkedList;

	doubleLinkedList.PushFront(30);
	doubleLinkedList.PushFront(20);
	doubleLinkedList.PushFront(10);
	doubleLinkedList.PushBack(40);
	doubleLinkedList.PushBack(50);

	doubleLinkedList.PopBack();
	doubleLinkedList.PopFront();

	doubleLinkedList.Show();

	cout << endl << "size: " << doubleLinkedList.Size() << endl;
	return 0;
}

결과값:

---

양방향 연결 리스트 시간복잡도

삽입/삭제 -> O(1) 탐색 -> O(n) ( head와 tail을 알 경우 O(1) )

📌 양방향 연결 리스트 장/단점

양방향 연결 리스트 장점

• 단일 연결 리스트에서는 맨 마지막 노드를 탐색하려면 head부터 순차적으로 접근했지만, 양방향 연결 리스트는 양방향에서 접근이 가능하여 뒤에서부터도 접근이 가능함
  
  -> 맨 마지막 노드를 탐색해야 하는데 tail을 알고 있을 경우 시간복잡도 O(1)

• 이전 노드의 정보를 알고있기에 중간 노드 삭제가 효율적이다

양방향 연결 리스트 단점

• 각 노드마다 2개의 포인터를 가지고 있어서, 단일 연결 리스트보다 메모리 사용이 크다