yeolyi.com성열의 컴퓨터공학

연결 리스트

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

배열은 값이 이어진 주소에 붙어 있어야 해서, 맨 앞에 끼워 넣으면 값을 모두 밀어야 했습니다. 값을 밀지 않고 끼워 넣을 수 있는 자료구조는 없을까요?

노드와 포인터

배열이 값을 미는 까닭은 순서를 주소로 정하기 때문입니다. 인덱스 3의 값은 반드시 시작 주소 + 3에 있어야 하니, 앞에 하나 끼우면 뒤의 값이 모두 자리를 옮깁니다.

순서를 주소 대신 값 옆에 적어 두면 어떨까요? 값마다 다음 값의 주소를 적어 두면, 쪽지마다 다음 쪽지 위치가 적힌 보물찾기처럼 값이 메모리 아무 데나 흩어져 있어도 순서대로 따라갈 수 있습니다. 끼워 넣을 때도 값은 그대로 두고 적어 둔 주소만 고치면 됩니다.

값 하나와 다음 값의 주소를 한 묶음으로 노드(node)라 합니다. 이 주소처럼 다른 데이터가 있는 주소를 담은 값을 포인터(pointer)라 하고, 노드를 포인터로 줄줄이 이은 것을 연결 리스트(linked list)라 합니다. 첫 노드의 주소는 따로 기억해 두고, 마지막 노드의 포인터에는 끝이라는 표시를 둡니다.

07
152
2
3🍌
4→19
5
613
7
8🍓
9끝
10
1199
125
13
14🍎
15→3
16
17
18
19🍇
20→8
21
22
23
따라가며 읽은 순서
처음 14????

처음 노드의 주소는 14번입니다.

위 숫자는 주소입니다. 노드마다 이웃한 두 칸에 값과 포인터(→ 다음 노드의 주소)가 있습니다.

끼워 넣기

새 노드는 빈 주소 아무 데나 만들면 됩니다. 앞 노드의 포인터가 새 노드를, 새 노드의 포인터가 원래 뒤 노드를 가리키게 고치면 끝입니다. 다른 노드는 옮기지 않고 포인터 두 개만 바꿉니다. 맨 앞에 넣을 때는 새 노드가 첫 노드가 됩니다. C로 써 봅시다. struct로 값과 포인터를 한 노드로 묶고, malloc으로 빈 주소에 새 노드를 만듭니다.

1#include <stdio.h>
2#include <stdlib.h>
3
4struct Node {
5 int value;
6 struct Node *next;
7};
8
9// 맨 앞에 새 노드 넣기
10struct Node *push(struct Node *head,
11 int value) {
12 struct Node *node =
13 malloc(sizeof(struct Node));
14 node->value = value;
15 node->next = head;
16 return node;
17}
18
19int main(void) {
20 struct Node *head = NULL;
21 head = push(head, 30);
22 head = push(head, 20);
23 head = push(head, 10);
24
25 // 처음부터 따라가며 읽기
26 struct Node *p = head;
27 while (p != NULL) {
28 printf("%d\n", p->value);
29 p = p->next;
30 }
31 return 0;
32}

변수 없음
출력 없음

대신 노드의 주소를 계산으로 알 수 없으니, 인덱스 3의 값을 보려면 처음 노드부터 포인터를 세 번 따라가야 합니다.

몇 칸을 건드릴까

할 일
위치 (인덱스) 2
배열
10100
20101
30102
40103
50104
105
106
107
연결 리스트
10231204
20217231
30240217
40209240
50끝209

읽기(위치 4), 넣기(위치 0), 넣기(맨 끝 다음)를 차례로 실행해 봅시다.

연결 리스트도 넣을 자리의 앞 노드까지 찾아가는 데에는 시간이 걸립니다.

걸리는 시간

파이썬의 collections.deque는 내부적으로 연결 리스트로 구현되어 있습니다(노드 하나에 값을 여러 개 담습니다). 배열 글과 같은 코드를 deque로 돌려 봅시다.

하나씩 다 읽기
1from collections import deque
2d = deque([0] * 100_000)
3for i in range(len(d)):
4 x = d[i]

실행을 눌러 봅시다.

맨 앞에 넣기
1from collections import deque
2d = deque([0] * 100_000)
3for _ in range(1000):
4 d.appendleft(0)

실행을 눌러 봅시다.

배열과 반대로 하나씩 다 읽기는 오래 걸리고, 맨 앞에 넣기는 금방 끝납니다. d[i]를 읽을 때마다 노드를 따라가야 하기 때문입니다. 시간 복잡도로 쓰면 배열은 읽기가 O(1), 맨 앞에 넣기가 O(n)이고 연결 리스트는 그 반대입니다. 그래서 맨 앞에서 넣고 빼는 일이 잦으면 연결 리스트가, 아무 위치나 자주 읽으면 배열이 유리합니다. 배열은 값이 붙어 있어 공간적 지역성 덕도 봅니다.

도전 문제

노드 1000개짜리 연결 리스트가 있습니다. 노드마다 다음 노드의 주소만 적혀 있고, 첫 노드와 마지막 노드의 주소는 따로 기억해 둡니다. 그래서 맨 끝에 값을 하나 넣을 때는 포인터를 한 번도 따라가지 않습니다. 맨 끝 노드 하나를 빼고 기억해 둔 마지막 노드 주소도 고치려면, 포인터를 적어도 몇 번 따라가야 할까요? 첫 노드에서 한 번 따라가면 인덱스 1 노드에 닿습니다. 숫자로 답하세요.