양방향 연결 목록

단방향 목록은 이전 Node를 찾으려면 head에서 다시 걸어야 합니다.

양방향 목록은 각 Node에 prev와 next를 함께 저장하고 head·꼬리 노드 두 끝점을 관리합니다.

탐색 방향은 빨라질 수 있지만 연결 하나를 바꿀 때 맞춰야 할 참조가 늘어납니다.

이 절의 기준은 “정방향으로 이어진다”가 아니라 모든 인접 쌍이 양쪽에서 서로를 확인한다는 것입니다.

역방향 링크를 빠뜨린 삽입 실패

A와 C 사이에 B를 넣으면서 B의 prev·next와 A의 next까지 연결하고 C의 prev 갱신을 빠뜨리면, 앞에서 뒤로는 A, B, C가 보입니다.

그러나 꼬리 노드에서 prev를 따라가면 C 다음에 A가 나타나 B가 사라집니다.

정방향 출력만 검사한 구현이 통과하는 전형적인 반쪽 연결입니다.

lab/BrokenPrevLinkFailure.java

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

새 Node의 두 참조만 설정하고 다음 노드의 prev를 바꾸지 않았습니다.

양방향 목록에서는 next가 null이 아닌 노드의 node.next.prev == node, prev가 null이 아닌 노드의 node.prev.next == node가 성립해야 합니다.

한 방향 출력 성공은 충분한 검증이 아닙니다.

A의 참조: 참조 상태: prev = null, next = B
B의 참조: 참조 상태: prev = A, next = C
C의 참조: 참조 상태: prev = A (B가 아님), next = null
관찰한 순서: 참조 상태:
next: A → B → C → null
prev: C → A → null (B를 건너뜀)

head·tail·Node가 함께 지키는 규칙

빈 목록에서는 head와 꼬리 노드가 모두 null이고 size는 0입니다.
원소가 하나뿐이면 head와 꼬리 노드가 같은 Node를 가리킵니다.
head의 prev는 항상 null이며 꼬리 노드의 next도 항상 null입니다.
두 Node가 next로 인접하면 반대쪽 prev도 원래 Node를 가리킵니다.
head부터 센 개수와 꼬리 노드부터 센 개수는 모두 size와 같습니다.
인덱스 범위 검사에서 실패하면 위 참조와 size가 달라지지 않아야 합니다.

가까운 끝에서 노드 탐색

인덱스가 size의 앞쪽 절반이면 head에서 next를 따라가고, 뒤쪽 절반이면 꼬리 노드에서 prev를 따라갑니다.

양방향 연결이 get을 O(1)로 바꾸는 것은 아니지만 최대 이동 거리를 절반가량 줄입니다.

위치 탐색과 참조 재배선은 여전히 별도 비용입니다.

가운데 삽입은 다음 노드를 먼저 찾습니다.

이전 노드는 다음 노드의 prev에서 얻습니다.

새 Node가 두 이웃을 가리키게 한 다음 이전 노드의 next와 다음 노드의 prev를 새 Node로 교체합니다.

앞 삽입은 이전 노드가 null인 경우, 끝 삽입은 다음 노드가 null인 경우로 같은 원리를 확장할 수 있습니다.

삭제에서는 제거할 노드의 prev와 next를 먼저 보존합니다.

이전 노드가 없으면 head를 다음 노드로 바꾸고, 다음 노드가 없으면 꼬리 노드를 이전 노드로 바꿉니다.

남은 이웃을 서로 연결한 뒤 제거한 노드의 prev와 next를 null로 비웁니다.

src/DoublyLinkedListInvariant.java

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;
        }
    }
}

이 main은 중간 B를 삭제한 뒤 새 B를 재삽입하고, forward와 backward가 서로 반대 순서이며 links=true임을 보여 줍니다. 양끝·마지막 원소 삭제와 별도 순환 입력은 실행하지 않습니다.

검사 메서드는 정방향으로 걸으며 현재 prev가 직전에 방문한 Node인지 비교합니다.

마지막 방문 Node가 꼬리 노드이고 방문 수가 size인지도 함께 확인합니다.

중간 B의 삭제·재삽입과 최종 검사 범위
원문 호출·검사	탐색과 연결 변경	직후 상태·관찰
`addLast("A")` `addLast("C")`	두 번의 끝 추가. C가 새 `tail`이 됨	A ↔ C `head = A`, `tail = C`, `size = 2`
`add(1, "B")`	`node(1)`: `tail = C`에서 이동 0회 새 B를 A와 C 사이에 연결	A ↔ B ↔ C `size = 3`
`remove(1)`	`node(1)`: C에서 `prev` 1회 → B `A.next = C`, `C.prev = A` 제거한 B의 `prev = null`, `next = null`	A ↔ C `head = A`, `tail = C`, `size = 2` `removed=B` 출력
`add(1, "B")`	`tail = C`에서 이동 0회 값 B인 새 노드를 생성하여 재삽입	A ↔ B ↔ C `head = A`, `tail = C`, `size = 3` `A-B-C` `C-B-A`
`linksAreValid()`	정방향 A/B/C의 `prev`를 각각 `null`/A/B와 비교 마지막 방문 C = `tail`, 방문 수 3 = `size` `head.prev = null`, `tail.next = null`	`links=true` 이 main이 마지막에 만든 상태의 검사 결과

addLast("A") addLast("C"): 탐색과 연결 변경: 두 번의 끝 추가. C가 새 tail이 됨
직후 상태·관찰:
A ↔ C
head = A, tail = C, size = 2
add(1, "B"): 탐색과 연결 변경:
node(1): tail = C에서 이동 0회
새 B를 A와 C 사이에 연결
직후 상태·관찰:
A ↔ B ↔ C
size = 3
remove(1): 탐색과 연결 변경:
node(1): C에서 prev 1회 → B
A.next = C, C.prev = A
제거한 B의 prev = null, next = null
직후 상태·관찰:
A ↔ C
head = A, tail = C, size = 2
removed=B 출력
add(1, "B"): 탐색과 연결 변경:
tail = C에서 이동 0회
값 B인 새 노드를 생성하여 재삽입
직후 상태·관찰:
A ↔ B ↔ C
head = A, tail = C, size = 3
A-B-C
C-B-A
linksAreValid(): 탐색과 연결 변경:
정방향 A/B/C의 prev를 각각 null/A/B와 비교
마지막 방문 C = tail, 방문 수 3 = size
head.prev = null, tail.next = null
직후 상태·관찰:
links=true
이 main이 마지막에 만든 상태의 검사 결과

양끝 전이의 독립 검산

0개에서 1개로 갈 때 새 Node는 head이자 꼬리 노드입니다.

1개에서 0개로 갈 때 head와 꼬리 노드를 모두 null로 만들어야 합니다.

이 두 전이는 일반 중간 연결 공식에 null 이웃을 적용한 결과지만, 가장 많은 불변식이 동시에 바뀌므로 별도 실행 사례가 필요합니다.

두 원소 목록에서 head를 제거하면 새 head의 prev가 null이어야 합니다.

꼬리 노드를 제거하면 새 꼬리 노드의 next가 null이어야 합니다.

가운데 삭제만 확인하면 끝점에 남은 낡은 참조를 발견하지 못합니다.

최근 기록과 오래된 기록을 양끝에서 보기

게시글 저장소가 입력 순서는 head부터, 최근 순서는 꼬리 노드부터 제공한다고 가정합니다.

같은 Node를 두 번 저장하지 않고 prev 순회만으로 역순 보기를 만들 수 있습니다.

합계는 어느 방향으로 순회해도 같아야 합니다.

app/DoublyPostRepositoryCli.java

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));
        System.out.println("oldest=" + entries.getFirst().title());
        System.out.println("newest=" + entries.getLast().title());
        int total = entries.stream().mapToInt(Entry::viewCount).sum();
        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");
            }
        }
    }
}

표준 LinkedList를 사용한 CLI는 first와 last 요구를 명확히 보여 줍니다.

다만 실제 애플리케이션에서 index 조회가 많다면 양방향이라는 이유만으로 LinkedList를 택하지 않습니다.

오래된 기록과 최근 기록을 모두 O(1)로 읽는 요구가 충분히 중요한지 작업 부하로 확인합니다.

양방향 구조 선택표

질문	측정 대상	판단
양끝 원소 접근이 잦은가	getFirst·getLast 호출	`head`·꼬리 노드 가치 확인
`index` 조회가 주 경로인가	평균 조회 위치	ArrayList 우선 검토
`Node` 참조를 보유하는가	반복자 내부 변경	재배선 이점 가능
메모리가 민감한가	원소당 `prev`·`next` 비용	배열 구조와 비교

양방향 링크는 뒤로 이동할 수 있는 기능을 얻는 대신 원소마다 참조 하나가 더 필요하고 변경 코드도 복잡해집니다.

필요 없는 역순 탐색을 위해 유지하면 버그 면적만 늘어납니다.

Deque 요구라면 표준 ArrayDeque도 다음 장에서 비교합니다.

연습 문제

A와 C 사이에 B를 넣으세요.

A.next, B.prev, B.next, C.prev 네 참조가 모두 올바른지 boolean 하나로 출력합니다.

정답과 해설

기존 A-C 연결을 새 Node의 양쪽에 보존한 뒤 두 이웃이 B를 가리키게 합니다.

정방향 문자열만 비교하지 않고 참조 동일성을 직접 검사합니다.

exercise/DoublyLinkRepairSolution.java

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입니다.

검사하는 네 참조 관계 중 하나라도 성립하지 않으면 false가 됩니다.

제거 연습에서는 같은 방식으로 남은 두 이웃의 상호 참조와 제거한 노드의 null 정리를 검사할 수 있습니다.

양방향 목록 검증 기준

head의 prev와 꼬리 노드의 next는 언제나 null이어야 합니다.

인접 Node의 next·prev는 서로를 가리켜야 하며 정방향과 역방향 방문 수가 모두 size와 같아야 합니다.

빈 상태 전이와 한 원소 상태 전이를 별도로 실행한 뒤 이 조건이 유지되면 양방향 구현의 핵심 규칙을 충족합니다.

이 페이지의 목차