단방향 연결 리스트(Singly Linked List)는 각 노드가 다음 노드(next)만을 참조하기 때문에, 이전 노드로 역방향 탐색이 불가능하다는 한계가 있다. 이를 해결하기 위해 고안된 구조가 이중 연결 리스트(Doubly Linked List)이다. 이중 연결 리스트는 각 노드가 이전 노드(prev)와 다음 노드(next)의 참조를 모두 가지며, 양방향으로 탐색이 가능한 형태의 자료구조이다
← DEQUEUE ENQUEUE →
+----+------+------+ +----+------+------+ +----+------+------+
|null| A(1) | Next |<---->|Prev| B(2) | Next |<---->|Prev| C(3) |null |
+----+------+------+ +----+------+------+ +----+------+------+
↑ ↑
HEAD TAIL
(FRONT) (REAR)
이처럼 각 노드가 양쪽으로 연결되어 있기 때문에, 리스트의 양 끝에서 삽입/삭제를 O(1)에 수행할 수 있다. 또한 prev 포인터를 통해 역방향 탐색이 가능하다
자바의 강타입 특성에 따라 제네릭을 적용하여, 타입 안정성을 유지하면서 여러 데이터 타입에 대응할 수 있도록 설계했다.
노드(Node) 클래스
/**
* 각 노드는 데이터와 다음/이전 노드에 대한 참조를 가진다
* @param<T> 노드에 저장될 데이터 타입
*/
public class Node<T> {
T data;
Node<T> next;
Node<T> prev; // 이전 노드를 가리키는 참조 변수 추가
public Node(T data, Node<T> next, Node<T> prev) {
this.data = data;
this.next = next;
this.prev = prev;
}
/**
* 데이터만으로 노드를 생성하는 생성자
* next와 prev는 기본적으로 null로 설정된다
*/
public Node(T data) {
this.data = data;
this.next = null;
this.prev = null;
}
public T getData() {
return data;
}
public Node<T> getNext() {
return next;
}
public Node<T> getPrev() {
return prev;
}
public void setData(T data) {
this.data = data;
}
public void setNext(Node<T> next) {
this.next = next;
}
public void setPrev(Node<T> prev) {
this.prev = prev;
}
@Override
public String toString() {
return "Node{data=" + data + '}';
}
}
이중 연결 리스트의 핵심 개념
- head: 첫 번째 노드를 가리킨다
- tail: 마지막 노드를 가리킨다
이중 연결 리스트 (DoublyLinkedList)
/**
* 이중 연결 리스트 클래스
* head와 tail 포인터를 유지하며, 각 노드는 이전/다음 노드에 대한 참조를 가진다
* 양방향 탐색과 효율적인 삽입/삭제를 지원한다
* @param<T> 리스트에 지정될 데이터 타입
*/
public class DoublyLinkedList<T> {
private Node<T> head;
private Node<T> tail;
private int size;
public DoublyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
/**
* 리스트의 모든 요소를 출력한다
* 형식: [data1, data2, data3, ...]
*/
public void printAll() {
Node<T> currentNode = this.head;
StringBuilder sb = new StringBuilder("[");
while (currentNode != null) {
sb.append(currentNode.data);
currentNode = currentNode.next;
if (currentNode != null) {
sb.append(", ");
}
}
sb.append("]");
System.out.println(sb.toString());
}
/**
* 지정된 인덱스에 데이터를 삽입한다
* 시간 복잡도: O(n) - 중간 삽입의 경우
*
* @param index 삽입할 위치 (0부터 size까지 가능)
* @param data 삽입할 데이터
* @throws IndexOutOfBoundsException 인덱스가 유효 범위를 벗어나는 경우
*/
public void insertAt(int index, T data) {
if (index > this.size || index < 0) {
String message = "인덱스 " + index + "는 유효한 범위 [" + 0 + ", " + this.size + "]를 벗어났습니다.";
throw new IndexOutOfBoundsException(message);
}
Node<T> newNode = new Node<>(data);
if (this.head == null) { // 리스트가 비어있을 때 (첫 노드 삽입)
// 새 노드가 유일한 노드가 되므로 head와 tail 모두 새 노드를 가리킴
this.head = newNode;
this.tail = newNode;
} else if (index == 0) { // head에 삽입하는 경우
// 예시: [1] → [2] → [3]에서 head에 [NEW] 삽입
// 결과: [NEW] → [1] → [2] → [3]
// 1단계: 새 노드의 next를 현재 head로 설정
newNode.next = this.head;
// 2단계: 현재 head의 prev를 새 노드로 설정 (역방향 연결)
this.head.prev = newNode;
// 3단계: head 포인터를 새 노드로 업데이트
this.head = newNode; // head는 이제 [NEW]를 가리킴
} else if (index == this.size) { // tail에 삽입하는 경우
// 예시: [1] → [2] → [3]에서 tail에 [NEW] 삽입
// 결과: [1] → [2] → [3] → [NEW]
// 1단계: 새 노드의 prev를 현재 tail로 설정
newNode.prev = this.tail;
// 2단계: 현재 tail의 next를 새 노드로 설정 (정방향 연결)
this.tail.next = newNode;
// 3단계: tail 포인터를 새 노드로 업데이트
this.tail = newNode; // tail은 이제 [NEW]를 가리킴
} else { // 그 외 중간 위치에 삽입하는 경우
// 예시: [1] → [2] → [3]에서 인덱스 1에 [NEW] 삽입
// 결과: [1] → [NEW] → [2] → [3]
// 1단계: 삽입할 위치의 이전 노드를 찾음
Node<T> currentNode = this.head;
for (int i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
// currentNode는 이제 [1]을 가리킴
// 2단계: 새 노드의 next를 currentNode의 다음 노드로 설정
newNode.next = currentNode.next; // [NEW] → [2]
// 3단계: 새 노드의 prev를 currentNode로 설정
newNode.prev = currentNode; // [1] ← [NEW]
// 4단계: currentNode의 다음 노드([2])의 prev를 새 노드로 설정 (역방향 연결)
currentNode.next.prev = newNode; // [NEW] ← [2]
// 5단계: currentNode의 next를 새 노드로 설정 (정방향 연결 완료)
currentNode.next = newNode; // [A] → [NEW]
// 최종 결과: [1] ↔ [NEW] ↔ [2] → [3]
}
this.size++;
}
/**
* 리스트의 마지막에 데이터를 삽입한다
* 시간 복잡도: O(1) - tail 포인터를 사용
*
* @param data 삽입할 데이터
*/
public void insertLast(T data) {
insertAt(this.size, data);
}
/**
* 지정된 인덱스의 노드를 제거한다
* 시간 복잡도: O(n) - 중간 삭제의 경우
*
* @param index 제거할 노드의 인덱스
* @return 제거된 노드
* @throws IndexOutOfBoundsException 인덱스가 유효 범위를 벗어나는 경우
*/
public Node<T> deleteAt(int index) {
if (index >= this.size || index < 0) {
String message = "인덱스 " + index + "는 유효한 범위 [" + 0 + ", " + (this.size - 1) + "]를 벗어났습니다. 제거할 수 없습니다.";
throw new IndexOutOfBoundsException(message);
}
Node<T> deletedNode;
if (this.size == 1) { // 데이터가 하나 남았을 때
// 리스트에 노드가 하나만 있으므로 head와 tail을 모두 null로 설정
deletedNode = this.head;
this.head = null;
this.tail = null;
} else if (index == 0) { // head를 제거하는 경우
// 예시: [1] → [2] → [3]에서 head [1] 제거
// 결과: [2] → [3]
// 1단계: 제거할 노드(현재 head)를 저장
deletedNode = this.head; // [1]을 저장
// 2단계: head를 다음 노드로 이동
this.head = this.head.next; // head는 이제 [2]를 가리킴
// 3단계: 새로운 head의 prev를 null로 설정 (첫 번째 노드이므로)
if (this.head != null) {
this.head.prev = null; // [2]의 prev = null
} else {
// head가 null이 되면 리스트가 비어있음
this.tail = null;
}
} else if (index == this.size - 1) { // tail을 제거하는 경우
// 예시: [1] → [2] → [3]에서 tail [3] 제거
// 결과: [1] → [2]
// 1단계: 제거할 노드(현재 tail)를 저장
deletedNode = this.tail; // [3]을 저장
// 2단계: tail을 이전 노드로 이동
this.tail = this.tail.prev; // tail은 이제 [2]를 가르킴
// 3단계: 새로운 tail의 next를 null로 설정 (마지막 노드이므로)
if (this.tail != null) {
this.tail.next = null; // [2]의 next = null
} else {
// tail이 null이 되면 리스트가 비어있음
this.head = null;
}
} else { // 중간 위치의 노드를 제거하는 경우
// 예시: [1] → [2] → [3] → [4]에서 인덱스 1의 [2] 제거
// 결과: [1] → [3] → [4]
// 1단계: 제거할 노드의 이전 노드를 찾음
Node<T> currentNode = this.head;
for (int i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
// currentNode는 이제 [1]를 가리킴
// 2단계: 제거할 노드를 저장 ([2])
deletedNode = currentNode.next; // [2]를 저장
// 3단계: currentNode의 next를 제거할 노드의 다음 노드로 설정
currentNode.next = deletedNode.next; // [1] → [3]
// 4단계: 제거할 노드의 다음 노드([C])의 prev를 currentNode로 설정 (역방향 연결)
deletedNode.next.prev = currentNode; // [1] ← [3]
// 최종 결과: [1] ↔ [3] → [4] (2가 제거됨)
}
this.size--;
return deletedNode;
}
/**
* 리스트의 마지막 노드를 제거한다
* 시간 복잡도: O(1) - tail 포인터를 사용
*
* @return 제거된 마지막 노드
* @throws IndexOutOfBoundsException 리스트가 비어있을 경우
*/
public Node<T> deleteLast() {
if (this.size == 0) {
throw new IndexOutOfBoundsException("리스트가 비어있어 제거할 노드가 없습니다.");
}
return deleteAt(this.size - 1);
}
/**
* 리스트의 첫 번째 노드를 제거한다
* 시간 복잡도: O(1) - head 포인터를 사용
*
* @return 제거된 첫 번째 노드
* @throws IndexOutOfBoundsException 리스트가 비어있을 경우
*/
public Node<T> deleteFirst() {
if (this.size == 0) {
throw new IndexOutOfBoundsException("리스트가 비어있어 제거할 노드가 없습니다.");
}
return deleteAt(0);
}
/**
* 지정된 인덱스의 노드를 반환한다
* 시간 복잡도: O(n)
*
* @param index 가져올 노드의 인덱스
* @return 해당 인덱스의 노드
* @throws IndexOutOfBoundsException 인덱스가 유효 범위를 벗어나는 경우
*/
public Node<T> getNodeAt(int index) {
if (index >= this.size || index < 0) {
String message = "인덱스 " + index + "는 유효한 범위 [" + 0 + ", " + (this.size - 1) + "]를 벗어났습니다.";
throw new IndexOutOfBoundsException(message);
}
Node<T> currentNode = this.head;
for (int i = 0; i < index; i++) {
currentNode = currentNode.next;
}
return currentNode;
}
public int getSize() {
return this.size;
}
public Node<T> getHead() {
return this.head;
}
public Node<T> getTail() {
return this.tail;
}
public void clear() {
this.head = null;
this.tail = null;
this.size = 0;
}
}
시간 복잡도 비교
| 연산 | 단방향 연결 리스트 | 이중 연결 리스트 |
|---|---|---|
| 맨 앞 삽입/삭제 | O(1) | O(1) |
| 맨 뒤 삽입/삭제 | O(n) | O(1) |
| 중간 삽입/삭제 | O(n) | O(n) |
| 탐색 | O(n) | O(n) |
| 역방향 탐색 | 불가능 | 가능 |
장점
- 앞뒤 방향 모드 탐색 가능
- tail 참조를 통해 뒤에서의 삽입/삭제가 O(1)
- 양방향 순회에 용이
단점
- prev 포인터로 인해 메모리 사용량 증가
- 삽입/삭제 시 포인터 관리가 더 복잡
- 실수로 참조 연결이 깨지면 디버깅이 어려움
활용 예시
- 브라우저의 ‘뒤로/앞으로’ 기능
- 미딜 플레이어의 이전/다음 트랙
- LRU Cache(최근 사용한 항목 관리)
- Undo/Redo 스택
이중 연결 리스트는 단순한 리스트 구조를 넘어, 양방향 탐색, O(1)끝 삽입/삭제, 노드 간 유연한 이동이 가능하게 한다. 이는 스택과 큐뿐 아니라 캐시, 로그 관리, 히스토리 관리 등 다양한 시룸 환경에서 매우 중요한 기초 자료구조이다