[자료구조] Linked List (연결 리스트) (feat. C 언어)

[자료구조] Linked List (연결 리스트) (feat. C 언어)

2023. 7. 19. 23:32ㆍCS/자료구조

정의

연결 리스트(Linked List)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장한다. 노드의 포인터는 다음이나 이전의 노드와의 연결을 담당한다. 연결 리스트의 종류로는 단방향 연결 리스트(Singly Linked List), 양방향 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linkde List) 등이 있다.

일반적으로 연결 리스트는 헤드라는 더미 노드를 가지고 있다. 헤드는 데이터 값을 가지지 않고 연결 리스트의 처음을 담당한다. 연결 리스트의 마지막 위치(테일)에 있는 노드의 포인터는 null을 가리킨다.

연결 리스트는 자료의 추가, 삽입 및 삭제 연산이 배열보다 빠르다는 장점이 있으며 탐색 연산은 배열보다 시간이 걸린다는 단점도 갖는다. 데이터의 삽입 및 삭제 연산 시에 해당되는 노드만 처리해 주면 되기 때문에 낭비되는 메모리가 거의 없다고 볼 수 있다.

특징

선형 구조
단방향 연결 리스트, 양방향 연결 리스트, 원형 연결 리스트 등이 존재
자료의 추가, 삽입 및 삭제 연산은 앞, 뒤 노드의 주소만 알면 쉽다는 장점이 있음
자료의 탐색 연산은 연결 리스트의 헤드 부터 테일까지 탐색해야 하기 때문에 시간이 걸리는 단점이 있음
배열과 달리 데이터의 삽입과 삭제 연산 시 그 때마다 처리해 주기 때문에 메모리 낭비가 거의 없음

연산

가장 단순한 연결 리스트인 단방향 연결 리스트를 예시로 연산 및 구현을 한다.

push_front 연산 : 헤드 쪽으로 노드 추가 시 헤드의 포인터는 추가되는 노드의 주소를 가리키고 추가되는 노드는 추가 전 헤드가 가리키던 노드의 주소를 가리키도록 한다.

pop_front 연산 : 헤드 쪽 노드 삭제 시 헤드의 포인터는 삭제되는 노드가 가리키는 포인터의 주소를 가리키고 삭제되는 노드는 free 함수를 사용해서 메모리를 해제한다.

push_back 연산 : 테일 쪽으로 노드 추가 시 헤드에서부터 테일에 해당하는 노드에 도착할 때 까지 각 노드의 포인터를 타고 가기 때문에 O(n) 만큼 걸리며 테일 노드에 도착했을 경우 테일 노드의 포인터는 추가되는 노드의 주소를 가리키며 추가되는 노드의 포인터는 null값을 가지게 된다. 그리고 추가되는 노드가 새로운 테일 노드가 된다.

pop_back : 테일 쪽 노드 삭제 시 헤드에서부터 테일에 해당하는 노드에 도착할 때 까지 각 노드의 포인터를 타고 가기 때문에 O(n) 만큼 걸리며 테일 노드에 도착했을 경우 테일 노드를 가리키는 노드의 포인터는 null값을 가지며 그 자신이 테일 노드로 변경된다. 삭제되는 노드는 free 함수를 사용해서 메모리를 해제한다.

구현

init_singlylist 함수 : 단방향 연결 리스트 초기화

1
2
3
4
5
6
7
8

void init_singlylist(struct Singlylist* list) // singly linkedlist 이니셜라이징, head라는 key값이 없는 더미노드를 하나 생성한다.(head는 총 노드에 포함되지 않는다.)
{
    struct Node_singlylist* head = (struct Node_singlylist*)malloc(sizeof(struct Node_singlylist));
    head->next = NULL;
    list->head = head;
    list->tail = NULL;
    list->count = 0;
}
Colored by Color Scripter

cs

push_front 함수 : 헤드쪽 데이터 추가

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void push_front(struct Singlylist* list, int item) // item을 리스트 head부분부터 넣어주는 함수, head의 다음 노드를 새로 들어가는 노드로 변경
{
    struct Node_singlylist* node = (struct Node_singlylist*)malloc(sizeof(struct Node_singlylist));
 
    if (list->count == 0) // list가 비어있는 경우
    {
        list->tail = node;
    }
 
    node->next = list->head->next; 
    node->item = item;
    list->head->next = node;
    list->count += 1;
}
 
Colored by Color Scripter

cs

pop_front 함수 : 헤드쪽 데이터 삭제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int pop_front(struct Singlylist* list) // item을 리스트 head부분부터 제거하는 함수, head의 다음 노드를 제거되는 노드의 다음 노드로 변경
{
    if (list->count == 0) // list가 비어있는 경우
    {
        printf("남은 itme가 없습니다.\n");
        return 0;
    }
 
    struct Node_singlylist* node = list->head->next;
    int item = node->item;
    list->head->next = node->next;
    list->count -= 1;
    free(node);
    return item;
}
Colored by Color Scripter

cs

push_back 함수 : 테일쪽 데이터 추가

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void push_back(struct Singlylist* list, int item) // item을 리스트 tail부분부터 넣어주는 함수, list의 tail을 찾기 위해 head부분부터 탐색
{
    struct Node_singlylist* cur = list->head->next;
    struct Node_singlylist* node = (struct Node_singlylist*)malloc(sizeof(struct Node_singlylist));
 
    if (list->count == 0) // list가 비어있는 경우
    {
        list->head->next = node;
    }
 
    else
    {
        while (cur->next != NULL) // cur이 tail의 위치에 도달할 때 까지
        {
            cur = cur->next;
        }
        cur->next = node; // cur==tail이 되고 cur->next를 새로 생성된 node의 주소로 변경
    }
 
    node->next = NULL;
    node->item = item;
    list->tail = node;
    list->count += 1;
}
Colored by Color Scripter

cs

pop_back 함수 : 테일쪽 데이터 삭제

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

int pop_back(struct Singlylist* list) // item을 리스트 tail부분부터 제거하는 함수, list의 tail을 찾기 위해 head부분부터 탐색
{
    struct Node_singlylist* before = list->head;
    struct Node_singlylist* after = list->head->next;
 
    if (list->count == 0) // list가 비어있는 경우
    {
        printf("남은 item이 없습니다.\n");
        return 0;
    }
 
    else
    {
        while (after->next != NULL) // after가 tail에 도달할 때 까지
        {
            before = before->next;
            after = after->next;
        }
        
        // after가 tail이 된 후 after에 위치한 item값 리턴 후 제거
 
        int item = after->item;
        before->next = NULL;
        list->count -= 1;
        free(after);
        return item;
    }
}
Colored by Color Scripter

cs

search 함수 : 원하는 data를 갖고 있는 노드 탐색

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

void search(struct Singlylist* list, int item) // list에 존재하는 item 탐색 함수
{
    struct Node_singlylist* cur = list->head;
 
    if (list->count == 0) // list가 비어있는 경우
    {
        printf("남은item이 없습니다.\n");
        return 0;
    }
 
    else
    {
        while (cur->next != NULL) // cur이 tail에 도달할 때 까지
        {
            cur = cur->next;
            if (cur->item == item) // cur이 찾는 key값을 가진 node에 도달했을 경우 while문 탈출
            {
                printf("찾으시는 item %d list에 들어있습니다.\n", item);
                break;
            }
        }
 
        // list에 찾고자 하는 item이 없는 경우
        printf("찾으시는 item %d list에 들어있지 않습니다.\n", item);
    }
}
Colored by Color Scripter

cs

전체 구조

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

struct Node_singlylist {
 
    int item;
    struct Node_singlylist* next;
};
 
 
struct Singlylist {
 
    struct Node_singlylist* head;
    struct Node_singlylist* tail;
    int count;
};
 
 
void init_singlylist(struct Singlylist* list);
void push_front(struct Singlylist* list, int item);
int pop_front(struct Singlylist* list);
void push_back(struct Singlylist* list, int item);
int pop_back(struct Singlylist* list);
void search(struct Singlylist* list, int item)
 
 
void init_singlylist(struct Singlylist* list) // singly linkedlist 이니셜라이징, head라는 key값이 없는 더미노드를 하나 생성한다.(head는 총 노드에 포함되지 않는다.)
{
    struct Node_singlylist* head = (struct Node_singlylist*)malloc(sizeof(struct Node_singlylist));
    head->next = NULL;
    list->head = head;
    list->tail = NULL;
    list->count = 0;
}
 
void push_front(struct Singlylist* list, int item) // item을 리스트 head부분부터 넣어주는 함수, head의 다음 노드를 새로 들어가는 노드로 변경
{
    struct Node_singlylist* node = (struct Node_singlylist*)malloc(sizeof(struct Node_singlylist));
 
    if (list->count == 0) // list가 비어있는 경우
    {
        list->tail = node;
    }
 
    node->next = list->head->next; 
    node->item = item;
    list->head->next = node;
    list->count += 1;
}
 
int pop_front(struct Singlylist* list) // item을 리스트 head부분부터 제거하는 함수, head의 다음 노드를 제거되는 노드의 다음 노드로 변경
{
    if (list->count == 0) // list가 비어있는 경우
    {
        printf("남은 itme가 없습니다.\n");
        return 0;
    }
 
    struct Node_singlylist* node = list->head->next;
    int item = node->item;
    list->head->next = node->next;
    list->count -= 1;
    free(node);
    return item;
}
 
void push_back(struct Singlylist* list, int item) // item을 리스트 tail부분부터 넣어주는 함수, list의 tail을 찾기 위해 head부분부터 탐색
{
    struct Node_singlylist* cur = list->head->next;
    struct Node_singlylist* node = (struct Node_singlylist*)malloc(sizeof(struct Node_singlylist));
 
    if (list->count == 0) // list가 비어있는 경우
    {
        list->head->next = node;
    }
 
    else
    {
        while (cur->next != NULL) // cur이 tail의 위치에 도달할 때 까지
        {
            cur = cur->next;
        }
        cur->next = node; // cur==tail이 되고 cur->next를 새로 생성된 node의 주소로 변경
    }
 
    node->next = NULL;
    node->item = item;
    list->tail = node;
    list->count += 1;
}
 
int pop_back(struct Singlylist* list) // item을 리스트 tail부분부터 제거하는 함수, list의 tail을 찾기 위해 head부분부터 탐색
{
    struct Node_singlylist* before = list->head;
    struct Node_singlylist* after = list->head->next;
 
    if (list->count == 0) // list가 비어있는 경우
    {
        printf("남은 item이 없습니다.\n");
        return 0;
    }
 
    else
    {
        while (after->next != NULL) // after가 tail에 도달할 때 까지
        {
            before = before->next;
            after = after->next;
        }
        
        // after가 tail이 된 후 after에 위치한 item값 리턴 후 제거
 
        int item = after->item;
        before->next = NULL;
        list->count -= 1;
        free(after);
        return item;
    }
}
 
void search(struct Singlylist* list, int item) // list에 존재하는 item 탐색 함수
{
    struct Node_singlylist* cur = list->head;
 
    if (list->count == 0) // list가 비어있는 경우
    {
        printf("남은item이 없습니다.\n");
        return 0;
    }
 
    else
    {
        while (cur->next != NULL) // cur이 tail에 도달할 때 까지
        {
            cur = cur->next;
            if (cur->item == item) // cur이 찾는 key값을 가진 node에 도달했을 경우 while문 탈출
            {
                printf("찾으시는 item %d list에 들어있습니다.\n", item);
                break;
            }
        }
 
        // list에 찾고자 하는 item이 없는 경우
        printf("찾으시는 item %d list에 들어있지 않습니다.\n", item);
    }
}
Colored by Color Scripter

cs

'CS > 자료구조' 카테고리의 다른 글

[자료구조] Hash Table (해시 테이블) (0)	2023.07.24
[자료구조] 배열(Array) vs 연결 리스트(Linked List) (0)	2023.07.20
[자료구조] Queue - Josephus problem (feat. C 언어) (0)	2023.07.19
[자료구조] Queue (feat. C 언어) (0)	2023.07.19
[자료구조] Stack (feat. C 언어) (0)	2023.07.19

생각 정리 ISFJ

생각 정리 ISFJ

태그

최근글

댓글

공지사항

아카이브

'CS > 자료구조' 카테고리의 다른 글

관련글

티스토리툴바