이중 연결 리스트(Double linked list), 이중 원형 연결 리스트 예제

오늘은 이중 연결 리스트(Double linked list)에 대해서 알아보려고 합니다. 이중 연결 리스트는 prev, next라는 2개의 방향을 가리키는 포인터를 가지고 있는 리스트입니다. prev라는 이전 노드를 가리키는 포인터, next라는 다음 노드를 가리키는 포인터를 갖고 있기 때문에 양쪽으로 탐색이 가능합니다. 이중 연결 리스트는 Head라는 처음을 가리키는 노드와 Tail이라는 마지막을 가리키는 노드를 갖고 있는데요, 저는 Head만을 이용해서 이중 연결 리스트를 원형으로 구현을 해보도록 하겠습니다.

이중 연결 리스트 구조

그림으로 표현을 하자면 이중 연결 리스트의 경우 위에 와 같이 처음 시작 노드에는 Head 노드가 있고 마지막 노드에는 Tail 노드가 있습니다.

이중 원형 연결 리스트

제가 구현할 연결 리스트는 노드의 처음 부분은 Head가 되고 Tail은 Head->prev가 되게 됩니다.

이중 원결 리스트 구현(1) - 초기화, Insert Head/Tail

구조체

1
2
3
4
5
typedef struct _Node {
    int data;
    struct _Node *prev;
    struct _Node *next;
}Node;

- Node의 구조체입니다. 구조체에는 Data와 이전 노드와 다음 노드를 가리키는 prev, next 포인터가 들어갑니다.

노드 생성

1
2
3
4
5
6
7
8
9
10
11
Node *CreateNode()
{
    Node *New_Node = (Node *)malloc(sizeof(Node));
 
    if(New_Node == NULL) return New_Node;
    
    New_Node->data = 0;
    New_Node->prev = New_Node->next = NULL;
 
    return New_Node;
}

- Node를 생성하는 함수입니다. 생성된 노드의 메모리를 할당 후에 Data와 Prev, next의 값을 초기화해줍니다.

Head 초기화

1
2
3
4
5
6
7
8
9
10
11
Node *Head;
void Init_Head()
{
    Head = CreateNode();
 
    if(Head == NULL) return;
    
    Head->data = 0;
    Head->prev = Head->next = Head;
}

- Node의 앞 부분, 기준이 되는 Head 노드입니다. 초기엔 아무것도 없기 때문에 Head의 next, prev의 초깃값은 자기 자신인 Head를 가리켜야 합니다. Head의 next와 prev의 값을 이용해 노드의 존재 여부를 확인할 수 있습니다.

Head 노드 삽입

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Insert_Head(Node *New_Node, int data)
{
    New_Node = CreateNode();
 
    if(New_Node == NULL) return;
    
    // 새로운 노드 연결.
    New_Node->prev = Head;
    New_Node->next = Head->next;
    New_Node->prev->next = New_Node;
    New_Node->next->prev = New_Node;
 
    // data 삽입.
    New_Node->data = data;
}

- Head에 노드를 삽입하는 함수입니다. 코드로만 봐서는 이해가 쉽게 되지 않기 때문에 그림을 통해서 살펴보겠습니다.

Head만 있는 경우 Insert Head

Head 노드만 있는 상태에서 새로운 노드를 삽입한 경우에 대해서 알아보겠습니다. Insert Head 부분이 새로운 노드입니다.

<Node의 prev, next 연결>

1. Node(Insert Head)의 이전 노드(prev)는 당연히 Head가 됩니다. (Node->prev = Head)

2. 원형 연결 리스트이기 때문에 Node(Insert Head)의 Next는 Head가 되게 됩니다. (Node->next = Head)

노드가 삽입되기 전 Head->next는 Head이기 때문에 Node->next = Head->next라고도 표현을 할 수 있습니다.

<Head의 prev, next 연결>

3. Node(Insert Head)의 prev는 Head이고 Head의 next는 node이기 때문에 이를 Node->prev->next = Node라고 할 수 있습니다.

4. Node(Insert Head)의 next는 Head이고 Head의 prev는 node이기 때문에 이를 Node->next->prev = Node라고 할 수 있습니다.

Node가 있는 상태에서 Insert Head

노드가 있는 상태에서 Head와 노드 사이에 새로운 노드를 삽입을 하는 경우입니다. 새로운 노드를 삽입하는 경우 Head next와 2번째 노드의 prev를 재정의를 해줘야 합니다.

<Node의 prev, next 연결>

1. 노드(Insert Head)의 prev는 Head가 되게 됩니다. (Node->prev = Head)

2. 노드(Insert Head)의 next는 2번째 노드를 가리켜야 합니다. 두 번째 노드는 Head의 next이기 때문에 Node->next = Head->next가 되게 됩니다.

<Head의 next 연결>

3. Node(Insert Head)의 prev는 Head이고 Head의 next는 노드이기 때문에 Node->prev->next = Node라고 할 수 있습니다.

<두 번째 노드의 prev 연결>

4. Node(Insert Head)의 next는 두 번째 노드이며 두 번째 노드의 prev는 노드이기 때문에 Node->next->prev = Node라고 할 수 있습니다.

※Insert Head

즉, Node가 아무리 증가를 하더라도 Head Node 삽입은 아래와 같이 표현을 할 수 있게 됩니다.

Node->prev = Head;

Node->next = Head->next;

Node->prev->next =Node;

Node->next->prev =Node;

Tail 노드 삽입

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Insert_Tail(Node *New_Node, int data)
{
    New_Node = CreateNode();
 
    if(New_Node == NULL) return;
 
    // 새로운 노드 연결.
    New_Node->prev = Head->prev;
    New_Node->next = Head;
    New_Node->prev->next = New_Node;
    New_Node->next->prev = New_Node;
 
    // data 삽입.
    New_Node->data = data;
}

- Tail에 노드를 삽입하는 함수입니다. Tail은 별도로 없기 때문에 Head->prev가 Tail 노드가 됩니다. 이번에도 그림을 통해서 알아보도록 하겠습니다.

Head만 있는 경우 Insert Tail

Insert Head를 했기 때문에 Tail은 쉽게 할 수 있겠네요. Head의 prev, next 그리고 Insert Tail의 prev, next를 연결을 해야 합니다.

<Node의 prev, next 연결>

1. Node(Insert Tail)의 prev는 Head이기 때문에 Node->prev = Head가 됩니다.

Node가 삽입되기 전 Head->prev는 Head이기 때문에 Node->prev = Head->prev라고 할 수 있습니다.

2. Node(Insert Tail)의 next는 항상 Head이기 때문에 Node->next = Head가 됩니다.

<Head의 prev, next 연결>

3. Node(Insert Tail)의 prev는 Head이고 Head의 next는 node이기 때문에 이를 Node->prev->next = Node라고 할 수 있습니다.

4. Node(Insert Tail)의 next는 Head이고 Head의 prev는 node이기 때문에 이를 Node->next->prev = Node라고 할 수 있습니다.

Node가 있는 상태에서 Insert Head

노드가 있는 상태에서 새로운 노드(Insert Tail)를 삽입을 하는 경우입니다. 새로운 노드(Insert Tail)를 삽입하는 경우 이전 노드의 next, Head 노드의 prev를 재정의를 해줘야 합니다.

<Node의 prev, next 연결>

1. Insert Tail을 하는 경우 prev는 이전 노드가 되게 됩니다. 이전 노드는 Head->prev이기 때문에 Node->prev = Head->prev가 됩니다.

2. 노드(Insert Tail)의 next는 항상 Head이기 때문에 Node->next = Head가 됩니다.

<이전 Node의 next 연결>

3. Node(Insert Tail)의 prev는 이전 노드이며 노드의 next는 Tail이기 때문에 Node->prev->next = Node라고 할 수 있습니다.

<Head의 prev 연결>

4. Node(Insert Tail)의 next는 Head이며 Head의 prev는 Tail이기 때문에 Node->next->prev = Node라고 할 수 있습니다.

※Insert Tail

즉, Node가 아무리 증가를 하더라도 Head Node 삽입은 아래와 같이 표현을 할 수 있게 됩니다.

Node->prev = Head->prev;

Node->next = Head;

Node->prev->next =Node;

Node->next->prev =Node;

이중 원결 리스트 구현(2) - Remove Head/Tail, Print All Node

1
2
3
4
5
6
7
uint8 Check_Node_Empty()
{
    if(Head->prev == Head && Head->next == Head)
        return FAIL;
    else 
        return SUCCESS;    
}

- Node가 존재하는지 확인을 하는 함수입니다.

노드가 없는 상태에서 Head의 prev와 next의 초깃값은 Head이기 때문에 Head->prev = Head이면서 Head->next = Head인 경우는 노드가 존재하지 않는 경우입니다. 노드가 존재하지 않는 경우 Fail을 return 하게 됩니다.

Remove Head

1
2
3
4
5
6
7
8
9
10
11
12
13
14
uint8 Remove_Head()
{
    Node *Target = Head->next;
 
    // Node의 존재 여부를 확인.
    if(!Check_Node_Empty())
        return FAIL;
 
    Target->prev->next = Target->next;
    Target->next->prev = Target->prev;
    free(Target);
 
    return SUCCESS;    
}

- Head 노드를 제거하는 함수입니다.

Remove Head를 하는 경우 Head의 next와 Remove 노드 다음 노드(2번째 노드)의 prev를 재정의 해야 합니다.

노드의 prev는 Head이고 Head의 next는 2번째 노드를 가리켜야 하기 때문에 Node->prev->next = Node->next가 되게 됩니다.

노드의 next는 2번째 노드이고 이 노드는 Head와 연결이 되어야 하기 때문에 Node->next->prev = Node->prev가 되게 됩니다.

Remove node의 prev와 node는 따로 정의하지 않고 free(Node)를 합니다. 이로써 Remove Head와의 연결은 끊기게 되고 Head의 next는 Remove Head 다음의 노드(2번째 노드)가 되고 2번째 노드의 prev는 Head가 되어 Remove Head는 사라지게 됩니다.

Remove Tail

1
2
3
4
5
6
7
8
9
10
11
12
13
14
uint8 Remove_Tail()
{
    Node *Target = Head->prev;
 
    // Node의 존재 여부 확인.
    if(!Check_Node_Empty())
        return FAIL;
 
    Target->prev->next = Target->next;
    Target->next->prev = Target->prev;
    free(Target);
 
    return SUCCESS;
}

- Tail 노드를 제거하는 함수입니다.

Remove Tail을 하는 경우 Tail의 이전 노드의 next와 Head의 prev를 재정의 해야 합니다.

Remove tail의 prev는 Tail의 전 Node가 되고 이 노드의 next는 Head가 되어야 하기 때문에 Node->prev->next = Node->next가 됩니다.

Remove tail의 next는 Head이고 Head의 prev는 tail의 이전 노드가 되어야 하기 때문에 Node->next->prev = Node->prev가 됩니다.

Remove Tail의 연결된 노드를 끊고 첫 번째 노드의 next는 Head가 되었고 Head의 prev는 첫 번째 노드가 되었습니다.

Print All Node

1
2
3
4
5
6
7
8
9
10
11
12
void Print_All_Node()
{
    Node *Target = Head->next;
 
    if (!Check_Node_Empty()) 
        return;
    
    while(Target != Head){
        printf("Data : %d\r\n", Target->data);
        Target = Target->next;
    }
}

- Node의 모든 값은 출력하는 함수입니다.

처음 노드를 출력하고 다음 노드가 Head인지 아닌지 판별을 하여 Head가 아니면 노드를 출력하게 됩니다.

소스 코드 및 테스트 결과

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
 
typedef struct _Node {
    int data;
    struct _Node *prev;
    struct _Node *next;
}Node;
 
Node *CreateNode()
{
    Node *New_Node = (Node *)malloc(sizeof(Node));
 
    if(New_Node == NULL) return New_Node;
    
    New_Node->data = 0;
    New_Node->prev = New_Node->next = NULL;
 
    return New_Node;
}
 
Node *Head;
void Init_Head()
{
    Head = CreateNode();
 
    if(Head == NULL) return;
    
    Head->data = 0;
    Head->prev = Head->next = Head;
}
 
void Insert_Head(Node *New_Node, int data)
{
    New_Node = CreateNode();
 
    if(New_Node == NULL) return;
    
    // 새로운 노드 연결.
    New_Node->prev = Head;
    New_Node->next = Head->next;
    New_Node->prev->next = New_Node;
    New_Node->next->prev = New_Node;
 
    // data 삽입.
    New_Node->data = data;
}
 
void Insert_Tail(Node *New_Node, int data)
{
    New_Node = CreateNode();
 
    if(New_Node == NULL) return;
 
    // 새로운 노드 연결.
    New_Node->prev = Head->prev;
    New_Node->next = Head;
    New_Node->prev->next = New_Node;
    New_Node->next->prev = New_Node;
 
    // data 삽입.
    New_Node->data = data;
}
 
uint8 Check_Node_Empty()
{
    if(Head->prev == Head && Head->next == Head)
        return FAIL;
    else 
        return SUCCESS;    
}
 
uint8 Remove_Head()
{
    Node *Target = Head->next;
 
    // Node의 존재 여부를 확인.
    if(!Check_Node_Empty())
        return FAIL;
 
    Target->prev->next = Target->next;
    Target->next->prev = Target->prev;
    free(Target);
 
    return SUCCESS;    
}
 
uint8 Remove_Tail()
{
    Node *Target = Head->prev;
 
    // Node의 존재 여부 확인.
    if(!Check_Node_Empty())
        return FAIL;
 
    Target->prev->next = Target->next;
    Target->next->prev = Target->prev;
    free(Target);
 
    return SUCCESS;
}
 
void Print_All_Node()
{
    Node *Target = Head->next;
 
    if (!Check_Node_Empty()) 
        return;
    
    while(Target != Head){
        printf("Data : %d\r\n", Target->data);
        Target = Target->next;
    }
}
 
void Control_List(void)
{
    Node *Node = NULL;
 
    Init_Head();
    Insert_Tail(Node, 1);
    Insert_Tail(Node, 2);
    Insert_Tail(Node, 3);
    Insert_Tail(Node, 3);
    Insert_Head(Node, 9);
    Remove_Tail();
    Print_All_Node();
}
 
int main(void)
{
    Control_List();
 
    return 0;
}