양방향 연결 목록

연결 목록의 삽입과 삭제에서 만든 단방향 연결 목록은 노드가 다음 노드만 알고 있었습니다. 그래서 어떤 노드의 앞 노드가 필요할 때마다 head부터 다시 걸어야 했습니다. 꼬리 참조 tail을 두어 마지막 노드를 바로 찾을 수 있어도, 마지막 노드를 지우려면 그 앞 노드의 next를 바꿔야 하므로 결국 처음부터 걸어야 했습니다. 목록을 거꾸로 훑는 것도 불가능했습니다.

양방향 연결 목록(doubly linked list)은 노드마다 앞 노드를 가리키는 참조 prev를 하나 더 둡니다. 이제 어느 노드에서든 앞뒤로 한 칸씩 움직일 수 있고, 목록은 head와 tail 양쪽 끝에서 출발할 수 있습니다. 그 대가로 노드를 넣거나 뺄 때 맞춰야 할 참조가 두 배로 늘어납니다. 게다가 그중 하나를 빠뜨려도 앞에서 뒤로 훑을 때는 아무 문제가 드러나지 않습니다. 이 글에서는 그런 실수가 어떻게 숨는지 먼저 보고, 양쪽 연결을 함께 맞추는 삽입과 삭제, 가까운 끝에서 노드를 찾는 방법, 연결이 올바른지 검사하는 방법을 차례로 구현합니다.

앞뒤를 모두 가리키는 노드

양방향 노드에는 값과 함께 참조가 두 개 있습니다. next는 다음 노드를, prev는 앞 노드를 가리킵니다. 첫 노드에는 앞 노드가 없으므로 prev가 null이고, 마지막 노드에는 다음 노드가 없으므로 next가 null입니다. A, B, C 세 노드라면 next를 따라가면 A → B → C, prev를 따라가면 C → B → A 순서로 방문합니다.

이 구조가 제대로 동작하려면 목록이 어떻게 바뀌든 다음 조건들이 늘 성립해야 합니다. 이처럼 자료구조를 바꾸는 연산이 끝날 때마다 언제나 참이어야 하는 조건을 불변식(invariant)이라고 합니다.

• 빈 목록에서는 head와 tail이 모두 null이고 size는 0입니다.
• 원소가 하나뿐이면 head와 tail이 같은 노드를 가리킵니다.
• head의 prev와 tail의 next는 언제나 null입니다.
• X의 next가 Y라면, Y의 prev는 반드시 X입니다. 반대로 Y의 prev가 X라면 X의 next는 Y입니다.
• head부터 next로 센 노드 수와 tail부터 prev로 센 노드 수는 모두 size와 같습니다.

네 번째 조건이 양방향 목록의 핵심입니다. 이웃한 두 노드는 서로를 가리켜야 합니다. 한쪽만 가리키면 앞에서 본 목록과 뒤에서 본 목록이 달라집니다.

prev 하나를 빠뜨린 삽입

A와 C가 서로를 가리키는 두 노드 사이에 B를 넣어 보겠습니다. 다음 코드는 B의 prev와 next를 설정하고 A의 next도 B로 바꿉니다. 하지만 C의 prev를 B로 바꾸는 줄은 빠뜨렸습니다.

public final class BrokenPrevLinkFailure {
    public static void main(String[] args) {
        Node a = new Node("A");
        Node c = new Node("C");
        a.next = c;
        c.prev = a;

        Node b = new Node("B");
        b.prev = a;
        b.next = c;
        a.next = b;
        // c.prev = b를 빠뜨렸다.

        System.out.println("forward=" + a.value + a.next.value + a.next.next.value);
        System.out.println("backward=" + c.value + c.prev.value);
    }

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

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

forward=ABC
backward=CA

첫 줄은 A에서 next를 두 번 따라간 결과입니다. A의 next는 B, B의 next는 C이므로 ABC가 나옵니다. 앞에서 뒤로 보는 한 삽입은 성공한 것처럼 보입니다. 둘째 줄은 C에서 prev를 한 번 따라간 결과인데, CB가 아니라 CA가 나왔습니다. C의 prev가 여전히 삽입 전의 앞 노드인 A를 가리키고 있기 때문입니다. 뒤에서 앞으로 걸으면 B를 건너뛰는 셈입니다.

이런 버그가 위험한 이유는 오래 숨어 있기 때문입니다. 대부분의 코드는 목록을 앞에서부터 훑으므로, toString이나 정방향 순회로 확인하면 아무 이상이 없습니다. 그러다 역순으로 훑거나 맨 끝에서 지우는 코드가 실행될 때에야 원소가 빠지거나 엉뚱한 노드가 연결됩니다. 그래서 양방향 목록은 한 방향의 출력만으로 검사하면 부족합니다. 이웃한 모든 노드 쌍에서 node.next.prev == node가 성립하는지, 즉 앞의 네 번째 불변식을 직접 확인해야 합니다.

양방향 목록 구현하기

다음 DoublyList<E>는 head, tail, size 세 필드로 목록을 표현합니다. 끝 추가 addLast와 위치 삽입 add(index, value)는 모두 내부 메서드 linkBefore 하나로 처리합니다. 지정한 노드 바로 앞에 새 노드를 끼우는 메서드입니다. remove(index)는 노드를 빼서 값을 돌려주고, linksAreValid()는 앞 절의 불변식이 모두 성립하는지 검사합니다. forward()와 backward()는 목록을 앞에서부터, 그리고 뒤에서부터 훑어 값을 -로 이은 문자열을 만듭니다.

main은 A와 C를 넣고 그 사이에 B를 끼운 뒤, B를 지우고 값이 같은 새 B를 다시 넣습니다. 그다음 양방향으로 출력하고 연결을 검사합니다.

public final class DoublyLinkedListInvariant {
    public static void main(String[] args) {
        DoublyList<String> list = new DoublyList<>();
        list.addLast("A");
        list.addLast("C");
        list.add(1, "B");
        System.out.println("removed=" + list.remove(1));
        list.add(1, "B");
        System.out.println(list.forward());
        System.out.println(list.backward());
        System.out.println("links=" + list.linksAreValid());
    }

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

        void addLast(E value) {
            linkBefore(value, null);
        }

        void add(int index, E value) {
            checkAddIndex(index);
            linkBefore(value, index == size ? null : node(index));
        }

        private void linkBefore(E value, Node<E> successor) {
            Node<E> predecessor = successor == null ? tail : successor.prev;
            Node<E> added = new Node<>(value, predecessor, successor);
            if (predecessor == null) head = added;
            else predecessor.next = added;
            if (successor == null) tail = added;
            else successor.prev = added;
            size++;
        }

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

        private Node<E> node(int index) {
            checkElementIndex(index);
            if (index < size / 2) {
                Node<E> current = head;
                for (int i = 0; i < index; i++) {
                    current = current.next;
                }
                return current;
            }
            Node<E> current = tail;
            for (int i = size - 1; i > index; i--) {
                current = current.prev;
            }
            return current;
        }

        boolean linksAreValid() {
            int count = 0;
            Node<E> previous = null;
            for (Node<E> current = head; current != null; current = current.next) {
                if (current.prev != previous) return false;
                previous = current;
                count++;
            }
            return previous == tail
                    && count == size
                    && (head == null || head.prev == null)
                    && (tail == null || tail.next == null);
        }

        String forward() {
            return join(true);
        }

        String backward() {
            return join(false);
        }

        private String join(boolean forward) {
            StringBuilder out = new StringBuilder();
            for (Node<E> n = forward ? head : tail; n != null; n = forward ? n.next : n.prev) {
                if (!out.isEmpty()) out.append('-');
                out.append(n.value);
            }
            return out.toString();
        }

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

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

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

        private Node(E value, Node<E> prev, Node<E> next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }
}

removed=B
A-B-C
C-B-A
links=true

main의 호출마다 무엇이 바뀌는지 따라가 보겠습니다. 위치를 받는 호출에서 어떤 노드를 찾을지는 뒤에서 설명할 node(index)가 정하는데, 이 예제의 세 호출은 모두 tail에서 출발합니다.

출력의 첫 줄 removed=B는 remove(1)이 돌려준 값입니다. 다시 넣은 B는 값만 같을 뿐, 지운 B와는 다른 새 노드입니다. 둘째 줄과 셋째 줄은 같은 목록을 앞에서, 그리고 뒤에서 훑은 결과이고 서로 정확히 반대 순서입니다. 마지막 줄 links=true는 마지막 상태에서 모든 불변식이 성립한다는 뜻입니다. 중간 상태들은 검사하지 않았으므로, 이 한 줄이 모든 단계가 올바랐다는 뜻은 아닙니다.

linkBefore: 새 노드를 양쪽 이웃에 연결하기

linkBefore(value, successor)는 successor 바로 앞에 새 노드를 끼웁니다. successor가 null이면 맨 끝에 붙인다는 뜻입니다. 메서드는 세 단계로 진행합니다.

먼저 새 노드의 앞 노드가 될 predecessor를 구합니다. 맨 끝에 붙일 때는 지금의 tail이 앞 노드이고, 그렇지 않으면 successor.prev가 앞 노드입니다. 이렇게 양쪽 이웃을 지역 변수 predecessor와 successor에 붙잡아 두는 것이 이 메서드의 핵심입니다. 다음으로 새 노드를 만들면서 생성자에서 prev와 next가 두 이웃을 가리키게 합니다. 이 단계는 새 노드의 필드만 쓰고 기존 노드는 하나도 건드리지 않습니다. 마지막으로 기존 연결 두 개를 새 노드로 바꿉니다. 앞 노드의 next(앞 노드가 없으면 head)와 뒤 노드의 prev(뒤 노드가 없으면 tail)입니다.

앞 글의 단방향 삽입에서는 앞 노드의 next를 덮어쓰기 전에 그 값을 새 노드에 옮겨 두어야 했습니다. 여기서는 두 이웃을 지역 변수로 이미 붙잡아 두었으므로, 마지막 두 대입을 어떤 순서로 하든 어느 노드도 잃지 않습니다. 단, 둘 중 하나를 빠뜨리면 앞 절의 BrokenPrevLinkFailure와 같은 반쪽 연결이 됩니다.

두 이웃이 각각 있는지 없는지에 따라 네 가지 경우가 생기는데, 코드의 두 if가 이를 모두 처리합니다.

양쪽 이웃이 없을 때 null 대신 head나 tail을 바꾼다고 생각하면, 네 경우가 모두 같은 규칙입니다. 그래서 맨 앞과 맨 끝을 위한 별도의 메서드가 필요 없습니다.

remove: 지운 노드의 양쪽 이웃을 서로 잇기

remove(index)는 지울 노드를 찾은 뒤 그 노드의 prev와 next를 지역 변수 predecessor와 successor에 붙잡습니다. 그다음 앞 노드의 next가 뒤 노드를, 뒤 노드의 prev가 앞 노드를 가리키게 해서 두 이웃을 서로 직접 잇습니다. 앞 노드가 없으면 head를, 뒤 노드가 없으면 tail을 대신 바꾸는 것은 삽입과 같습니다. 우회로가 완성되면 지운 노드의 두 참조를 모두 null로 비우고 size를 줄입니다.

remove에는 범위 검사가 따로 보이지 않습니다. 첫 줄의 node(index)가 맨 처음에 checkElementIndex를 실행하기 때문입니다. 잘못된 인덱스는 참조를 하나도 바꾸기 전에 예외로 거부되므로, 예외가 나도 목록은 호출 전 그대로입니다.

단방향 목록과 비교하면 큰 차이가 하나 있습니다. 노드를 찾은 다음의 작업이 전부 그 노드의 prev와 next만으로 끝난다는 점입니다. 단방향 목록에서는 지울 노드의 앞 노드를 찾으려고 head부터 걸어야 했지만, 여기서는 removed.prev가 바로 앞 노드입니다. 그래서 지울 노드를 이미 가지고 있다면 삭제는 위치와 상관없이 O(1)입니다. 맨 끝 원소를 지우는 일도 tail.prev가 새 꼬리가 되므로 O(1)입니다. 단방향 목록에서는 O(n)이었습니다.

가까운 끝에서 노드 찾기

node(index)는 인덱스가 앞쪽 절반에 있으면(index < size / 2) head에서 next로, 그렇지 않으면 tail에서 prev로 걷습니다. tail의 인덱스가 size - 1이므로 뒤에서 걸을 때는 size - 1 - index번 이동합니다. 크기가 9와 10인 목록에서 인덱스마다 이동 횟수를 세어 보면 다음과 같습니다.

head에서만 걷는다면 크기 10에서 마지막 원소까지 9번 이동해야 하지만, 가까운 끝에서 출발하면 어느 인덱스든 n/2번을 넘지 않습니다. 이동 횟수는 min(i, n−1−i)입니다. 그렇다고 get이 O(1)이 되지는 않습니다. 가운데 원소를 읽으려면 여전히 원소 수의 절반쯤 걸어야 하므로, 최악의 경우는 그대로 O(n)이고 상수만 절반으로 줄어듭니다. 위치를 받는 add와 remove도 노드를 찾는 데 이만큼 걷고, 찾은 뒤의 연결 작업은 O(1)입니다.

맨 앞, 맨 끝, 빈 목록에서도 맞는지 확인하기

앞의 main은 가운데 노드만 넣고 뺐습니다. 하지만 불변식이 깨지기 가장 쉬운 곳은 양 끝입니다. 원소가 0개에서 1개가 될 때 새 노드는 head이면서 동시에 tail이어야 하고, 1개에서 0개가 될 때는 두 필드가 모두 null로 돌아가야 합니다. 원소가 둘인 목록에서 head를 지우면 남은 노드의 prev가 null이 되어야 하고, tail을 지우면 남은 노드의 next가 null이 되어야 합니다. 일반 규칙에 null 이웃을 넣은 결과일 뿐이지만, 한 번에 여러 불변식이 함께 바뀌므로 따로 실행해 확인할 가치가 있습니다.

앞의 DoublyLinkedListInvariant에서 DoublyList는 그대로 두고 main의 본문만 아래처럼 바꾸면, 양 끝의 변화를 단계마다 검사할 수 있습니다. 실행하기 전에 일곱 줄의 출력을 먼저 예상해 보세요.

DoublyList<String> list = new DoublyList<>();
list.addLast("A");
list.addLast("C");
System.out.println("tail-removed=" + list.remove(1));
System.out.println(list.forward());
System.out.println("one-links=" + list.linksAreValid());
System.out.println("last-removed=" + list.remove(0));
System.out.println("empty-links=" + list.linksAreValid());
list.add(0, "X");
System.out.println(list.backward());
System.out.println("readded-links=" + list.linksAreValid());

tail-removed=C
A
one-links=true
last-removed=A
empty-links=true
X
readded-links=true

양 끝 처리를 하나라도 빠뜨리면 어떻게 될까요? remove에서 tail을 되돌리는 처리를 빠뜨려, 뒤 노드가 없을 때 아무것도 하지 않게 만들었다고 해 봅시다.

if (predecessor == null) head = successor;
else predecessor.next = successor;
if (successor != null) successor.prev = predecessor; // tail 갱신을 빠뜨림

이 상태에서 A와 C를 넣고 remove(1)로 C를 지운 뒤 linksAreValid()를 검사하고, 이어서 addLast("D")를 하고 양방향으로 출력하면 결과는 다음과 같습니다. 셋째 줄은 앞에서부터, 넷째 줄은 뒤에서부터 훑은 결과이므로, 목록이 정상이라면 두 줄에 같은 원소가 반대 순서로 나와야 합니다.

removed=C
links=false
A
D-C

C를 지운 뒤에도 tail은 이미 목록에서 빠진 C를 가리킵니다. linksAreValid()는 head부터 걸은 뒤 마지막으로 방문한 A가 tail과 다르다는 것을 발견하고 false를 돌려줍니다. 검사하지 않고 넘어가면 문제는 더 커집니다. addLast("D")는 tail을 앞 노드로 쓰므로 D를 떨어져 나간 C 뒤에 붙입니다. 그 결과 앞에서 훑으면 A만 보이고, 뒤에서 훑으면 D와 이미 지운 C가 보입니다. 원소를 하나 지우고 하나 넣었을 뿐인데 두 방향이 완전히 다른 목록이 되었습니다.

linksAreValid()의 검사 방법도 짚어 보겠습니다. head부터 next로 걸으면서, 지금 노드의 prev가 직전에 방문한 노드(previous)인지 비교합니다. 첫 노드에서는 previous가 null이므로 head의 prev가 null인지도 함께 확인됩니다. 다 걸은 뒤에는 마지막으로 방문한 노드가 tail인지, 방문한 노드 수가 size와 같은지 봅니다. 이 조건들이 모두 맞으면 tail부터 prev로 걷는 순서는 앞에서 걸은 순서를 정확히 뒤집은 것이 됩니다. 반환문의 마지막 두 조건은 사실 반복문 안의 검사와 반복의 종료 조건에 이미 포함되어 있지만, 불변식을 코드에 그대로 드러내려고 적어 두었습니다.

표준 LinkedList로 게시글 기록 보기

자바 표준 라이브러리의 java.util.LinkedList도 양방향 연결 목록입니다. 처음 노드와 마지막 노드를 필드로 가지고 있어서, 양 끝을 읽고 넣고 빼는 메서드가 모두 O(1)입니다. 다음 프로그램은 게시글을 입력 순서대로 저장한 뒤, 가장 오래된 기록과 최신 기록을 읽고 최신순으로 훑습니다.

import java.util.LinkedList;

public final class DoublyPostRepositoryCli {
    public static void main(String[] args) {
        LinkedList<Entry> entries = new LinkedList<>();
        entries.addLast(new Entry("prev-link", 45));
        entries.addLast(new Entry("next-link", 55));
        entries.addLast(new Entry("tail-link", 30));
        System.out.println("oldest=" + entries.getFirst().title());
        System.out.println("newest=" + entries.getLast().title());
        for (Entry entry : entries.reversed()) {
            System.out.println("recent: " + entry.title());
        }
        System.out.println("dropped=" + entries.removeFirst().title());
        int total = 0;
        for (Entry entry : entries) {
            total += entry.viewCount();
        }
        System.out.println("total=" + total);
    }

    private record Entry(String title, int viewCount) {
        private Entry {
            if (title == null || title.isBlank() || viewCount <= 0) {
                throw new IllegalArgumentException("invalid entry");
            }
        }
    }
}

oldest=prev-link
newest=tail-link
recent: tail-link
recent: next-link
recent: prev-link
dropped=prev-link
total=85

getFirst()와 getLast()는 처음과 마지막 노드의 값을 바로 돌려줍니다. reversed()는 Java 21에서 추가된 메서드로, 원소를 복사하지 않고 같은 목록을 거꾸로 보여 주는 뷰(view)를 돌려줍니다. 그래서 recent: 세 줄이 최신 기록부터 나옵니다. removeFirst()는 가장 오래된 기록을 지우면서 그 값을 돌려주고, 마지막 줄은 남은 두 기록의 조회 수 55와 30을 더한 결과입니다. 이 프로그램이 쓴 연산은 모두 양 끝에서 일어나므로, 기록이 아무리 많아도 순회를 뺀 각 연산은 O(1)입니다.

하지만 양 끝만 빠르다는 이유로 LinkedList를 고르면 안 됩니다. get(i)처럼 인덱스로 읽는 일이 잦다면 앞 절에서 본 것처럼 호출마다 목록의 절반까지 걸어야 하므로, 위치를 계산해 바로 읽는 ArrayList가 훨씬 빠릅니다. Java 21부터는 ArrayList에도 getFirst(), getLast(), reversed() 같은 메서드가 있습니다. 다만 ArrayList의 removeFirst()는 나머지 원소를 모두 한 칸씩 당겨야 하므로 O(n)입니다. 양 끝에서 넣고 빼는 일이 주된 작업이라면 배열 기반이면서 양 끝의 삽입과 삭제를 분할 상환 O(1)에 처리하는 ArrayDeque가 보통 더 나은 선택인데, 이는 ArrayDeque로 스택과 큐 다루기에서 비교합니다.

더 깊이: java.util.LinkedList의 내부

OpenJDK 21의 LinkedList는 이 글의 DoublyList와 거의 같은 모양입니다. 아래의 필드와 메서드 이름은 공개 API가 아닌 내부 구현이라 버전에 따라 바뀔 수 있습니다. 첫 노드와 마지막 노드를 가리키는 first와 last 필드, 원소 수 size를 가지고 있습니다. 노드 클래스 Node<E>에는 값 item과 참조 next, prev가 있습니다. 인덱스로 노드를 찾는 내부 메서드 node(int index)는 index < (size >> 1)이면 first에서, 아니면 last에서 걷습니다. 공식 문서도 인덱스를 쓰는 연산은 지정한 인덱스에 더 가까운 끝에서부터 목록을 훑는다고 설명합니다. size >> 1은 size / 2와 같은 값을 비트 이동으로 계산한 것입니다.

삽입은 linkBefore, linkFirst, linkLast가, 삭제는 unlink, unlinkFirst, unlinkLast가 맡습니다. 이 메서드들은 지운 노드의 item, prev, next를 모두 null로 비웁니다. 지운 노드가 원소 객체나 목록의 다른 노드를 계속 붙잡아 가비지 컬렉션을 방해하지 않게 하려는 것입니다.

연결 목록의 장점이 그대로 살아나는 곳은 반복자입니다. listIterator()로 얻은 반복자의 add와 remove는 반복자가 이미 들고 있는 노드를 기준으로 linkBefore와 unlink를 부르므로, 순회하는 동안의 삽입과 삭제가 한 번에 O(1)입니다. 반대로 for (int i = 0; i < list.size(); i++) 안에서 list.get(i)를 부르면 호출마다 노드를 다시 찾으므로 전체가 O(n²)이 됩니다. 반복자는 Iterable과 Iterator에서 자세히 다룹니다.

단방향과 양방향, 무엇을 얻고 무엇을 내주는가

지금까지 본 연산의 비용을 단방향 연결 목록과 비교하면 다음과 같습니다. 두 목록 모두 head와 tail을 가지고 있다고 가정합니다.

양방향 연결이 주는 것은 '앞 노드를 바로 안다'는 한 가지이고, 표에서 달라진 칸은 모두 여기서 나옵니다. 대신 노드마다 참조가 하나 더 들고, 노드를 바꾸는 코드는 참조를 두 배로 맞춰야 합니다. 앞에서 본 것처럼 그중 하나를 빠뜨린 버그는 한 방향에서는 보이지 않습니다. 그러니 역순 탐색이나 맨 끝 삭제, 순회 중 삭제가 실제로 필요할 때 양방향 연결을 고르는 것이 좋습니다. 필요하지 않은 prev를 유지하는 것은 버그가 숨을 곳만 늘리는 일입니다. 배열 목록과의 실제 성능 차이는 ArrayList와 LinkedList의 연산 비용에서 다룹니다.

정리

• 양방향 노드는 prev와 next를 함께 가지고, 목록은 head와 tail을 함께 관리합니다. 이웃한 두 노드는 반드시 서로를 가리켜야 하고, head의 prev와 tail의 next는 null입니다.
• 삽입은 두 이웃을 지역 변수로 붙잡고, 새 노드가 두 이웃을 가리키게 만든 뒤, 앞 노드의 next와 뒤 노드의 prev를 새 노드로 바꿉니다. 이웃이 없는 쪽은 head나 tail을 바꿉니다.
• 삭제는 지울 노드의 두 이웃을 서로 직접 잇고, 지운 노드의 prev와 next를 비웁니다. 노드를 이미 가지고 있으면 삭제는 O(1)이고, 맨 끝 삭제도 O(1)입니다.
• 인덱스로 노드를 찾을 때는 가까운 끝에서 출발하므로 이동이 n/2번을 넘지 않지만, 최악의 경우는 여전히 O(n)입니다.
• 한 방향의 출력만으로는 연결이 올바른지 알 수 없습니다. 모든 이웃 쌍의 상호 참조와 head, tail, size를 함께 검사하고, 빈 목록과 원소 하나인 목록에서도 따로 확인합니다.

연습 문제

1. A와 C가 서로를 가리키는 두 노드 사이에 B를 넣으세요. A.next, B.prev, B.next, C.prev 네 참조가 모두 올바른지 boolean 하나로 출력해야 합니다. 정방향 문자열만 비교하는 검사와 무엇이 다른지도 설명하세요.
2. DoublyList에 A, B, C가 들어 있을 때 remove(2)를 호출하면 node(2)는 어디서 출발해 몇 번 이동하나요? 이어서 predecessor와 successor는 무엇이고, head, tail, 각 노드의 참조, size는 어떻게 바뀌나요? 같은 일을 tail이 있는 단방향 목록에서 할 때와 비교하세요.
3. node(index)가 가까운 끝을 고르지 않고 언제나 head에서 걷도록 바꾸면, 본문 main의 출력이 달라질까요? 달라지는 것이 있다면 무엇인지, Big-O로는 어떻게 되는지 설명하세요.

public final class DoublyLinkRepairSolution {
    public static void main(String[] args) {
        Node a = new Node("A");
        Node c = new Node("C");
        a.next = c;
        c.prev = a;

        Node b = new Node("B");
        b.prev = a;
        b.next = c;
        a.next = b;
        c.prev = b;

        boolean valid = a.next == b && b.prev == a && b.next == c && c.prev == b;
        System.out.println("valid=" + valid);
    }

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

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

valid=true

다음 글

이제 배열 목록 하나와 연결 목록 두 가지를 직접 만들었습니다. 셋 다 add, get, size 같은 이름의 메서드를 가지고 있지만, 지금 상태로는 한 구현을 쓰던 코드에서 다른 구현으로 바꾸려면 그 코드를 고쳐야 합니다. MyList 인터페이스로 목록 구현 바꾸기에서는 목록의 공통 역할을 인터페이스로 묶어, 쓰는 쪽 코드를 고치지 않고 구현을 바꿔 끼우는 방법을 살펴봅니다.