단방향 연결 목록

배열의 조회·삽입·삭제와 시간 복잡도와 용량이 늘어나는 동적 배열 만들기에서 만든 배열 목록은 원소를 연속된 칸에 차례로 담습니다. 덕분에 i번째 원소는 위치를 계산해 바로 읽을 수 있습니다. 하지만 맨 앞에 값을 넣으려면 뒤의 원소를 모두 한 칸씩 밀어야 하고, 칸이 모자라면 더 큰 배열을 만들어 전부 복사해야 합니다. 원소들이 붙어 있어야 한다는 조건이 이런 비용을 만듭니다.

연결 목록(linked list)은 이 조건을 없앤 구조입니다. 원소마다 작은 객체를 하나씩 만들고, 각 객체가 다음 객체의 참조를 들고 있게 해서 원소들을 사슬처럼 잇습니다. 이 객체를 노드(node)라고 하고, 노드가 다음 노드 하나만 가리키는 연결 목록을 단방향 연결 목록(singly linked list)이라고 합니다. 이 글에서는 노드를 직접 이어 보고, 첫 노드에서 출발해 참조를 따라가는 조회와 끝 추가를 구현합니다. 그 과정에서 배열에서는 한 번에 끝나던 'i번째 원소 찾기'가 왜 비싸지는지도 확인합니다.

노드를 참조로 이어 붙이기

노드에는 두 가지가 들어 있습니다. 하나는 원소의 값이고, 다른 하나는 다음 노드를 가리키는 참조 next입니다. 다음 프로그램은 값 A, B, C를 담은 노드 세 개를 이어 붙인 뒤, 첫 노드부터 차례로 따라가며 값을 출력합니다.

public final class ThreeNodeWalk {
    public static void main(String[] args) {
        Node head = new Node("A", new Node("B", new Node("C", null)));

        int index = 0;
        for (Node current = head; current != null; current = current.next) {
            System.out.println(index + ": " + current.value);
            index++;
        }
    }

    private record Node(String value, Node next) {}
}

0: A
1: B
2: C

생성자의 인수는 생성자보다 먼저 계산되므로, 세 번째 줄에서는 next가 null인 C 노드가 가장 먼저 완성됩니다. 그 참조를 받아 B 노드가, 다시 B의 참조를 받아 A 노드가 완성됩니다. 변수 head에는 첫 노드 A의 참조만 들어갑니다. B와 C를 가리키는 변수는 따로 없지만, A의 next를 따라가면 B에, B의 next를 따라가면 C에 닿습니다. 이처럼 목록의 첫 노드를 가리키는 참조를 보통 head라고 부릅니다.

current.next처럼 괄호 없이 쓴 것은 레코드의 필드를 직접 읽는 코드입니다. 레코드의 필드는 private이지만, 이 레코드처럼 클래스 안에 중첩된 타입의 private 멤버는 바깥 클래스의 코드에서도 쓸 수 있습니다. 읽기 메서드 current.next()를 불러도 결과는 같습니다.

for 문은 지역 변수 current를 head로 초기화하고, 값을 출력할 때마다 current = current.next로 한 칸 옮깁니다. 반복마다 상태가 어떻게 바뀌는지 보면 다음과 같습니다.

세 번째 반복이 끝나면 C의 next인 null이 current에 들어가고, 조건 current != null이 거짓이 되어 반복이 끝납니다. 마지막 노드의 next를 null로 두는 것은 '다음 노드가 없다'는 표시이고, 순회는 이 표시를 보고 멈춥니다. 노드가 하나도 없는 빈 목록은 head 자체가 null인 상태입니다.

배열이라면 i번째 칸의 위치를 시작 위치와 인덱스로 계산해 곧장 찾아갑니다. 연결 목록의 노드는 힙의 서로 다른 곳에 따로 만들어지므로 이런 계산을 할 수 없습니다. 그래서 i번째 노드에 가려면 head에서 출발해 next를 정확히 i번 따라가야 합니다. 대신 노드들이 붙어 있을 필요가 없으니, 원소가 늘어나도 큰 배열을 새로 만들어 복사하는 일이 없습니다.

null을 지나 한 번 더 이동하면

배열은 length로 칸 수를 알려 주지만, 노드 사슬에는 길이를 알려 주는 곳이 없습니다. 각 노드는 자기 다음 노드만 알 뿐입니다. 그래서 사슬이 몇 칸인지 확인하지 않고 이동 횟수를 미리 정해 두면 문제가 생깁니다. 다음 프로그램은 노드가 두 개뿐인 사슬에서 next를 세 번 따라가려고 합니다.

public final class BrokenNodeTraversalFailure {
    public static void main(String[] args) {
        Node first = new Node("node", new Node("link", null));
        Node current = first;
        for (int i = 0; i <= 2; i++) {
            current = current.next;
        }
        System.out.println(current.value);
    }

    private record Node(String value, Node next) {}
}

Exception in thread "main" java.lang.NullPointerException: Cannot read field "next" because "<local2>" is null
	at BrokenNodeTraversalFailure.main(BrokenNodeTraversalFailure.java:6)

반복을 하나씩 따라가 보겠습니다. i가 0일 때 current는 첫 노드에서 두 번째 노드 link로 이동합니다. i가 1일 때는 link의 next인 null이 current에 들어갑니다. 변수에 null을 넣는 것 자체는 아무 문제가 없으므로 여기까지는 정상입니다. 문제는 i가 2일 때입니다. current.next를 계산하려면 current가 가리키는 객체의 필드를 읽어야 하는데, 가리키는 객체가 없으니 NullPointerException이 발생합니다. 예외가 main 밖으로 빠져나가 프로그램이 끝나므로 8번째 줄의 println은 실행되지 않습니다.

메시지의 Cannot read field "next"는 실패한 동작이 next 필드 읽기라는 뜻이고, 둘째 줄의 BrokenNodeTraversalFailure.java:6은 current = current.next;가 있는 6번째 줄을 가리킵니다. <local2>는 2번 지역 변수, 곧 current입니다. 0번은 args, 1번은 first가 차지합니다. null과 NullPointerException에서 본 것처럼 javac -g로 컴파일하면 "current" is null처럼 변수 이름이 나옵니다.

이 버그는 사슬이 실제로 몇 칸인지 확인하지 않고 '세 번 이동할 수 있다'고 가정한 데서 생겼습니다. 해결 방법은 상황에 따라 두 가지입니다. 끝까지 훑을 때는 앞의 ThreeNodeWalk처럼 current != null을 반복 조건으로 삼아, 다음 노드가 없으면 멈추게 합니다. 특정 위치로 갈 때는 원소 수를 따로 세어 두었다가, 이동하기 전에 그 위치가 원소 수보다 작은지 확인합니다. 다음 절에서 만드는 목록 클래스는 두 방법을 모두 씁니다.

head와 size를 가진 목록 클래스

노드를 main에서 직접 이어 붙이면 사슬을 쓰는 모든 코드가 next를 다뤄야 하고, 앞의 예처럼 실수하기도 쉽습니다. 그래서 노드 사슬은 클래스 안에 감추고, 바깥에는 add와 get 같은 목록 연산만 보여 줍니다. 다음 NodeChain은 첫 노드를 가리키는 head와 원소 수 size, 두 필드로 목록을 표현합니다. 빈 목록은 head가 null이고 size가 0인 상태입니다. 이번에는 add가 기존 노드의 next를 바꿔야 하므로, 노드를 레코드 대신 next를 다시 대입할 수 있는 일반 클래스로 만들었습니다.

public final class LinkedNodeWalk {
    public static void main(String[] args) {
        NodeChain chain = new NodeChain();
        chain.add("node");
        chain.add("next");
        chain.add("head");
        System.out.println(chain.get(1));
        System.out.println(chain);
    }

    private static final class NodeChain {
        private Node head;
        private int size;

        void add(String value) {
            Node added = new Node(value);
            if (head == null) head = added;
            else getNode(size - 1).next = added;
            size++;
        }

        String get(int index) {
            check(index);
            return getNode(index).value;
        }

        private Node getNode(int index) {
            Node current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            return current;
        }

        private void check(int index) {
            if (index < 0 || index >= size) throw new IndexOutOfBoundsException(index);
        }

        @Override
        public String toString() {
            StringBuilder out = new StringBuilder("[");
            for (Node current = head; current != null; current = current.next) {
                if (out.length() > 1) out.append(", ");
                out.append(current.value);
            }
            return out.append(']').toString();
        }
    }

    private static final class Node {
        String value;
        Node next;

        Node(String value) {
            this.value = value;
        }
    }
}

next
[node, next, head]

add는 새 노드를 만든 뒤 두 경우로 나눕니다. 목록이 비어 있으면(head == null) 새 노드가 곧 첫 노드이므로 head에 넣습니다. 그렇지 않으면 마지막 노드를 찾아 그 next에 새 노드를 연결합니다. 마지막 노드의 인덱스는 size - 1이므로 getNode(size - 1)로 찾습니다. size는 연결이 끝난 뒤에야 1 늘리는데, 이 순서가 왜 중요한지는 연습 문제 3에서 확인합니다.

getNode는 인덱스로 노드를 찾는 내부 도우미입니다. 지역 변수 current를 head로 초기화하고 next를 정확히 index번 따라갑니다. 이 메서드는 인덱스가 올바르다고 믿고 걷기만 하므로 private으로 감춰 두었습니다. 바깥에서 부르는 get은 먼저 check로 인덱스가 0 이상 size 미만인지 확인하고, 통과했을 때만 getNode를 부릅니다. 범위를 벗어난 인덱스는 사슬을 걷기 전에 IndexOutOfBoundsException으로 거부되므로, 앞 절처럼 null을 지나쳐 엉뚱한 곳에서 실패하는 일이 없습니다.

toString은 처음부터 끝까지 훑는 경우이므로 size 대신 current != null 조건으로 걷습니다. out은 [로 시작하므로 길이가 1보다 길다면 이미 원소를 하나 이상 붙였다는 뜻이고, 그때만 앞에 쉼표를 붙입니다. 이 조건을 current.next != null로 잘못 쓰면 마지막 노드에 닿기 전에 반복이 끝나 출력이 [node, next]가 되고, 빈 목록에서는 null의 next를 읽다가 NullPointerException이 납니다. 순회 조건은 '다음 노드가 있는가'가 아니라 '지금 노드가 있는가'여야 합니다.

출력의 첫 줄 next는 get(1)의 결과입니다. current가 첫 노드에서 next를 한 번 따라가 두 번째 노드에 닿았고, 그 노드의 값이 문자열 "next"입니다. 둘째 줄은 toString이 세 노드를 차례로 방문한 결과입니다. 이 예제의 값 "node", "next", "head"는 필드 이름과 같은 단어라서 헷갈리기 쉽습니다. 세 번째 노드에 담긴 문자열 "head"는 첫 노드를 가리키는 필드 head와 아무 관계가 없습니다.

더 깊이: 사슬이 고리로 이어지면

current != null이라는 종료 조건은 사슬의 끝이 null이라는 전제 위에 서 있습니다. 버그 때문에 마지막 노드의 next가 앞쪽 노드를 다시 가리키면 사슬은 고리(cycle)가 되고, 순회는 같은 노드들을 끝없이 돌게 됩니다. 노드 수를 세기만 하는 순회라면 예외 없이 영원히 돌고, toString처럼 문자열을 이어 붙이는 순회라면 문자열이 메모리를 다 쓸 때까지 커지다가 OutOfMemoryError로 끝납니다. 어느 쪽이든 오류 메시지가 고리를 직접 가리키지는 않으므로 원인을 찾기 어렵습니다.

이 목록처럼 size를 관리한다면 가장 간단한 진단은 방문한 노드 수를 세다가 size를 넘으면 구조가 망가졌다고 판단하는 것입니다. size를 믿을 수 없거나 아예 없을 때는 플로이드의 순환 탐지(Floyd's cycle detection)를 씁니다. 한 참조는 한 칸씩, 다른 참조는 두 칸씩 움직이면, 고리가 없을 때는 빠른 쪽이 먼저 null에 닿습니다. 고리가 있으면 빠른 쪽이 고리 안을 돌다가 느린 쪽을 따라잡아 두 참조가 같은 노드를 가리키게 됩니다. 이 방법은 참조 변수 두 개만으로, 즉 O(1)의 추가 메모리와 O(n) 시간으로 고리가 있는지 알려 줍니다.

head는 그대로 두고 current만 옮기기

getNode는 왜 굳이 지역 변수 current를 따로 만들까요? head를 직접 옮겨도 원하는 노드에는 도착할 것 같습니다. 다음은 그렇게 바꾼 getNode입니다. 나머지 코드와 main은 앞의 LinkedNodeWalk와 같습니다.

private Node getNode(int index) {
    for (int i = 0; i < index; i++) {
        head = head.next; // head를 직접 옮긴다
    }
    return head;
}

head
[head]

get(1)은 "next" 대신 "head"를 돌려주었고, 목록에는 원소가 하나만 남았습니다. 그런데 목록이 처음 망가진 시점은 get(1)이 아니라 그보다 앞선 세 번째 add입니다. add도 마지막 노드를 찾으려고 getNode를 부르기 때문입니다. 호출마다 head가 어디를 가리키는지 따라가 보겠습니다.

head가 앞으로 밀려날 때마다 그 앞의 노드는 어떤 변수도 가리키지 않게 됩니다. 단방향 연결에는 뒤로 돌아가는 참조가 없으므로 그 노드들을 다시 찾을 방법이 없고, 결국 가비지 컬렉터가 회수할 대상이 됩니다. 조회 메서드 하나가 목록의 앞부분을 영영 지워 버린 셈입니다. 게다가 size는 여전히 3이라서, 이어서 get(2)를 부르면 범위 검사는 통과한 뒤 사슬을 걷다가 NullPointerException이 납니다.

그래서 head는 목록이 살아 있는 동안 언제나 첫 노드를 가리키는 필드로 두고, 조회와 순회는 지역 변수 current로만 합니다. 아래 그림은 올바른 getNode(1)이 실행될 때의 상태입니다. current만 두 번째 노드로 한 칸 이동하고, head는 계속 첫 노드를 가리키며, size도 3 그대로입니다.

정리하면 인덱스 0의 노드는 head가 가리키는 노드이고, 인덱스 i의 노드는 head에서 next를 i번 따라간 노드입니다. 이 정의가 곧 다음 절의 비용 계산입니다.

조회와 끝 추가에 드는 시간

getNode(index)는 next를 정확히 index번 따라가므로 get(i)에 드는 시간은 i에 비례합니다. 첫 원소는 바로 읽지만 마지막 원소를 읽으려면 n−1번 이동해야 하므로, 최악의 경우는 O(n)입니다. 배열 목록의 get이 위치와 상관없이 O(1)인 것과 대조됩니다.

이 차이는 모든 원소를 인덱스로 차례로 읽을 때 크게 벌어집니다. for (int i = 0; i < size; i++) 안에서 get(i)를 부르면 호출마다 head에서 다시 출발하므로, 이동 횟수가 0 + 1 + … + (n−1) = n(n−1)/2번이 되어 O(n²)입니다. 같은 일을 toString처럼 current 하나로 걸으면 노드마다 한 번씩만 이동하면 됩니다. 목록 바깥의 코드도 이렇게 걸을 수 있게 해 주는 방법이 Iterable과 Iterator에서 배울 반복자입니다.

끝 추가도 마찬가지입니다. 이 구현은 마지막 노드를 기억하지 않으므로 add할 때마다 getNode(size - 1)로 처음부터 끝까지 걸어갑니다. 원소가 k−1개 있을 때 k번째 값을 추가하면 k−2번 이동하므로, 끝 추가 한 번이 O(n)입니다. 빈 목록에서 시작해 n개를 추가하면 이동 횟수는 0 + 0 + 1 + 2 + … + (n−2) = (n−1)(n−2)/2번이 되어 전체가 O(n²)입니다. 1,000개라면 998 × 999 / 2 = 498,501번입니다. getNode에 이동 횟수를 세는 변수를 넣고 실제로 1,000개를 추가해 보면 정확히 이 값이 나옵니다.

용량이 늘어나는 동적 배열 만들기에서 배열 목록의 끝 추가는 분할 상환 O(1)이었습니다. 가끔 전체를 복사하더라도 n번 추가하는 데 드는 일이 n에 비례했습니다. 그러니 마지막 노드를 기억하지 않는 연결 목록은 끝 추가에서 배열 목록보다 훨씬 느립니다. 원인은 마지막 노드의 위치를 모른다는 한 가지이므로, 해결책도 간단합니다.

꼬리를 기억하는 게시글 저장소

head처럼 마지막 노드를 가리키는 필드를 하나 더 두면 끝 추가에서 사슬을 걸을 필요가 없습니다. 이 필드를 꼬리(tail)라고 부릅니다. 다음은 이 장의 앞 글들에서 Entry[] 배열로 만들어 온 게시글 저장소를 head와 tail을 가진 노드 사슬로 바꾼 것입니다. main은 지금까지의 CLI와 같고 저장소 내부만 달라졌습니다.

public final class PostRepositoryCliCH144 {
    public static void main(String[] args) {
        PostRepository repository = new PostRepository();
        repository.add("node-chain", 38);
        repository.add("linear-walk", 47);
        repository.print();
        System.out.println("total=" + repository.totalViewCount());
    }

    private static final class PostRepository {
        private Node head;
        private Node tail;

        void add(String title, int viewCount) {
            if (title == null || title.isBlank()) throw new IllegalArgumentException("title");
            if (viewCount <= 0) throw new IllegalArgumentException("viewCount");
            Node added = new Node(new Entry(title, viewCount));
            if (head == null) head = added;
            else tail.next = added;
            tail = added;
        }

        int totalViewCount() {
            int total = 0;
            for (Node current = head; current != null; current = current.next) {
                total += current.entry.viewCount();
            }
            return total;
        }

        void print() {
            int index = 0;
            for (Node current = head; current != null; current = current.next) {
                System.out.println(index + ":" + current.entry.title() + "=" + current.entry.viewCount());
                index++;
            }
        }
    }

    private static final class Node {
        final Entry entry;
        Node next;

        Node(Entry entry) {
            this.entry = entry;
        }
    }

    private record Entry(String title, int viewCount) {}
}

0:node-chain=38
1:linear-walk=47
total=85

add는 입력을 검사한 뒤 새 노드를 만들고, 목록이 비어 있으면 head에, 아니면 지금 꼬리의 next에 연결합니다. 어느 경우든 새 노드가 마지막 노드가 되므로, 마지막 줄에서 tail을 새 노드로 옮깁니다. 사슬을 걷는 반복문이 없으니 원소가 몇 개든 끝 추가는 O(1)입니다. 대신 노드를 바꾸는 모든 메서드가 head와 tail이 언제나 첫 노드와 마지막 노드를 가리키도록 함께 관리해야 합니다. 예를 들어 tail = added;를 else 쪽에만 넣으면 첫 원소를 넣을 때 tail이 null로 남고, 두 번째 add에서 tail.next에 대입하다가 NullPointerException이 납니다.

print와 totalViewCount는 head부터 null까지 노드마다 한 번씩 방문하므로 각각 O(n)입니다. 출력 형식은 앞 글들의 배열 저장소와 똑같습니다. 저장소를 쓰는 쪽은 next나 head를 전혀 몰라도 되고, 그래서 내부 구조를 배열에서 노드 사슬로 바꿔도 main은 한 줄도 고칠 필요가 없었습니다. 이렇게 구현을 바꿔 끼우는 방법은 MyList 인터페이스로 목록 구현 바꾸기에서 인터페이스로 정리합니다.

배열 목록과 비교하면

지금까지 본 연산의 시간을 배열 목록과 나란히 놓으면 다음과 같습니다. 맨 앞 삽입과 위치 삽입은 다음 글에서 구현합니다.

표에서 연결 목록이 분명히 앞서는 곳은 맨 앞 삽입입니다. 흔히 '연결 목록은 삽입이 O(1)'이라고 말하지만, 이 말은 삽입할 자리 바로 앞의 노드를 이미 가지고 있을 때만 맞습니다. 인덱스만 받는 삽입이라면 그 노드를 찾는 O(i)의 이동이 먼저 필요하고, 전체 시간은 이 탐색이 좌우합니다. 반대로 인덱스 조회가 잦은 작업에서는 배열 목록이 압도적으로 유리합니다.

실제 실행 시간에는 Big-O 말고도 메모리 배치가 영향을 줍니다. 배열 목록은 원소의 참조가 연속된 칸에 모여 있지만, 연결 목록의 노드는 힙 여기저기에 흩어져 있어서 순회할 때 CPU 캐시를 덜 효율적으로 씁니다. 원소마다 노드 객체가 하나씩 더 생기는 만큼 메모리도 더 듭니다. 이 비교는 ArrayList와 LinkedList의 연산 비용에서 측정과 함께 자세히 다룹니다.

정리

• 노드는 값과 다음 노드의 참조 next를 담고, 마지막 노드의 next는 null입니다. 목록은 첫 노드를 가리키는 head로 시작하며, 빈 목록의 head는 null입니다.
• 노드 사슬에는 길이 정보가 없습니다. 끝까지 훑을 때는 current != null일 때만 반복하고, 특정 위치로 갈 때는 size로 인덱스를 먼저 검사합니다.
• 조회와 순회는 지역 변수 current로만 합니다. head를 옮기면 앞쪽 노드를 다시 찾을 수 없습니다.
• get(i)는 next를 i번 따라가므로 O(i)이고 최악은 O(n)입니다. 꼬리를 기억하지 않으면 끝 추가도 O(n)이라 n번 추가하면 O(n²)이 되고, tail 필드를 두면 끝 추가가 O(1)이 됩니다.
• size처럼 구조를 요약하는 값은 연결을 바꾼 뒤에 갱신합니다.

연습 문제

1. 첫 노드 head를 받아 노드 수와 마지막 노드의 값을 함께 돌려주는 메서드를 작성하세요. head가 null인 빈 사슬도 처리해야 합니다.
2. 본문의 LinkedNodeWalk에서 get(1) 다음에 get(2)와 get(3)을 차례로 부르면 각각 어떻게 될까요? next 이동 횟수, 결과, 호출 뒤 head가 가리키는 노드를 적으세요. get에서 check(index)를 지우면 get(3)의 결과가 어떻게 달라지는지도 설명하세요.
3. NodeChain.add에서 size++를 메서드 맨 앞으로 옮기면 main을 실행했을 때 어떻게 될까요? 어느 호출에서 무엇이 잘못되는지 따라가 보세요.

public final class NodeChainSummarySolution {
    public static void main(String[] args) {
        Node head = new Node("node", new Node("next", new Node("end", null)));
        print(summarize(head));
        print(summarize(null));
    }

    private static Summary summarize(Node head) {
        int count = 0;
        String last = null;
        for (Node current = head; current != null; current = current.next()) {
            count++;
            last = current.value();
        }
        return new Summary(count, last);
    }

    private static void print(Summary result) {
        System.out.println("count=" + result.count() + ", last=" + result.last());
    }

    private record Node(String value, Node next) {}

    private record Summary(int count, String last) {}
}

count=3, last=end
count=0, last=null

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index out of range: 3

Exception in thread "main" java.lang.NullPointerException: Cannot assign field "next" because the return value of "LinkedNodeWalk$NodeChain.getNode(int)" is null

다음 글

연결 목록의 삽입과 삭제에서는 이 목록에 원하는 위치의 삽입과 삭제를 더합니다. 맨 앞 삽입이 왜 O(1)인지, 그리고 중간에 노드를 끼우거나 뺄 때 참조를 어떤 순서로 바꿔야 뒤쪽 사슬을 잃지 않는지 살펴봅니다.