이중 연결리스트

6 min read

이중 연결리스트 (Doubly Linked List)

각 노드가 이전 노드와 다음 노드를 모두 가리키는 자료구조

구조

        +-------+    +-------+    +-------+
null <- | prev  | <- | prev  | <- | prev  |
        | data  |    | data  |    | data  |
        | next  | -> | next  | -> | next  | -> null
        +-------+    +-------+    +-------+
          head                       tail

노드 구조

class Node {
    int data;
    Node prev;  // 이전 노드
    Node next;  // 다음 노드
 
    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

단일 vs 이중 연결리스트

구분단일 연결리스트이중 연결리스트
포인터next만prev + next
메모리노드당 1포인터노드당 2포인터
역방향 탐색불가능 (O(n) 재탐색)가능 O(1)
삭제이전 노드 필요현재 노드만으로 가능
구현 복잡도단순복잡

핵심 연산

1. 삽입

맨 앞 삽입 - O(1)

void insertFirst(int data) {
    Node newNode = new Node(data);
 
    if (head == null) {
        head = tail = newNode;
    } else {
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }
}
Before:  head -> [A] <-> [B] <-> [C] <- tail

Insert X:
newNode.next = head (A)
head.prev = newNode
head = newNode

After:   head -> [X] <-> [A] <-> [B] <-> [C] <- tail

맨 뒤 삽입 - O(1)

void insertLast(int data) {
    Node newNode = new Node(data);
 
    if (tail == null) {
        head = tail = newNode;
    } else {
        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
    }
}

중간 삽입 (특정 노드 뒤) - O(1)

void insertAfter(Node target, int data) {
    if (target == null) return;
 
    Node newNode = new Node(data);
    newNode.prev = target;
    newNode.next = target.next;
 
    if (target.next != null) {
        target.next.prev = newNode;
    } else {
        tail = newNode;  // target이 tail이었음
    }
 
    target.next = newNode;
}

2. 삭제

특정 노드 삭제 - O(1)

이중 연결리스트의 가장 큰 장점!

void delete(Node target) {
    if (target == null) return;
 
    // 이전 노드의 next 수정
    if (target.prev != null) {
        target.prev.next = target.next;
    } else {
        head = target.next;  // target이 head였음
    }
 
    // 다음 노드의 prev 수정
    if (target.next != null) {
        target.next.prev = target.prev;
    } else {
        tail = target.prev;  // target이 tail이었음
    }
}
Before:  [A] <-> [B] <-> [C]
Delete B:

A.next = B.next (C)
C.prev = B.prev (A)

After:   [A] <-> [C]

3. 양방향 순회

// 정방향
void printForward() {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " -> ");
        current = current.next;
    }
}
 
// 역방향
void printBackward() {
    Node current = tail;
    while (current != null) {
        System.out.print(current.data + " -> ");
        current = current.prev;
    }
}

전체 구현

public class DoublyLinkedList {
    private Node head;
    private Node tail;
    private int size;
 
    public void addFirst(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }
 
    public void addLast(int data) {
        Node newNode = new Node(data);
        if (tail == null) {
            head = tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }
 
    public void removeFirst() {
        if (head == null) return;
 
        if (head == tail) {
            head = tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
        size--;
    }
 
    public void removeLast() {
        if (tail == null) return;
 
        if (head == tail) {
            head = tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
        size--;
    }
 
    // 인덱스로 접근 - 최적화: 가까운 쪽에서 시작
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
 
        Node current;
        if (index < size / 2) {
            // 앞에서 탐색
            current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
        } else {
            // 뒤에서 탐색
            current = tail;
            for (int i = size - 1; i > index; i--) {
                current = current.prev;
            }
        }
        return current.data;
    }
}

Java LinkedList

Java의 LinkedList는 이중 연결리스트로 구현되어 있다.

LinkedList<Integer> list = new LinkedList<>();
 
list.addFirst(1);   // O(1)
list.addLast(2);    // O(1)
list.removeFirst(); // O(1)
list.removeLast();  // O(1)
 
list.get(5);        // O(n) - 순차 탐색 필요
                    // 단, 중간 지점 기준 가까운 쪽에서 시작
 
// Deque로 활용
list.offerFirst(1);
list.offerLast(2);
list.pollFirst();
list.pollLast();

활용 예시

1. LRU 캐시 구현

// HashMap + DoublyLinkedList 조합
// - HashMap: O(1) 조회
// - DoublyLinkedList: O(1) 삽입/삭제, 순서 관리
 
class LRUCache {
    Map<Integer, Node> map;
    Node head, tail;  // Dummy nodes
    int capacity;
 
    // get: map에서 찾고, 맨 앞으로 이동
    // put: 새 노드 맨 앞 삽입, 용량 초과시 맨 뒤 삭제
}

2. 브라우저 히스토리

← [page1] <-> [page2] <-> [page3] →
                 ↑
              현재 위치

뒤로가기: current = current.prev
앞으로가기: current = current.next

3. 음악 플레이어

이전곡 ← [현재곡] → 다음곡

면접 포인트

  1. 단일 vs 이중 연결리스트 선택 기준은?

    • 역방향 탐색 필요 → 이중
    • 메모리 절약 중요 → 단일
    • 삭제 연산 빈번 → 이중 (O(1))

  2. Java LinkedList는 어떻게 구현되어 있나?

    • 이중 연결리스트
    • first, last 포인터 유지
    • Deque 인터페이스도 구현

  3. LRU 캐시에서 왜 이중 연결리스트를 사용하나?

    • 특정 노드 삭제가 O(1)
    • 순서 유지하면서 빠른 재배치

  4. get(index) 최적화 방법은?

    • index가 size/2보다 작으면 head에서
    • 크면 tail에서 탐색 시작

Backlinks