왜 배열만으로는 부족한가

06편에서 배열은 인덱스로 즉시 접근할 수 있지만, 중간에 원소를 삽입·삭제할 때는 뒤 원소를 전부 이동해야 해서 $O(n)$이 든다는 것을 확인했다. 이 이동 비용이 생기는 근본 원인은 배열이 메모리에서 반드시 연속된 자리를 차지해야 하기 때문이다. 연결리스트(linked list)는 이 제약을 없앤다. 각 원소를 메모리 어디에나 흩어져 있게 두고, 대신 “다음 원소가 어디에 있는지”를 가리키는 링크(포인터)로 원소들을 실처럼 꿰어 연결한다. 04편(연결 구조를 읽기 위한 포인터 감각)에서 잡은 참조·노드·링크의 직관을 여기서 실제 자료구조로 완성한다.

쉽게 말하면: 배열이 “번호표를 붙여 한 줄로 세워 놓은 자리”라면, 연결리스트는 “각자 다음 사람이 누군지 손에 쪽지를 들고 있는, 자리는 흩어져 있어도 순서는 유지되는 줄”이다.

노드와 단순 연결리스트의 구조

단순 연결리스트(singly linked list)를 이루는 기본 단위는 노드(node)다. 노드 하나는 두 부분으로 구성된다.

• 데이터 필드(data field): 실제로 저장하려는 값
• 링크 필드(link field, next 포인터): 다음 노드의 주소를 가리키는 포인터. 마지막 노드의 링크 필드는 “더 이상 다음이 없다”는 뜻으로 NULL을 가리킨다.

C에서는 구조체(struct)로 노드를 표현한다.

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;           // 데이터 필드
    struct Node *next;  // 링크 필드(다음 노드를 가리키는 포인터)
} Node;

노드 4개가 10 -> 20 -> 30 -> 40 -> NULL 순서로 연결된 리스트를 그림으로 보면 다음과 같다.

리스트 전체를 대표하는 것은 head 포인터 하나뿐이다. head가 첫 번째 노드를 가리키고 있고, 그 노드가 다음 노드를 가리키고, 이 연결을 따라가면 마지막 노드의 NULL에 도달할 때까지 전체 리스트를 훑을 수 있다. 배열과 달리 “몇 번째 노드가 정확히 몇 번지에 있는가”는 미리 계산할 수 없다. 오직 head부터 링크를 따라가야만 $k$번째 노드에 도달할 수 있다는 점이 배열과의 가장 큰 차이다.

자주 틀리는 점: 연결리스트에서 “3번째 원소에 접근하라”는 문제를 배열처럼 $O(1)$로 계산할 수 있다고 착각하면 안 된다. 연결리스트의 임의 위치 접근은 head부터 링크를 하나씩 따라가야 하므로 $O(n)$이다.

리스트 순회(traversal)

리스트의 모든 노드를 방문하며 값을 출력하는 순회 연산을 살펴보자.

void printList(Node *head) {
    Node *cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;  // 다음 노드로 이동
    }
    printf("\n");
}

10 -> 20 -> 30 -> 40 -> NULL 리스트에 대해 이 함수가 실행되는 과정을 cur 포인터의 변화로 추적하면 다음과 같다.

10 20 30 40

노드가 $n$개면 while 문이 $n$번 돌고 종료 확인까지 1번 더 하므로, 순회의 시간 복잡도는 $O(n)$이다.

맨 앞 삽입 — 포인터 두 줄이면 끝

맨 앞에 새 노드를 넣는 연산은 연결리스트가 배열보다 압도적으로 유리한 지점이다. 기존 원소를 하나도 옮기지 않고 포인터만 바꾸면 된다. 5를 맨 앞에 삽입하는 과정을 추적해 보자(기존 리스트: 10 -> 20 -> 30 -> NULL).

Node* insertFront(Node *head, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = head;  // 새 노드가 기존 head를 가리킴
    return newNode;        // 새 노드가 새로운 head가 됨
}

이 연산은 리스트 크기와 무관하게 포인터 대입 두 번(newNode->next = head, head = newNode)이면 끝나므로 시간 복잡도는 $O(1)$이다. 배열의 맨 앞 삽입이 원소를 전부 밀어야 해서 $O(n)$인 것과 정반대다.

중간 삽입 — 두 노드 사이 끼워 넣기

10 -> 20 -> 30 -> NULL에서 20과 30 사이에 25를 삽입하는 과정을 추적해 보자. 핵심은 삽입할 위치 바로 앞 노드(여기서는 20 노드, prev라고 부른다)를 먼저 찾는 것이다.

void insertAfter(Node *prev, int value) {
    if (prev == NULL) return;
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = prev->next;  // 순서 중요: 먼저 뒤쪽 연결부터 잇는다
    prev->next = newNode;        // 그다음 앞쪽 연결을 바꾼다
}

자주 틀리는 점: prev->next = newNode를 먼저 실행하고 newNode->next = prev->next를 나중에 실행하면, 이미 prev->next가 newNode 자신을 가리키게 된 뒤라서 newNode->next도 자기 자신을 가리키게 되어 리스트가 끊어진다. 반드시 새 노드의 링크를 먼저 연결한 다음 앞 노드의 링크를 바꿔야 순서가 안전하다.

노드 자체를 끼워 넣는 것은 포인터 대입 두 번, $O(1)$이지만, “20 노드를 찾는” 탐색 과정이 head부터 링크를 따라가야 하므로 $O(n)$이 걸린다. 그래서 전체 삽입 연산은 **삽입 위치를 이미 포인터로 알고 있다면 $O(1)$, 위치를 값으로 찾아야 한다면 $O(n)$**이라고 구분해서 답해야 한다.

삭제 — 앞 노드가 다음다음을 가리키게

5 -> 10 -> 20 -> 30 -> NULL에서 20을 삭제하는 과정을 추적해 보자. 여기서도 삭제할 노드의 바로 앞 노드(10 노드, prev)를 먼저 찾아야 한다.

void deleteAfter(Node *prev) {
    if (prev == NULL || prev->next == NULL) return;
    Node *target = prev->next;
    prev->next = target->next;  // 삭제 대상을 건너뛰고 바로 연결
    free(target);
}

배열의 삭제가 뒤 원소를 전부 당겨야 했던 것과 달리, 연결리스트는 앞 노드의 링크 하나만 바꾸면 된다. 노드를 찾는 탐색까지 포함하면 $O(n)$, 삭제할 노드의 바로 앞 노드를 이미 알고 있다면 삭제 자체는 $O(1)$이다.

자주 틀리는 점: free(target)을 prev->next = target->next보다 먼저 실행하면, 이미 해제된 메모리의 next 값을 읽으려다 오류가 나거나 예측 불가능한 값을 참조하게 된다. 링크를 먼저 바꾸고 메모리를 나중에 해제하는 순서를 지켜야 한다.

배열과 연결리스트 비교

06편의 표에 연결리스트 열을 추가해 나란히 비교하면 다음과 같다.

이 표에서 눈여겨볼 점은 “값으로 위치를 찾는” 경우에는 두 구조 모두 탐색에 $O(n)$이 걸린다는 것이다. 연결리스트가 유리한 지점은 삽입·삭제 위치를 이미 포인터로 알고 있을 때이지, 무조건 배열보다 빠른 것이 아니다. 이 구분을 놓치면 “연결리스트는 삽입이 항상 $O(1)$이다”라는 틀린 결론에 빠지기 쉽다.

연결리스트의 응용 감각

단순 연결리스트는 그 자체로도 쓰이지만, 이후 편들의 기초가 된다. 스택과 큐(09편)는 연결리스트로 구현할 수 있고(맨 앞 삽입·삭제가 $O(1)$이라는 성질을 그대로 활용한다), 이진트리(12편)의 노드도 데이터 필드에 링크 필드가 두 개(왼쪽·오른쪽 자식) 있는 구조로 확장된 것이라고 볼 수 있다. 08편에서는 링크 필드를 하나 더 추가한 이중 연결리스트와, 마지막 노드가 다시 첫 노드를 가리키는 원형 연결리스트를 다룬다.

자주 틀리는 점

• 연결리스트의 임의 위치 접근을 배열처럼 $O(1)$로 착각하는 오류: 연결리스트는 인덱스 계산이 불가능하고, head부터 링크를 따라가야 하므로 $O(n)$이다.
• 포인터 대입 순서를 바꿔 리스트를 끊어 먹는 오류: 삽입 시 새 노드의 링크를 먼저 연결하고, 삭제 시 앞 노드의 링크를 먼저 바꾼 뒤 메모리를 해제해야 한다.
• “연결리스트는 삽입이 항상 $O(1)$이다”라고 단정하는 오류: 삽입 위치를 값으로 찾아야 한다면 탐색에 $O(n)$이 걸린다. 포인터를 이미 쥐고 있을 때만 삽입 자체가 $O(1)$이다.

핵심 정리

• 단순 연결리스트의 노드는 데이터 필드와 다음 노드를 가리키는 링크 필드로 구성되며, head 포인터 하나로 전체 리스트를 대표한다.
• 순회·값으로 위치 찾기는 $O(n)$이고, 삽입·삭제 위치를 이미 포인터로 알고 있다면 그 연산 자체는 $O(1)$이다.
• 삽입은 “새 노드의 링크를 먼저 연결 → 앞 노드의 링크를 바꾼다” 순서로, 삭제는 “앞 노드의 링크를 바꾼다 → 메모리 해제” 순서로 해야 리스트가 끊어지지 않는다.
• 연결리스트는 맨 앞·중간 삽입·삭제가 빠른 대신 인덱스 접근이 느리고 링크를 저장할 추가 메모리가 필요하다는 트레이드오프를 가진다.

마무리 복습

참고 자료

• 국가평생교육진흥원 과목별 평가영역  — 자료구조 과목의 범위와 평가영역을 확인할 수 있는 공식 안내.
• MDN JavaScript reference  — 참조(reference) 기반 자료구조의 감각을 확인할 수 있는 참고 자료.