[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

참조