저번에는 단일 연결 리스트를 간단하게 구현해보았습니다. 그래서 이번에는 이중 연결 리스트에 대해 알아보고 구현해보도록 해보겠습니다.
탐색과 출력은 단일 연결 리스트와 크게 다른점이 없기 때문에 설명을 하지 않고 노드 정의와 추가, 삭제 연산에 대해서 설명해 보겠습니다.
단일 연결 리스트의 구현을 보고 오시면 이중 연결 리스트를 이해하시는데 더욱더 도움이 될 겁니다.
data structure(자료 구조) - Singly Linked List(단일 연결 리스트)의 노드 정의, 탐색 연산 구현::FBTT
지난번 글에서는 연결 리스트의 의미에 대해서 써보았습니다. 아래의 글을 보고 오신다면 이번 글에 대해 더 깊은 이해가 가능할 것 같습니다. https://readytoearndon.tistory.com/30 data structure(자료 구조)..
readytoearndon.tistory.com
data structure(자료 구조) - Singly Linked List(단일 연결 리스트)의 추가 연산 구현::FBTT
이번 글에서는 지난 글에 이어서 단일 연결 리스트의 구현을 해보겠습니다. 아래의 글은 노드의 정의와 탐색을 구현해놓았습니다. 먼저 보고 오시는 것을 추천드립니다. https://readytoearndon.tistory.com/31 da..
readytoearndon.tistory.com
data structure(자료 구조) - Singly Linked List(단일 연결 리스트)의 삭제 연산과 출력 기능 구현::FBTT
https://readytoearndon.tistory.com/31 data structure(자료 구조) - Singly Linked List(단일 연결 리스트)의 노드 정의, 탐색 연산 구현::FBTT 지난번 글에서는 연결 리스트의 의미에 대해서 써보았습니다. 아..
readytoearndon.tistory.com
이중 연결 리스트의 노드
이중 연결 리스트와 단일 연결 리스트의 차이점은 이름에서도 알다시피 연결의 개수입니다.
단일 연결 리스트는 한 방향으로만 연결되어 있어 다음 노드로의 접근만이 가능했습니다.
그러나 이중 연결 리스트는 다음 노드로의 접근뿐만 아니라 이전 노드로의 접근도 가능하게 링크가 연결되어 있습니다.
노드를 C언어로 정의하면 아래의 코드와 같습니다.
|
1
2
3
4
5
6
7
8
|
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
}node;
|
cs |
단일 연결 리스트와의 차이점은 이전 노드를 가리키는 포인터인 prev가 추가되었다는 점입니다.
그 외에는 다른 점이 없습니다.
insert(추가) 연산
추가 연산에서도 단일 연결 리스트와 큰 차이는 없습니다.
링크를 연결해주는 부분이 단일 연결 리스트보다 조금 복잡해질 뿐이죠.
|
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
|
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
}node;
node* init = NULL;
node* tail = NULL;
node* linear_search(int key)
{
node* current = init;
while (current != NULL)
{
if (current->data == key)
return current;
current = current->next;
}
return NULL;
}
//init부분에 추가
void insert(int data)
{
node* newnode = (node*)malloc(sizeof(node));
newnode->data = data;
if (init == NULL)
{
init = newnode;
tail = newnode;
init->next = NULL;
}
else
{
newnode->next = init;
init->prev = newnode;
init = newnode;
init->prev = NULL;
}
}
|
cs |
28~46line이 추가 연산에 대한 구현입니다. 이 코드는 앞 부분에 계속 노드를 추가하는 방식이여서 리스트의 끝을 가리키는 tail이라는 변수가 필요없지만 나중에 prev로 잘 연결되어 있는지 확인하기 위한 용도로 추가 했습니다.
마찬가지로 init->prev = NULL;이 문장 또한 추가해주었습니다.
prev의 연결을 확인하기 위해 반대로 출력할 때 필요합니다.
굳이 반대로 출력하지 않는다면 tail 변수와 init->prev = NULL;은 필요없다는 뜻입니다.
if문은 바뀐 것이 없지만 else아래를 보면 새로 추가할 노드(newnode)의 다음(next)을 init이 가리키는 노드로 연결해주고 init이 가리키는 노드의 이전 노드(prev)를 newnode로 설정해줍니다.
단일 연결 리스트와 비교하여 init->prev = newnode; 이 문장 하나가 추가되었습니다.
이중 연결 리스트에서 추가 연산을 할 때 만약 노드를 중간에 삽입한다면 고쳐야할 링크가 4개가 되기 때문에 지금보다 복잡해집니다.
우선 익숙해지는 것에 초점을 맞추고 나중에 크기 순으로 삽입하는 연결 리스트를 구현해보도록 하겠습니다.
delete(삭제) 연산
삭제 연산에서도 해주어야 할 것은 link를 다시 연결해주는 것 밖에 없습니다.
기본적으로 단일 연결 리스트와 크게 다를 것이 없죠.
우선 코드부터 보겠습니다.
|
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
|
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
}node;
node* init = NULL;
node* tail = NULL;
node* linear_search(int key)
{
node* current = init;
while (current != NULL)
{
if (current->data == key)
return current;
current = current->next;
}
return NULL;
}
//init부분에 추가
void insert(int data)
{
node* newnode = (node*)malloc(sizeof(node));
newnode->data = data;
if (init == NULL)
{
init = newnode;
tail = newnode;
init->next = NULL;
}
else
{
newnode->next = init;
init->prev = newnode;
init = newnode;
init->prev = NULL;
}
}
void node_delete(int data)
{
node* current = init;
if (init->data == data)
{
node* dnode = init;
init = init->next;
init->prev = NULL;
free(dnode);
return 0;
}
while (current->next != NULL)
{
if (current->next->data == data)
break;
current = current->next;
}
if (current->next->next == NULL)
{
node* dnode = current->next;
current->next = NULL;
tail = current;
free(dnode);
return 0;
}
else
{
node* dnode = current->next;
current->next = dnode->next;
dnode->next->prev = dnode->prev;
free(dnode);
return 0;
}
}
|
cs |
delete 연산이 구현된 함수는 48~84line입니다.
if문이 2개가 보이는데요, while문 이전의 if문은 삭제하려는 노드가 첫번째 노드일 경우입니다. 그 다음 if문은 삭제하려는 노드가 마지막 노드일 경우이고 else 이하는 삭제하려는 노드가 중간에 있는 경우입니다.
while문 이후의 if문 하나가 추가된 이유는 앞에서 말했다시피 끝에서부터 출력하기 위해 tail을 재설정하기 위해서입니다.
나머지는 모두 단일 연결과 비슷하니 else 이하만 좀 보면 current의 next는 dnode의 next node를 가리키게 하고 dnode의 next의 prev(dnode의 다음 노드가 자기의 전 노드를 가리키는 포인터)는 current 즉 dnode의 prev(dnode의 전 노드)를 가리키게 합니다.
이제 모두 구현되었으니 확인을 해보겠습니다.
|
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
|
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
}node;
node* init = NULL;
node* tail = NULL;
node* linear_search(int key)
{
node* current = init;
while (current != NULL)
{
if (current->data == key)
return current;
current = current->next;
}
return NULL;
}
//init부분에 추가
void insert(int data)
{
node* newnode = (node*)malloc(sizeof(node));
newnode->data = data;
if (init == NULL)
{
init = newnode;
tail = newnode;
init->next = NULL;
}
else
{
newnode->next = init;
init->prev = newnode;
init = newnode;
init->prev = NULL;
}
}
void node_delete(int data)
{
node* current = init;
if (init->data == data)
{
node* dnode = init;
init = init->next;
init->prev = NULL;
free(dnode);
return 0;
}
while (current->next != NULL)
{
if (current->next->data == data)
break;
current = current->next;
}
if (current->next->next == NULL)
{
node* dnode = current->next;
current->next = NULL;
tail = current;
free(dnode);
return 0;
}
else
{
node* dnode = current->next;
current->next = dnode->next;
dnode->next->prev = dnode->prev;
free(dnode);
return 0;
}
}
void print()
{
node* current = init;
while (current != NULL)
{
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
void print_reverse()
{
node* current = tail;
while (current != NULL)
{
printf("%d ", current->data);
current = current->prev;
}
printf("\n");
}
int main(void)
{
insert(10);
insert(12);
insert(13);
insert(14);
insert(15);
insert(16);
print();
node_delete(10);
node_delete(12);
print_reverse();
node* p = linear_search(13);
printf("%d \n", p->data);
}
|
cs |
모두 정상적으로 실행이 되는 것을 볼 수 있습니다.
이중 연결 리스트는 이전의 단일 연결 리스트를 모두 이해하였다면 어려움이 없었을 것입니다.
단일 연결 리스트에서 구현했던 것을 최대한 바꾸지 않고 링크를 갱신하는 과정만 변경해주었습니다.
연결 리스트는 이쯤에 마치고 다음 글에서는 다른 자료구조에 대해서 공부하도록 하겠습니다.
