[자료구조]#3_이중 연결 리스트(Double Linked List)

 

[자료구조]#2_이중 연결 리스트(Double Linked List)

 

선형 자료 구조 중 "이중 연결 리스트"에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 이중 연결 리스트
2. 삽입, 제거 알고리즘

 

이중 연결 리스트

1. 개념

typedef struct Node[
    Data data;
    Node* prevLink;
    Node* nextLink;
} Node;

 

• 연결 리스트의 노드는 "데이터 필드" + "다음 노드를 가리키는 링크(포인터)"로 이루어져 있습니다.
• 이중 연결  리스트는 다음 노드뿐만 아니라, 이전 노드를 가리키는 링크 또한 가집니다.
• 보통의 연결 리스트가 갖는 "단방향 탐색"에 대한 단점을 보완하기 위함입니다.

 

삽입, 제거 알고리즘

1. 삽입 알고리즘

1. 비어있는 연결리스트에 새로운 노드 삽입

#1 head = newNode;
#2 last = newNode;

2. 이중 연결 리스트의 왼쪽으로(Head 방향) 노드 삽입

#1 head->prev = newNode;
#2 newNode->Next = head;
#3 head = newNode;

3. 이중 연결 리스트의 오른쪽으로(Tail 방향) 노드 삽입

#1 tail->next = newNode;
#2 newNode->prev = tail;
#3 tail = newNode;

4. 이중 연결 리스트의 중간으로 노드 삽입 (A와 B노드 사이라고 가정)

#1 newNode->Next = A->Next;
#2 newNode->Prev = B->Next;
#3 A->Next = newNode;
#4 B->Prev = newNode;

 

Details

 

• 이중 연결 리스트의 삽입 알고리즘은 간단합니다.
• Head 혹은 Tail과 새롭게 삽입할 노드 간의 "이전 링크 or 다음 링크"의 교환 후, 새로운 노드를 Head 혹은 Tail이 가리키도록 합니다.
• 이중 연결 리스트의 중간에 새로운 노드를 삽입하는 과정도 어렵지 않게 이해할 수 있습니다.

 

2. 삭제 알고리즘

1. 리스트의 왼쪽 끝단의(Head 방향) 노드를 삭제하는 알고리즘

#1 tmpPtr = Head;
#2 Head = Head->Next;
#3 Head->Prev = nullptr;
#4 Delete *tmpPtr

2. 리스트의 오른쪽 끝단의 노드를(Tail 방향) 삭제하는 알고리즘

#1 tmpPtr = Tail;
#2 Tail = Tail->Prev;
#3 Tail->Next = nullptr;
#4 Delete *tmpPtr

3. 리스트의 중간 노드를 삭제하는 알고리즘 (A -- B -- C 로 가정)

#1 A->Next = B->Next;
#2 C->Prev = B->Prev;
#3 Delete B

 

Details

 

• 이중 연결리스트의 삭제 알고리즘도 원리는 비슷합니다.
• 양 쪽 끝단의 노드들은 삭제 할때, "Head" 혹은 "Tail"에게 링크를 전달하고 삭제합니다.
• 리스트의 중간 노드들은 "왼쪽" 혹은 "오른쪽" 노드에게 링크를 전달하고 삭제됩니다.