[C] Doubly Linked List 구현

Doubly Linked List는 단방향(Head -> Tail) 탐색만이 가능한 Singly Linked List의 탐색 기능을 개선한 자료구조입니다.

사진 출처 – GeeksforGeeks

Doubly Linked List의 연산은 ‘이전 노드’를 처리하기 위한 구현이 추가 될 뿐, Singly Linked List와 차이점이 전혀 없습니다. 아래 Singly Linked List 참조 바랍니다.


Doubly Linked List의 주요 연산

  • 노드 생성/소멸
  • 노드 추가
  • 노드 탐색
  • 노드 삭제
  • 노드 삽입

노드 구현

1
2
3
4
5
6
typedef struct Node
{
  int data;
  struct Node* nextNode;
  struct Node* prevNode;
} Node;
cs

Singly Linked List와 구별되는 점은 prevNode가 추가되었다는 점입니다.


노드 생성

1
2
3
4
5
6
7
8
9
Node* DLL_createNode(int data)
{
 Node* newNode = (Node*)malloc(sizeof(Node));
 newNode>data = data;
 newNode>nextNode = NULL;
 newNode>prevNode = NULL;
  return newNode;
}
cs

입력받은 데이터를 newNode->data에 입력해주고, nextNode와 prevNode 모두 NULL값을 할당합니다.


노드 소멸

1
2
3
4
void DDL_destroyNode(Node* node)
{
  free(node);
}
cs

free 함수는 <stdlib.h>를 include해주셔야 사용이 가능합니다.


노드 추가

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void DDL_appendNode(Node** head, Node* newNode)
{
  if(*head == NULL)
 {
  *head = newNode;
 }
  else
 {
 Node *tail = *head;
  while(tail>nextNode != NULL)
 tail = tail>nextNode;
 tail>nextNode = newNode;
 newNode>prevNode = tail;
 }
}
cs

Tail 뒤에 새로운 노드를 추가하는 연산으로 Singly와 대부분 유사하나 newNode->prevNode = tail; 부분만 추가되었습니다.


노드 탐색

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Node* DDL_getNodeAt(Node* head, int index)
{
 Node* current = head;
  while(current != NULL && index >= 0)
 {
 current = current>nextNode;
 }
  return current;
}
int main(int argc, const char * argv[])
{
 Node *list = NULL;
 Node *newNode = NULL;
 DDL_appendNode(&list, DLL_createNode(4));
 DDL_appendNode(&list, DLL_createNode(5));
 Node* searchedNode = DDL_getNodeAt(list, 1);
  printf(“%d\n”,searchedNode>data); //결과값 5
}
cs

Singly Linked List와 다른 부분이 하나도 없습니다.


노드 삭제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void DDL_removeNode(Node** head, Node* removedNode)
{
  if(*head == removedNode)
 {
  *head = removedNode>nextNode;
  if(*head != NULL)
 {
 (*head)>prevNode = NULL;
 }
 removedNode>nextNode = NULL;
 removedNode>prevNode = NULL;
 }
  else
 {
 Node* temp = removedNode;
 removedNode>prevNode>nextNode = temp>nextNode;
  if(removedNode>nextNode != NULL)
 removedNode>nextNode>prevNode = temp>prevNode;
 removedNode>nextNode = NULL;
 removedNode>prevNode = NULL;
 }
}
int main(int argc, const char * argv[])
{
 Node *list = NULL;
 Node *newNode = NULL;
 DDL_appendNode(&list, DLL_createNode(4));
 DDL_appendNode(&list, DLL_createNode(5));
 DDL_appendNode(&list, DLL_createNode(7));
 DDL_appendNode(&list, DLL_createNode(8));
 DDL_display(&list);
 Node* searchedNode = DDL_getNodeAt(list, 1);
 DDL_removeNode(&list, searchedNode);
 DDL_display(&list);
}
cs

Doubly Linked List의 삭제 연산은 삭제할 노드의 prev, next 그리고 이전 노드의 next, 다음 노드의 prev, 총 4가지 포인터를 수정해주어야 합니다. 보통 아래 순서대로 수정하시면 포인터 지정의 혼란을 피할 수 있습니다.

  1. 이전 노드의 next Node
  2. 다음 노드의 prev Node
  3. 삭제할 노드의 prev, next = NULL

노드 삽입

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void insertAfter(Node* current, Node* newNode)
{
  if(current != NULL)
 {
 newNode>prevNode = current;
 newNode>nextNode = current>nextNode;
  if(current>nextNode != NULL)
 current>nextNode>prevNode = newNode;
 current>nextNode = newNode;
 }
}
int main(int argc, const char * argv[])
{
 Node *list = NULL;
 Node *newNode = NULL;
 DDL_appendNode(&list, DLL_createNode(4));
 DDL_appendNode(&list, DLL_createNode(5));
 DDL_appendNode(&list, DLL_createNode(7));
 DDL_appendNode(&list, DLL_createNode(8));
 DDL_display(&list);
 Node* searchedNode = DDL_getNodeAt(list, 2);
 insertAfter(searchedNode, DLL_createNode(99));
 DDL_display(&list);
}
cs

노드 삭제와 마찬가지로 4가지 포인터(현재노드의 prev, next, 이전의 next, 다음의 prev)를 조정해야 합니다. 아래 순서대로 수정하면 혼선을 피할 수 있습니다.

  1. 현재 노드의 Prev
  2. 현재 노드의 Next
  3. 다음 노드의 Prev
  4. 이전 노드의 Next

C로 구현된 Doubly Linked List 전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
  int data;
  struct Node* nextNode;
  struct Node* prevNode;
} Node;
Node* DLL_createNode(int data)
{
 Node* newNode = (Node*)malloc(sizeof(Node));
 newNode>data = data;
 newNode>nextNode = NULL;
 newNode>prevNode = NULL;
  return newNode;
}
void DDL_destroyNode(Node* node)
{
  free(node);
}
void DDL_appendNode(Node** head, Node* newNode)
{
  if(*head == NULL)
 {
  *head = newNode;
 }
  else
 {
 Node *tail = *head;
  while(tail>nextNode != NULL)
 tail = tail>nextNode;
 tail>nextNode = newNode;
 newNode>prevNode = tail;
 }
}
Node* DDL_getNodeAt(Node* head, int index)
{
 Node* current = head;
  while(current != NULL && index >= 0)
 {
 current = current>nextNode;
 }
  return current;
}
void DDL_display(Node** head)
{
 Node* current = *head;
  printf(“PRINT CURRENT NODES\n”);
  printf(“===================\n”);
  while(current != NULL)
 {
  printf(“%d\t”,current>data);
 current = current>nextNode;
 }
  printf(“\n===================\n\n”);
}
void DDL_removeNode(Node** head, Node* removedNode)
{
  if(*head == removedNode)
 {
  *head = removedNode>nextNode;
  if(*head != NULL)
 {
 (*head)>prevNode = NULL;
 }
 removedNode>nextNode = NULL;
 removedNode>prevNode = NULL;
 }
  else
 {
 Node* temp = removedNode;
 removedNode>prevNode>nextNode = temp>nextNode;
  if(removedNode>nextNode != NULL)
 removedNode>nextNode>prevNode = temp>prevNode;
 removedNode>nextNode = NULL;
 removedNode>prevNode = NULL;
 }
}
void insertAfter(Node* current, Node* newNode)
{
  if(current != NULL)
 {
 newNode>prevNode = current;
 newNode>nextNode = current>nextNode;
  if(current>nextNode != NULL)
 current>nextNode>prevNode = newNode;
 current>nextNode = newNode;
 }
}
int main(int argc, const char * argv[])
{
 Node *list = NULL;
 Node *newNode = NULL;
 DDL_appendNode(&list, DLL_createNode(4));
 DDL_appendNode(&list, DLL_createNode(5));
 DDL_appendNode(&list, DLL_createNode(7));
 DDL_appendNode(&list, DLL_createNode(8));
 DDL_display(&list);
 Node* searchedNode = DDL_getNodeAt(list, 2);
 insertAfter(searchedNode, DLL_createNode(99));
 DDL_display(&list);
}
cs

참조

댓글 남기기