Data Structure : List
자료구조(출처)
순차 자료구조로 구현한 리스트
Linear 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
void insertElement(int *L, int size, int element) {
int index;
for(int i=0; i<size; i++) {
if(element <= L[i]) {
index=i;
break;
}
}
if(index == size) {index=size;}
for(int i=size; i>index;i--) {L[i]=L[i-1];}
L[index]=element;
}
void deleteElement(int *L, int size, int element) {
int index;
for(int i=0; i<size;i++) {
if(L[i] == element) {
index=i;
break;
}
}
if(index==size) {return;}
for(int i=index; i<size-1;i++) {L[i]=L[i+1];}
}
연결 자료구조로 구현한 리스트
Linear 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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct ListNode {
char data[4];
struct ListNode* link;
} listNode;
typedef struct {
listNode* head;
} linkedlist_h;
linkedlist_h* createLinkedList_h(void) {
linkedlist_h* L;
L = (linkedlist_h*)malloc(sizeof(linkedlist_h));
L->head = NULL;
return L;
}
void freeLinkedList_h(linkedlist_h* L) {
listNode* node;
while(L->head != NULL) {
node=L->head;
L->head=L->head->link;
free(node);
node=NULL;
}
}
void printList(linkedlist_h* L) {
listNode* node=L->head;
printf("L = (");
while(node != NULL) {
printf("%s",node->data);
node=node->link;
if(node != NULL) {
printf(", ");
}
}
printf(") \n");
}
void insertFirstNode(linkedlist_h* L, char* data) {
listNode* new = (listNode*)malloc(sizeof(listNode));
strcpy(new->data,data);
new->link=L->head;
L->head=new;
}
void insertMiddleNode(linkedlist_h* L, listNode* pre, char* data) {
listNode* new=(listNode*)malloc(sizeof(listNode));
strcpy(new->data, data);
if(L->head == NULL) {
new->link=NULL;
L->head=new;
}
else if(pre == NULL){
new->link=L->head;
L->head=new;
}
else {
new->link=pre->link;
pre->link=new;
}
}
void insertLastNode(linkedlist_h* L, char* data) {
listNode* lastnode=L->head;
listNode* new=(listNode*)malloc(sizeof(listNode));
strcpy(new->data, data);
new->link=NULL;
if(L->head == NULL) {
L->head=new;
return;
}
while(lastnode->link != NULL) { lastnode=lastnode->link;}
lastnode->link=new;
}
listNode* searchNode(linkedlist_h* L, char* data) {
listNode* f=L->head;
while(f != NULL) {
if(strcmp(f->data,data) == 0) { return f; }
else { f=f->link; }
}
return f;
}
void deleteNode(linkedlist_h* L, listNode* dNode) {
listNode* pre;
if((L-> head == NULL) || (dNode == NULL)) {return;}
if(L->head->link == NULL) {
free(L->head);
L->head=NULL;
return;
}
else if(L->head == dNode) {
L->head=dNode->link;
free(dNode);
}
else {
pre=L->head;
while(pre->link != dNode) { pre=pre->link; }
pre->link=dNode->link;
free(dNode);
}
}
void reverse(linkedlist_h* L) {
listNode* p=L->head;
listNode* q=NULL;
listNode* r=NULL;
while(p != NULL) {
r=q;
q=p;
p=p->link;
q->link=r;
}
L->head=q;
}
Circular 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
106
107
108
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct ListNode {
char data[4];
struct ListNode* link;
} listNode;
typedef struct {
listNode* head;
} linkedlist_h;
linkedlist_h* createLinkedList_h(void) {
linkedlist_h* CL;
CL = (linkedlist_h*)malloc(sizeof(linkedlist_h));
CL->head = NULL;
return CL;
}
void freeLinkedList_h(linkedlist_h* CL) {
listNode* node;
listNode* head=CL->head;
while(CL->head != head) {
node=CL->head;
CL->head=CL->head->link;
free(node);
node=NULL;
}
}
void printList(linkedlist_h* CL) {
listNode* node;
node=CL->head;
printf("CL = (");
if(CL->head == NULL) { printf(") \n"); return; }
do {
node=node->link;
if(node != CL->head) { printf(", "); }
} while(node != CL->head);
printf(") \n");
}
void insertFirstNode(linkedlist_h* CL, char* data) {
listNode* temp=CL->head;
listNode* new=(listNode*)malloc(sizeof(listNode));
strcpy(new->data,data);
if(CL->head == NULL) {
CL->head = new;
new->link=new;
}
else {
while(temp->link != CL->head) {temp=temp->link;}
new->link=temp->link;
temp->link=new;
CL->head=new;
}
}
void insertMiddleNode(linkedlist_h* CL, listNode* pre, char* data) {
listNode* new=(listNode*)malloc(sizeof(listNode));
strcpy(new->data, data);
if(CL->head == NULL) {
new->link=NULL;
CL->head=new;
}
else if(pre == NULL){
new->link=CL->head;
CL->head=new;
}
else {
new->link=pre->link;
pre->link=new;
}
}
listNode* searchNode(linkedlist_h* CL, char* data) {
listNode* f=CL->head;
if(f == NULL) { return;}
do {
if(strcmp(f->data,data) == 0) { return f; }
else f=f->link;
} while(f != CL->head);
return f;
}
void deleteNode(linkedlist_h* CL, listNode* dNode) {
if((CL-> head == NULL) || (dNode == NULL)) {return;}
if(CL->head->link == CL->head) {
free(CL->head);
CL->head=NULL;
return;
}
else if(CL->head == dNode) {
listNode* lastnode=CL->head;
while(lastnode->link != CL->head) { lastnode=lastnode->link;}
CL->head=dNode->link;
lastnode->link=CL->head;
free(dNode);
}
else {
listNode* pre=CL->head;
while(pre->link != dNode) { pre=pre->link; }
pre->link=dNode->link;
if(dNode == CL->head) { CL->head = dNode->link; }
free(dNode);
}
}
Double 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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct ListNode {
char data[4];
struct ListNode* llink, *rlink;
} listNode;
typedef struct {
listNode* head;
} linkedlist_h;
linkedlist_h* createLinkedList_h(void) {
linkedlist_h* DL;
DL = (linkedlist_h*)malloc(sizeof(linkedlist_h));
DL->head = NULL;
return DL;
}
void freeLinkedList_h(linkedlist_h* DL) {
listNode* node;
while(DL->head != NULL) {
node=DL->head;
DL->head=DL->head->rlink;
free(node);
node=NULL;
}
}
void printList(linkedlist_h* DL) {
listNode* node=DL->head;
printf("DL = (");
while(node != NULL) {
printf("%s",node->data);
node=node->rlink;
if(node != NULL) {
printf(", ");
}
}
printf(") \n");
}
void insertNode(linkedlist_h* DL, listNode* pre, char* data) {
listNode* new=(listNode*)malloc(sizeof(listNode));
strcpy(new->data, data);
if(DL->head == NULL) {
new->llink=NULL;
new->rlink=NULL;
DL->head=new;
}
else if(pre == NULL) {
listNode* lastnode=DL->head;
while(lastnode->rlink != NULL) { lastnode=lastnode->rlink; }
new->rlink=NULL;
new->llink=lastnode;
lastnode->rlink=new;
}
else {
new->rlink=pre->rlink;
new->llink=pre;
pre->rlink=new;
if(new->rlink != NULL) { new->rlink->llink = new; }
}
}
listNode* searchNode(linkedlist_h* DL, char* data) {
listNode* temp=DL->head;
while(temp != NULL) {
if(strcmp(temp->data,data) == 0) { return temp; }
else { temp = temp->rlink; }
}
return temp;
}
void deleteNode(linkedlist_h* DL, listNode* dNode) {
if((DL->head == NULL || dNode == NULL)) { return; }
else if(DL->head == dNode) {
dNode->rlink->llink = NULL;
DL->head = dNode->rlink;
free(dNode);
}
else {
dNode->llink->rlink = dNode->rlink;
dNode->rlink->llink = dNode->llink;
free(dNode);
}
}
This post is licensed under CC BY 4.0 by the author.