연결 리스트

연결 리스트(linked list)는 값을 담은 노드를, 다음 노드가 있는 자리를 적은 포인터로 이어 놓은 선형 구조입니다. 배열은 값을 이어진 칸에 두어 번호로 곧바로 찾지만, 가운데에 값을 넣거나 빼면 뒤의 값을 모두 한 칸씩 옮겨야 합니다. 연결 리스트는 노드가 메모리 어디에 있어도 되고, 넣고 뺄 때 화살표 한두 개만 바꿔 끼웁니다. 아래 그림은 흩어진 노드들이 화살표로 한 줄이 되고, 화살표가 끊기고 다시 이어지며 노드가 끼어들고 빠지는 모습을 보입니다.

1노드와 포인터 — 화살표를 따라 읽는다

연결 리스트의 한 칸을 노드(node)라 합니다. 노드는 값 칸과 다음 칸으로 이뤄집니다. 다음 칸에는 다음 노드가 메모리 어디에 있는지가 담기고, 이렇게 자리를 가리키는 값을 포인터(pointer)라 합니다. 마지막 노드의 다음 칸은 아무것도 가리키지 않습니다. C에서는 NULL, Python에서는 None으로 적습니다.

첫 노드를 가리키는 포인터를 head라 부르고, 값은 늘 head에서 출발해 화살표를 따라 읽습니다. 그래서 세 번째 값을 보려면 화살표를 두 번 따라가야 합니다.

2끼워 넣기와 빼기 — 화살표를 바꿔 끼운다

노드 a 뒤에 새 노드 n을 끼워 넣을 때는 두 줄을 이 차례로 씁니다.

1. n의 다음 칸에 a의 다음 칸을 옮겨 적습니다. 이제 n도 a 뒤의 노드를 가리킵니다.
2. a의 다음 칸이 n을 가리키게 합니다.

차례를 바꾸면 a의 다음 칸이 이미 n이라, n의 다음 칸에 옮겨 적는 값이 n 자신이 됩니다. a 뒤에 있던 노드들에는 다시 닿을 수 없게 됩니다.

빼기는 한 줄입니다. 빼려는 노드 바로 앞 노드의 다음 칸이 빼려는 노드를 건너 그다음 노드를 가리키게 합니다. 아무 화살표도 받지 않는 노드는 리스트에서 빠집니다.

3배열과 견주기

다음 칸에 더해 앞 노드를 가리키는 칸까지 두면 이중 연결 리스트(doubly linked list)입니다. 마지막 노드의 다음 칸이 첫 노드를 가리키면 원형 연결 리스트(circular linked list)이고, 노드마다 다음은 하나라 여전히 선형입니다.

예제

C — 구조체 노드 사이에 끼워 넣기

노드를 구조체(struct)로 만들고, 10 → 30 → 40의 10과 30 사이에 20을 끼워 넣습니다. 구조체와 포인터 문법은 32단원에서 자세히 배웁니다. 여기서는 셋만 읽습니다 — &b는 b가 있는 자리, p->data는 p가 가리키는 노드의 값 칸, NULL은 아무것도 가리키지 않는 포인터입니다.

#include <stdio.h>
struct node {
    int data;
    struct node *next;
};
struct node c = {40, NULL};
struct node b = {30, &c};
struct node a = {10, &b};
struct node n = {20, NULL}, *p;
int main(void) {
    n.next = a.next;
    a.next = &n;
    for (p = &a; p; p = p->next)
        printf("%d\n", p->data);
}

10
20
30
40

6~8번 줄이 a → b → c를 만듭니다. b가 c의 자리를 적어야 해서 뒤 노드부터 선언했습니다. 11·12번 줄이 끼워 넣기 두 줄입니다. n이 먼저 30을 가리키고, 그다음 a가 n을 가리킵니다. 13번 줄은 p가 NULL이 되어 조건이 거짓이 될 때까지 화살표를 따라갑니다.

Python — 클래스 노드에서 빼기

Python은 클래스(class)로 노드를 만듭니다. 클래스는 34단원에서 배웁니다. C 예제가 만든 10 → 20 → 30 → 40에서 30을 뺍니다. 노드 이름도 C 예제와 같습니다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a = Node(10)
n = Node(20)
b = Node(30)
c = Node(40)
a.next = n
n.next = b
b.next = c
n.next = n.next.next
p = a
while p is not None:
    print(p.data)
    p = p.next

10
20
40

12번 줄이 빼기입니다. 20의 다음 칸이 30을 건너 40을 가리켜, 30은 아무 화살표도 받지 않습니다. 14~16번 줄은 C 예제의 for 문처럼 None에 닿을 때까지 따라 읽습니다.

시험 포인트

• 필기: 연결 리스트는 노드(값 + 다음 노드를 가리키는 포인터)를 이은 선형 구조입니다. 배열과의 차이를 묻는 보기가 자주 나옵니다. 가운데에 넣고 빼기는 포인터만 바꾸는 연결 리스트가 빠르고, k번째 값 찾기는 번호로 곧바로 가는 배열이 빠릅니다. 포인터 칸만큼 자리를 더 쓰는 것도 차이입니다. 이중 연결 리스트는 앞을 가리키는 포인터를, 원형 연결 리스트는 끝에서 처음으로 가는 포인터를 더한 것입니다.
• 실기: C·Python 연결 리스트 코드의 출력을 그대로 씁니다. 끼워 넣기는 '새 노드의 다음 칸 먼저, 앞 노드의 다음 칸 나중'이고, 빼기는 앞 노드의 다음 칸이 한 노드를 건너뛰는 한 줄입니다. 이름은 연결 리스트(Linked List)·노드(Node)·포인터(Pointer)로 씁니다.

확인 문제

1. 배열보다 연결 리스트가 알맞은 경우를 고르세요.

• ① 정해진 100개의 값을 번호로 자주 꺼내 읽는다.
• ② 값마다 차지하는 자리를 가장 적게 쓰고 싶다.
• ③ 대기 줄 가운데에 손님을 끼워 넣고 빼는 일이 잦고, 손님 수를 미리 알 수 없다.
• ④ 맨 끝 값을 번호 하나로 곧바로 꺼내야 한다.

2. 다음 (가)~(다)에 맞는 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 값 하나와, 다음 것이 어디 있는지 적은 칸을 한 묶음으로 둔 단위입니다.
• (나) 그 묶음 안에 들어 있는, 다음 묶음이 놓인 메모리 위치를 담은 값입니다.
• (다) 그런 묶음들을 줄줄이 이어, 가운데에 하나를 넣어도 다른 값들이 자리를 옮기지 않게 한 구조입니다.

3. Python 예제의 12번 줄을 a.next = a.next.next로 바꿨습니다. 출력을 그대로 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a = Node(10)
n = Node(20)
b = Node(30)
c = Node(40)
a.next = n
n.next = b
b.next = c
a.next = a.next.next
p = a
while p is not None:
    print(p.data)
    p = p.next

10
30
40

4. C 예제의 11·12번 줄의 차례를 바꿔, a.next = &n;을 먼저 쓰고 n.next = a.next;를 나중에 썼습니다. 무슨 일이 생길까요?

• ① 출력이 10 20 30 40으로 같다.
• ② 10 다음에 20이 끝없이 찍힌다.
• ③ 10 30 40이 찍힌다.
• ④ 컴파일 오류가 난다.