연결 목록의 삽입과 삭제

배열 목록의 중간에 값을 넣으려면 그 뒤의 원소를 모두 한 칸씩 밀어야 했습니다. 연결 목록에서는 원소를 옮기지 않습니다. 단방향 연결 목록에서 본 것처럼 원소의 순서는 노드의 next 참조가 정하므로, 참조 몇 개만 바꾸면 새 노드를 사슬 중간에 끼울 수 있습니다. 노드를 빼는 것도 마찬가지입니다.

대신 새로운 위험이 생깁니다. 단방향 연결 목록에서 어떤 노드에 닿는 길은 바로 앞 노드의 next 하나뿐입니다. 그래서 참조를 잘못된 순서로 바꾸면 그 길이 끊어지고, 끊어진 지점 뒤의 노드들은 목록에서 통째로 사라집니다. 이 글에서는 이런 일이 실제로 어떻게 일어나는지 먼저 보고, 맨 앞과 중간에서 노드를 안전하게 넣고 빼는 규칙을 정리해 코드로 옮깁니다.

대입 하나를 빠뜨리면 뒤쪽이 사라진다

A 다음에 C가 이어진 사슬이 있고, 그 사이에 B를 넣으려고 합니다. 다음 코드는 A의 next를 새 노드 B로 바꾸기만 합니다.

public final class LinkedInsertionDisconnectBug {
    public static void main(String[] args) {
        Node first = new Node("A");
        first.next = new Node("C");
        Node inserted = new Node("B");
        first.next = inserted;
        System.out.println(first.value + "->" + first.next.value + "->" + first.next.next);
    }

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

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

A->B->null

출력에서 C가 사라졌습니다. 새로 만든 B의 next는 아무것도 대입하지 않았으므로 기본값 null입니다. 그런데 first.next = inserted;를 실행하는 순간, C를 가리키던 유일한 참조인 A의 next가 B로 덮어쓰입니다. C 노드를 가리키는 변수나 필드가 하나도 남지 않으므로, 프로그램은 C에 다시 닿을 방법이 없습니다. C 뒤에 노드가 더 이어져 있었다면 그 노드들도 모두 함께 사라졌을 것입니다. 마지막 출력값 null은 B의 next를 그대로 출력한 것입니다.

고치는 방법은 B를 사슬에 연결하기 전에 B의 next가 C를 가리키게 하는 것입니다. 즉 대입은 다음 순서여야 합니다.

1. 새 노드의 next에 앞 노드의 next(지금 C)를 넣는다: b.next = a.next
2. 앞 노드의 next에 새 노드를 넣는다: a.next = b

1번을 실행한 직후에는 A의 next와 B의 next가 모두 C를 가리킵니다. C로 가는 길이 잠시 두 개가 되는 것입니다. 그다음 2번에서 A의 next를 B로 바꾸면 A에서 C로 바로 가던 길은 없어지지만, B를 거쳐 C로 가는 길이 이미 있으므로 C를 잃지 않습니다. 결과는 A → B → C입니다.

순서를 거꾸로 하면 어떻게 될까요? a.next = b;를 먼저 실행하면 C로 가는 길은 그 순간 사라집니다. 이어서 b.next = a.next;를 실행하면 a.next는 이미 B이므로, B의 next에 B 자신이 들어갑니다. 사슬은 A → B → B → B …로 끝없이 이어지는 고리가 되고, 고리가 없는 사슬을 전제로 쓴 순회는 정상적으로 끝나지 않습니다. 참조를 바꿀 때는 늘 '이 대입으로 덮어쓰는 참조가 어떤 노드에 닿는 유일한 길인가'를 먼저 물어야 합니다. 그렇다면 그 노드를 다른 곳에 먼저 붙잡아 둔 뒤 덮어씁니다.

맨 앞과 중간을 나누는 이유

중간 삽입의 핵심은 '앞 노드'의 next를 바꾸는 것입니다. 그런데 인덱스 0에 넣을 때는 앞 노드가 없습니다. 이때 바꿔야 할 참조는 목록의 head 필드입니다. 그래서 위치를 받는 삽입과 삭제는 인덱스 0인 경우와 나머지 경우를 나눠서 구현합니다. 네 가지 경우를 정리하면 다음과 같습니다.

두 줄씩 짝을 지어 보면 규칙이 같습니다. 맨 앞 삽입은 'head가 앞 노드의 next 역할을 하는' 중간 삽입이고, 맨 앞 삭제도 같은 방식으로 중간 삭제와 짝을 이룹니다. 끝 삽입은 앞 노드가 마지막 노드이고 그 next가 null인 중간 삽입이므로 따로 다룰 필요가 없습니다. 새 노드의 next에 null이 들어가 새 노드가 그대로 마지막 노드가 됩니다.

삭제는 우회로를 만드는 일입니다. 앞 노드의 next가 지울 노드를 건너뛰고 그다음 노드를 가리키게 하면, head부터 걷는 순회는 더 이상 지울 노드를 지나가지 않습니다. 지울 노드를 변수에 먼저 붙잡아 두는 이유는 두 가지입니다. 삭제한 값을 호출한 쪽에 돌려줘야 하고, 우회로를 만들 때 지울 노드의 next를 읽어야 하기 때문입니다.

더 깊이: 더미 노드로 맨 앞 분기 없애기

맨 앞을 따로 처리하는 분기가 번거롭다면, 값을 담지 않는 더미 노드(dummy node)를 목록 맨 앞에 항상 하나 두는 방법이 있습니다. 실제 첫 원소는 더미 노드의 next에 오므로, 인덱스 0에 넣거나 지울 때도 앞 노드가 있습니다. 바로 더미 노드입니다. 그래서 '앞 노드를 찾아 그 next를 바꾼다'는 한 가지 규칙만으로 모든 위치를 처리할 수 있습니다. 이런 노드를 보초 노드(sentinel node)라고도 부릅니다.

Node prev = dummy;                       // 인덱스 0의 앞 노드는 더미 노드
for (int i = 0; i < index; i++) prev = prev.next;
prev.next = new Node(value, prev.next);  // 맨 앞이든 중간이든 같은 코드

대가는 노드 하나만큼의 메모리와, 순회를 head가 아니라 dummy.next에서 시작해야 한다는 규칙입니다. 분기가 줄어드는 만큼 경우를 빠뜨리는 실수가 줄어서, 연결 목록을 다루는 코드에서 자주 쓰이는 기법입니다.

위치를 받는 add와 remove 구현

이제 위 표를 그대로 코드로 옮깁니다. 다음 MyLinkedList<E>는 제네릭 목록과 타입 안전성에서처럼 원소 타입을 E로 받는 제네릭 클래스입니다. add(index, value)는 index 위치에 값을 넣고 원래 그 자리부터 있던 원소들의 인덱스를 하나씩 늘리며, remove(index)는 그 위치의 원소를 빼서 돌려줍니다. 표준 List의 같은 이름 메서드와 뜻이 같습니다.

public final class SinglyLinkedListMutation {
    public static void main(String[] args) {
        MyLinkedList<String> list = new MyLinkedList<>();
        list.add(0, "A");
        list.add(1, "C");
        list.add(1, "B");
        System.out.println(list.remove(1));
        System.out.println(list.get(1));
    }

    private static final class MyLinkedList<E> {
        private Node<E> head;
        private int size;

        void add(int index, E value) {
            checkAdd(index);
            if (index == 0) head = new Node<>(value, head);
            else {
                Node<E> prev = node(index - 1);
                prev.next = new Node<>(value, prev.next);
            }
            size++;
        }

        E remove(int index) {
            check(index);
            Node<E> removed;
            if (index == 0) {
                removed = head;
                head = head.next;
            } else {
                Node<E> prev = node(index - 1);
                removed = prev.next;
                prev.next = removed.next;
            }
            removed.next = null;
            size--;
            return removed.value;
        }

        E get(int index) {
            check(index);
            return node(index).value;
        }

        private Node<E> node(int index) {
            Node<E> n = head;
            for (int i = 0; i < index; i++) {
                n = n.next;
            }
            return n;
        }

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

        private void checkAdd(int i) {
            if (i < 0 || i > size) throw new IndexOutOfBoundsException(i);
        }
    }

    private static final class Node<E> {
        final E value;
        Node<E> next;

        Node(E v, Node<E> n) {
            value = v;
            next = n;
        }
    }
}

B
C

먼저 add를 보겠습니다. 이번 Node 생성자는 값과 다음 노드를 함께 받습니다. 그래서 new Node<>(value, head)는 '새 노드의 next에 지금 head를 넣는 일'을 노드를 만드는 순간에 끝냅니다. 자바는 대입할 값을 오른쪽 식에서 끝까지 계산한 다음에 왼쪽 변수에 넣으므로, head = new Node<>(value, head); 한 줄 안에서도 생성자가 읽는 head는 바뀌기 전의 첫 노드입니다. 새 노드가 다 만들어진 뒤에야 head에 대입됩니다. 중간 삽입의 prev.next = new Node<>(value, prev.next);도 같은 원리로, 오른쪽의 prev.next를 읽어 새 노드에 넣는 일이 먼저 일어나고 prev.next를 덮어쓰는 일은 그다음입니다. 앞 절의 두 단계 순서를 한 줄에 담은 셈입니다.

범위 검사는 두 종류입니다. get과 remove가 쓰는 check는 0 이상 size 미만, 즉 원소가 실제로 있는 위치만 허용합니다. add가 쓰는 checkAdd는 size까지 허용합니다. 원소가 세 개인 목록에 add(3, x)를 하면 맨 끝에 붙이는 것이므로 올바른 요청이기 때문입니다. 두 검사 모두 노드를 하나도 바꾸기 전에 실행되므로, 예외가 나면 목록은 호출 전과 똑같이 남습니다. 예를 들어 원소 세 개인 목록에 add(5, "X")를 부르면 IndexOutOfBoundsException이 나고, 그 예외를 잡은 뒤에도 size는 3이고 원소도 그대로입니다.

main에서 일어나는 일을 차례로 따라가 보겠습니다.

두 번째 호출은 끝 삽입이지만 따로 처리하지 않았습니다. A의 next가 null이었으므로 새 C의 next에도 null이 들어가고, C가 그대로 마지막 노드가 되었습니다. 세 번째 호출이 앞 절에서 본 A와 C 사이의 B 삽입입니다. 출력의 첫 줄 B는 remove(1)이 돌려준 값이고, 둘째 줄 C는 B가 빠진 뒤 인덱스 1로 당겨진 C를 get(1)이 읽은 결과입니다.

remove는 노드를 찾는 방법만 두 경우로 나뉘고, 마무리는 같습니다. 우회로를 만든 뒤 지운 노드의 next를 null로 비우고, size를 줄이고, 붙잡아 둔 노드의 값을 돌려줍니다. 아래 그림이 remove(1)의 세 단계입니다.

여기서도 순서가 중요합니다. removed.next = null;을 우회로를 만들기 전에 실행하면, 그다음 prev.next = removed.next;는 A의 next에 null을 넣습니다. 그러면 B와 함께 C 이후의 노드까지 모두 목록에서 떨어져 나갑니다. 지운 노드의 연결은 반드시 우회로를 만든 다음에 끊어야 합니다.

지운 노드의 next를 비우는 이유

removed.next = null;이 없어도 목록은 올바르게 동작합니다. 우회로를 만든 순간 head부터 걷는 어떤 순회도 B를 지나가지 않기 때문입니다. 그렇다면 왜 이 줄을 넣었을까요?

첫째, 지운 노드가 목록 안을 가리킨 채로 남지 않게 하려는 것입니다. B의 next가 계속 C를 가리키고 있으면 디버거로 B를 봤을 때 B가 아직 목록에 속한 것처럼 보이고, 실수로 B에서 출발해 순회하는 코드가 있으면 목록의 뒷부분을 읽어 버립니다. 연결을 끊어 두면 B가 목록 밖에 있다는 사실이 분명해집니다. 둘째, 가비지 컬렉션에 미치는 영향을 줄이려는 것입니다. 목록이 B를 더 이상 가리키지 않아도 다른 곳에 B의 참조가 남아 있을 수 있습니다. 그런 B가 C를 계속 가리키면, 목록에서 C까지 지운 뒤에도 C가 B를 통해 계속 닿을 수 있는 객체로 남아 회수되지 못할 수 있습니다.

다만 이 줄이 메모리를 '즉시' 돌려준다는 뜻은 아닙니다. 객체는 어떤 참조로도 닿을 수 없게 되었을 때 가비지 컬렉터가 회수할 수 있는 대상이 될 뿐, 언제 실제로 회수할지는 가비지 컬렉터가 정합니다. 위 예제에서도 B는 remove가 값을 돌려줄 때까지 지역 변수 removed로 쓰이고, 그 뒤에야 어디에서도 닿을 수 없는 객체가 됩니다. 표준 라이브러리의 java.util.LinkedList도 노드를 지울 때 그 노드의 참조 필드를 모두 null로 비웁니다.

삽입이 O(1)이라는 말의 조건

참조를 바꾸는 일 자체는 위치와 상관없이 대입 두세 번이면 끝납니다. 그래서 '연결 목록은 삽입과 삭제가 O(1)'이라고들 합니다. 하지만 이 말은 바꿀 자리의 앞 노드를 이미 손에 쥐고 있을 때만 맞습니다.

add(index, value)처럼 인덱스만 받는 메서드는 앞 노드를 직접 찾아야 합니다. node(index - 1)은 head에서 출발해 next를 index−1번 따라가므로, 인덱스 i에 넣거나 지우는 데 드는 전체 시간은 O(i)이고 최악은 O(n)입니다. 맨 앞(i = 0)만 탐색 없이 O(1)입니다. 지금 구현에는 꼬리 참조가 없으므로 맨 끝 삽입도 O(n)이고, 꼬리 참조를 두더라도 맨 끝 원소를 지우는 데는 여전히 O(n)이 듭니다. 단방향 연결에서는 마지막 노드의 앞 노드를 알려면 앞에서부터 걸어야 하기 때문입니다.

연결 목록의 강점이 그대로 살아나는 경우는 둘입니다. 하나는 맨 앞에서 넣고 빼는 일이 대부분인 경우입니다. 다른 하나는 순회하면서 지금 노드 주변을 고치는 경우입니다. 반복자로 목록을 한 번 훑으며 조건에 맞는 원소를 지우면, 탐색은 원래 하던 순회에 포함되고 지울 때마다 참조 몇 개만 바꾸면 됩니다. 같은 일을 배열 목록에서 원소마다 remove로 하면 지울 때마다 뒤쪽 원소를 당겨야 합니다. 반복자는 Iterable과 Iterator에서 다룹니다.

게시글 저장소에 위치 삽입과 삭제 붙이기

앞 글에서 노드 사슬로 바꾼 게시글 저장소에 원하는 위치에 넣는 insert와 위치로 지우는 remove를 더해 보겠습니다. 이 저장소는 끝 추가를 O(1)로 하려고 tail 필드를 가지고 있으므로, 노드를 바꿀 때마다 head와 함께 tail도 맞춰야 합니다. 원소 수를 알아야 인덱스를 검사할 수 있으므로 size도 다시 둡니다.

public final class PostRepositoryCliCH145 {
    public static void main(String[] args) {
        PostRepository repository = new PostRepository();
        repository.add("link-insert", 41);
        repository.add("link-remove", 49);
        repository.insert(1, "splice", 30);
        repository.print();
        System.out.println("removed=" + repository.remove(2).title());
        repository.add("tail-check", 25);
        repository.print();
        System.out.println("total=" + repository.totalViewCount());
    }

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

        void add(String title, int viewCount) {
            insert(size, title, viewCount);
        }

        void insert(int index, String title, int viewCount) {
            if (index < 0 || index > size) throw new IndexOutOfBoundsException(index);
            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 (index == 0) {
                added.next = head;
                head = added;
            } else {
                Node prev = index == size ? tail : node(index - 1);
                added.next = prev.next;
                prev.next = added;
            }
            if (added.next == null) tail = added;
            size++;
        }

        Entry remove(int index) {
            if (index < 0 || index >= size) throw new IndexOutOfBoundsException(index);
            Node prev = index == 0 ? null : node(index - 1);
            Node removed = prev == null ? head : prev.next;
            if (prev == null) head = removed.next;
            else prev.next = removed.next;
            if (removed == tail) tail = prev;
            removed.next = null;
            size--;
            return removed.entry;
        }

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

        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:link-insert=41
1:splice=30
2:link-remove=49
removed=link-remove
0:link-insert=41
1:splice=30
2:tail-check=25
total=96

add는 이제 insert(size, …)를 부르기만 합니다. index가 size와 같으면 앞 노드는 마지막 노드이므로, 사슬을 걷지 않고 tail을 바로 씁니다. 그래서 끝 추가는 여전히 O(1)입니다. 새 노드의 next가 null이라는 것은 새 노드가 마지막 노드가 되었다는 뜻이므로, 그때 tail을 새 노드로 옮깁니다. 빈 목록에 처음 넣을 때(index == 0이고 head가 null)도 이 조건으로 tail이 정해집니다.

remove는 마지막 노드를 지울 때 tail을 앞 노드로 되돌립니다. 원소가 하나뿐이었다면 앞 노드가 null이므로 tail도 null이 되어, head와 tail이 모두 null인 빈 목록 상태로 정확히 돌아갑니다. 실행 결과의 첫 묶음은 insert(1, …)이 splice를 두 원소 사이에 끼운 결과이고, removed=link-remove는 인덱스 2의 마지막 원소를 지운 결과입니다. 이어서 추가한 tail-check가 splice 뒤에 붙었다는 것은 tail이 제대로 앞 노드로 돌아갔다는 뜻입니다. 합계 96은 41 + 30 + 25입니다.

if (removed == tail) tail = prev; 한 줄을 빠뜨리면 예외 없이 결과만 틀어집니다. tail이 이미 목록에서 빠진 link-remove 노드를 계속 가리키므로, 다음 add는 새 노드를 그 떨어져 나간 노드 뒤에 붙입니다. 실제로 실행해 보면 두 번째 print에 tail-check가 나오지 않고 합계는 71이 되는데, size는 3입니다. 노드 수와 size가 어긋난 이런 상태는 한참 뒤에야 엉뚱한 곳에서 문제를 일으킵니다. 그래서 목록을 바꾸는 코드를 시험할 때는 원소의 순서뿐 아니라 head부터 센 노드 수가 size와 같은지, tail이 정말 마지막 노드인지도 함께 확인해야 합니다.

저장소의 insert와 remove는 노드가 아니라 인덱스와 Entry만 주고받습니다. 노드를 바깥에 돌려주면 바깥 코드가 next를 마음대로 바꿔 사슬을 망가뜨릴 수 있기 때문입니다. 그만큼 바깥에서는 앞 노드를 직접 쥘 수 없으므로, 위치를 받는 삽입과 삭제의 비용에는 앞 노드를 찾는 탐색이 항상 들어갑니다.

정리

• 노드를 끼울 때는 새 노드의 next에 뒤쪽 노드를 먼저 연결하고, 그다음 앞 노드의 next(맨 앞이면 head)를 새 노드로 바꿉니다. 순서를 거꾸로 하면 뒤쪽 사슬로 가는 유일한 길이 끊깁니다.
• 노드를 뺄 때는 지울 노드를 먼저 변수에 붙잡고, 앞 노드의 next(맨 앞이면 head)가 지울 노드의 next를 가리키게 우회한 뒤, 지운 노드의 next를 null로 비웁니다.
• 인덱스 0은 앞 노드가 없어서 head를 바꾸는 별도의 경우가 됩니다. 더미 노드를 두면 이 분기를 없앨 수 있습니다.
• 참조를 바꾸는 일은 O(1)이지만, 인덱스로 호출하면 앞 노드를 찾는 탐색 때문에 O(i), 최악 O(n)입니다. 맨 앞 삽입과 삭제는 탐색 없이 O(1)이고, 꼬리 참조가 있으면 맨 끝 삽입도 O(1)입니다. 맨 끝 삭제는 꼬리 참조가 있어도 O(n)입니다.
• 범위 검사는 노드를 바꾸기 전에 하고, size와 tail 같은 요약 정보는 연결을 바꾼 뒤 함께 갱신합니다.

연습 문제

1. A가 C를 가리키는 두 노드 사슬이 있습니다. 새 노드 B를 사이에 넣은 뒤, 순서가 A, B, C이고 C 다음이 null인지 출력해 확인하세요. 두 대입의 순서를 바꾸면 출력이 어떻게 달라지는지도 설명하세요.
2. A → B → C인 MyLinkedList에서 remove(2)를 호출하면 앞 노드와 지울 노드는 각각 무엇인가요? 대입이 끝난 뒤 B의 next, C의 next, 돌려주는 값, 새 size를 차례로 적으세요.
3. 단방향 연결 목록의 순서를 뒤집는 메서드 reverse(Node head)를 작성하세요. 새 노드를 만들지 말고, 각 노드의 next 방향만 바꿔서 새 첫 노드를 돌려주어야 합니다.

public final class LinkedSpliceIntegritySolution {
    public static void main(String[] args) {
        Node a = new Node("A");
        Node c = new Node("C");
        a.next = c;
        Node b = new Node("B");
        b.next = a.next;
        a.next = b;
        String order = a.value + a.next.value + a.next.next.value;
        System.out.println("order=" + order + ", end=" + (a.next.next.next == null));
    }

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

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

order=ABC, end=true

public final class ReverseInPlace {
    public static void main(String[] args) {
        Node head = new Node("A", new Node("B", new Node("C", null)));
        System.out.println(join(reverse(head)));
        System.out.println(join(reverse(null)));
    }

    static Node reverse(Node head) {
        Node prev = null;
        Node current = head;
        while (current != null) {
            Node next = current.next; // 뒤쪽 사슬을 먼저 붙잡는다
            current.next = prev;      // 방향을 뒤집는다
            prev = current;
            current = next;
        }
        return prev;
    }

    static String join(Node head) {
        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 {
        final String value;
        Node next;

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

[C, B, A]
[]

다음 글

단방향 연결 목록은 앞 노드를 알려면 언제나 head부터 다시 걸어야 했고, 그래서 맨 끝 삭제조차 O(n)이었습니다. 양방향 연결 목록에서는 노드마다 앞 노드의 참조 prev를 하나 더 두어 이 문제를 풉니다. 그 대가로 노드를 넣고 뺄 때마다 맞춰야 할 참조가 두 배로 늘어나는데, 그 규칙을 정리합니다.