연결리스트
연결리스트란?
- 서로 연결되어 있지 않은 값들을 임의로 연결하여 배열과 같은 역할을 수행하는 자료구조
- 구성요소
- 데이터를 담는 변수
- 특정 노드를 연결하는 포인터 변수
종류
단일 연결리스트
head부터 시작하여 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 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
#include <stdio.h> #include <stdlib.h> #define ERR -99999 // making stack using linked list typedef struct Node { int key; struct Node *next; } ND; // function that creates new node // returns pointer of new node ND *createNewNode(int value) { ND *temp = (ND *)malloc(sizeof(ND)); if (!temp) { // defensive coding return NULL; } temp->key = value; return temp; // node return } // insert new node to linked list // return 0 if successfully inserted, else return 1 int insert(ND **head, int value) { ND *temp = createNewNode(value); if (!temp) // can't create new node return 1; ND *cur = *head, *pre = NULL; if (!*head) { // no node in linked list *head = temp; return 0; } while (cur) // find tail of linked list pre = cur, cur = cur->next; pre->next = temp; // link new node to the tail of linked list return 0; } int delete (ND **head) { if (!(*head)) { // no node in linked list printf("No node!"); return ERR; } else if (!(*head)->next) { // only 1 node in linked list ND *temp = *head; *head = NULL; // no node in linked list int retval = temp->key; free(temp); // delete node return retval; // return node's key value } ND *pre = NULL, *cur = *head; while (cur->next) // find tail of linked list pre = cur, cur = cur->next; ND *temp = cur; // tail of linked list pre->next = NULL; // cut link int retval = temp->key; free(temp); // delete node return retval; } int main() { ND *head = NULL; // head of linked list /* using some code */ return 0; }
원형 연결리스트
소스코드
여러 가지로 응용 가능
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
/* myLinkedList.c */
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *next;
} ND;
typedef ND *NDPtr;
NDPtr createNewNode(int value); // create a Node
void insertToHead(NDPtr *head, NDPtr node); // insert node to First
void insertToMiddle(NDPtr *head, NDPtr node); // insert node to Middle
void insertToTail(NDPtr *head, NDPtr node); // insert node to Tail
void deleteFromHead(NDPtr *head); // delete node from head
void deleteFromMiddle(NDPtr *head); // delete node from middle
void deleteFromTail(NDPtr *head); // delete node from tail
NDPtr findTail(NDPtr head); // find Tail of List
NDPtr search(NDPtr head, int value); // search the value
void changeValue(NDPtr head); // change node's value to input
int isEmpty(NDPtr head); // 1 if Empty, 0 if not Empty
void printList(NDPtr head); // print All List
void instructions(); // how to use this system
int getInput(); // get input type int
int main() {
NDPtr Head = NULL;
int choose, end = 1, temp;
while (end) {
instructions();
scanf("%d", &choose);
switch (choose) {
case 1:
insertToHead(&Head, createNewNode(getInput()));
break;
case 2:
insertToMiddle(&Head, createNewNode(getInput()));
break;
case 3:
insertToTail(&Head, createNewNode(getInput()));
break;
case 4:
deleteFromHead(&Head);
break;
case 5:
deleteFromMiddle(&Head);
break;
case 6:
deleteFromTail(&Head);
break;
case 7:
temp = getInput();
if (search(Head, temp))
printf("%d found!\n", temp);
else
printf("%d not found!\n", temp);
break;
case 8:
printList(Head);
break;
case 9:
changeValue(Head);
break;
case 0:
end = 0;
break;
}
}
printf("End of System");
char str;
scanf("\n%c", &str);
return 0;
}
NDPtr createNewNode(int value) { // create a Node
NDPtr temp = (NDPtr)malloc(sizeof(ND));
if (temp) {
temp->value = value;
temp->next = NULL;
}
return temp;
}
void insertToHead(NDPtr *head, NDPtr node) { // change fisrt node to Node
node->next = *head;
*head = node;
return;
}
void insertToMiddle(NDPtr *head, NDPtr node) {
if (isEmpty(*head)) {
printf("List is Empty!\n");
free(node);
return;
}
NDPtr temp = search(*head, getInput());
if (!temp) {
printf("Target Not Found!\n");
free(node);
}
else {
node->next = temp->next;
temp->next = node;
}
return;
}
void insertToTail(NDPtr *head, NDPtr node) { // 맨 처음에 삽입이 안되는 문제가 있음
if (isEmpty(*head))
*head = node;
else
findTail(*head)->next = node;
return;
}
void deleteFromHead(NDPtr *head) {
if (isEmpty(*head)) {
printf("List is Empty!\n");
return;
}
NDPtr temp = *head;
*head = temp->next;
free(temp);
return;
}
void deleteFromMiddle(NDPtr *head) {
if (isEmpty(*head)) {
printf("List is Empty!\n");
return;
}
int a = getInput();
if (search(*head, a)) {
NDPtr temp = *head;
if (temp->value == a) {
deleteFromHead(head);
return;
}
while (temp->next->value != a)
temp = temp->next;
NDPtr temp2 = temp->next;
temp->next = temp2->next;
free(temp2);
}
else
printf("Target not Founded!\n");
return;
}
void deleteFromTail(NDPtr *head) {
if (isEmpty(*head)) {
printf("List is Empty!\n");
return;
}
NDPtr temp = *head;
if (!temp->next) {
free(temp);
*head = NULL;
return;
}
while (temp->next->next)
temp = temp->next;
NDPtr temp2 = temp->next;
temp->next = NULL;
free(temp2);
return;
}
NDPtr findTail(NDPtr head) { // find Tail of list
NDPtr temp = head;
while (temp->next)
temp = temp->next;
return temp;
}
NDPtr search(NDPtr head, int value) { // find node with value in list
NDPtr temp = head;
while (temp && temp->value != value)
temp = temp->next;
return temp;
}
void changeValue(NDPtr head) {
NDPtr temp = search(head, getInput());
if (temp)
temp->value = getInput();
else
printf("Can't find that value!\n");
return;
}
int isEmpty(NDPtr head) { // 1 if Empty, 0 if not Empty
if (head)
return 0;
else
return 1;
}
void printList(NDPtr head) {
NDPtr temp = head;
if (isEmpty(head)) {
printf("List is Empty!\n");
return;
}
while (temp) {
printf("%d -> ", temp->value);
temp = temp->next;
}
printf("NULL\n");
return;
}
void instructions() {
printf("1 : 리스트 맨 앞에 삽입\n"
"2 : 리스트 중간에 삽입\n"
"3 : 리스트 맨 뒤에 삽입\n"
"4 : 리스트 맨 앞 노드 삭제\n"
"5 : 리스트 중간 노드 삭제\n"
"6 : 리스트 맨 뒤 노드 삭제\n"
"7 : 리스트 값 검색\n"
"8 : 리스트 전체출력\n"
"9 : 리스트 특정 값 수정\n"
"0 : 종료\n"
"Choose? ");
return;
}
int getInput() {
int temp;
printf("Input a Data :: ");
scanf("%d", &temp);
return temp;
}
기본 구현 방법
- 시작점 포인터를 생성 ( head )
- 노드를 동적할당으로 만들어 목적에 맞게 연결시킴 ( 앞 / 중간 / 뒤 )
- 노드를 삭제할 때는 연결을 재설정 한 후 free 해주어야 함 ( 메모리 누수 우려 )