양방향 연결 목록
`head`와 꼬리 노드 양쪽에서 탐색하고 삽입·삭제 뒤 `prev`와 `next`가 서로를 가리키는지 확인합니다.
단방향 목록은 이전 Node를 찾으려면 head에서 다시 걸어야 합니다.
양방향 목록은 각 Node에 prev와 next를 함께 저장하고 head·꼬리 노드 두 끝점을 관리합니다.
탐색 방향은 빨라질 수 있지만 연결 하나를 바꿀 때 맞춰야 할 참조가 늘어납니다.
이 절의 기준은 “정방향으로 이어진다”가 아니라 모든 인접 쌍이 양쪽에서 서로를 확인한다는 것입니다.
역방향 링크를 빠뜨린 삽입 실패
A와 C 사이에 B를 넣으면서 next만 연결하면 앞에서 뒤로는 A, B, C가 보입니다.
그러나 꼬리 노드에서 prev를 따라가면 C 다음에 A가 나타나 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새 Node의 두 참조만 설정하고 다음 노드의 prev를 바꾸지 않았습니다.
양방향 목록에서는 `node.next.prev == node`와 `node.prev.next == node`가 가능한 모든 Node에서 성립해야 합니다.
한 방향 출력 성공은 충분한 검증이 아닙니다.
head·tail·Node가 함께 지키는 규칙
- 빈 목록에서는
head와 꼬리 노드가 모두null이고size는 0입니다. - 원소가 하나뿐이면
head와 꼬리 노드가 같은Node를 가리킵니다. head의prev는 항상null이며 꼬리 노드의next도 항상null입니다.- 두
Node가next로 인접하면 반대쪽prev도 원래Node를 가리킵니다. head부터 센 개수와 꼬리 노드부터 센 개수는 모두size와 같습니다.- 구조 변경에 실패하면 위 여섯 값 중 어느 것도 달라지지 않습니다.
가까운 끝에서 노드 탐색
인덱스가 size의 앞쪽 절반이면 head에서 next를 따라가고, 뒤쪽 절반이면 꼬리 노드에서 prev를 따라갑니다.
양방향 연결이 get을 O(1)로 바꾸는 것은 아니지만 최대 이동 거리를 절반가량 줄입니다.
위치 탐색과 참조 재배선은 여전히 별도 비용입니다.
가운데 삽입은 다음 노드를 먼저 찾습니다.
이전 노드는 다음 노드의 prev에서 얻습니다.
새 Node가 두 이웃을 가리키게 한 다음 이전 노드의 next와 다음 노드의 prev를 새 Node로 교체합니다.
앞 삽입은 이전 노드가 null인 경우, 끝 삽입은 다음 노드가 null인 경우로 같은 원리를 확장할 수 있습니다.
삭제에서는 제거할 노드의 prev와 next를 먼저 보존합니다.
이전 노드가 없으면 head를 다음 노드로 바꾸고, 다음 노드가 없으면 꼬리 노드를 이전 노드로 바꿉니다.
남은 이웃을 서로 연결한 뒤 제거한 노드의 prev와 next를 null로 비웁니다.
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;
}
}
}실행은 앞으로와 backward가 서로 반대 순서이고 links=true임을 보여 줍니다.
검사 메서드는 정방향으로 걸으며 현재 prev가 직전에 방문한 Node인지 비교합니다.
마지막 방문 Node가 꼬리 노드이고 방문 수가 size인지도 함께 확인합니다.
양끝 전이의 독립 검산
0개에서 1개로 갈 때 새 Node는 head이자 꼬리 노드입니다.
1개에서 0개로 갈 때 head와 꼬리 노드를 모두 null로 만들어야 합니다.
이 두 전이는 일반 중간 연결 공식에 null 이웃을 적용한 결과지만, 가장 많은 불변식이 동시에 바뀌므로 별도 실행 사례가 필요합니다.
두 원소 목록에서 head를 제거하면 새 head의 prev가 null이어야 합니다.
꼬리 노드를 제거하면 새 꼬리 노드의 next가 null이어야 합니다.
가운데 삭제만 확인하면 끝점에 남은 낡은 참조를 발견하지 못합니다.
최근 기록과 오래된 기록을 양끝에서 보기
Study Log가 입력 순서는 head부터, 최근 순서는 꼬리 노드부터 제공한다고 가정합니다.
같은 Node를 두 번 저장하지 않고 prev 순회만으로 역순 보기를 만들 수 있습니다.
합계는 어느 방향으로 순회해도 같아야 합니다.
import java.util.LinkedList;
public final class DoublyStudyLogCli {
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().topic());
System.out.println("newest=" + entries.getLast().topic());
int total = entries.stream().mapToInt(Entry::minutes).sum();
System.out.println("total=" + total);
}
private record Entry(String topic, int minutes) {
private Entry {
if (topic == null || topic.isBlank() || minutes <= 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를 가리키게 합니다.
정방향 문자열만 비교하지 않고 참조 동일성을 직접 검사합니다.
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와 같아야 합니다.
빈 상태 전이와 한 원소 상태 전이를 별도로 실행한 뒤 이 조건이 유지되면 양방향 구현의 핵심 규칙을 충족합니다.