이중 연결리스트

5 min read

이중 연결리스트는 각 노드가 다음 노드뿐 아니라 이전 노드도 함께 가리키는 구조다. 단일 연결리스트가 한 방향으로만 이동할 수 있다면, 이중 연결리스트는 앞뒤로 모두 이동할 수 있다.

null <- [prev | data | next] <-> [prev | data | next] <-> [prev | data | next] -> null

포인터가 하나 더 들어가므로 메모리 사용량과 구현 복잡도는 늘어난다. 대신 특정 노드를 알고 있을 때 그 노드를 지우거나 앞뒤로 재배치하기가 쉬워진다. 단일 연결리스트에서는 삭제할 때 이전 노드를 찾아야 하지만, 이중 연결리스트는 노드 안에 prev가 있으므로 바로 양쪽 연결을 바꿀 수 있다.

void delete(Node node) {
    if (node.prev != null) {
        node.prev.next = node.next;
    } else {
        head = node.next;
    }
 
    if (node.next != null) {
        node.next.prev = node.prev;
    } else {
        tail = node.prev;
    }
}

단일 연결리스트와 무엇이 다를까

단일 연결리스트는 구조가 단순하고 노드당 포인터가 하나만 필요하다. 하지만 역방향으로 이동할 수 없고, 특정 노드를 삭제하려면 이전 노드를 따로 찾아야 한다. 이중 연결리스트는 노드당 prev와 next를 모두 저장하므로 더 무겁지만, 양방향 이동과 O(1) 삭제가 가능하다.

이 차이는 LRU 캐시 같은 구조에서 중요해진다. 캐시에서 어떤 항목이 조회되면 그 항목을 “가장 최근에 사용한 위치”로 옮겨야 한다. 이때 HashMap으로 노드를 O(1)에 찾고, 이중 연결리스트로 노드를 O(1)에 떼어내 다시 붙이면 전체 연산을 빠르게 유지할 수 있다.

Java LinkedList도 이중 연결리스트다

Java의 LinkedList는 이중 연결리스트 기반이고, Deque 인터페이스도 구현한다. 그래서 앞뒤로 넣고 빼는 작업은 잘 맞는다.

LinkedList<Integer> list = new LinkedList<>();
 
list.addFirst(1);
list.addLast(2);
list.removeFirst();
list.removeLast();

하지만 get(index)가 빠른 것은 아니다. 내부적으로 앞에서 시작할지 뒤에서 시작할지 정도는 최적화할 수 있지만, 결국 노드를 따라 이동해야 하므로 O(n)이다. 그래서 단순히 “중간 삽입/삭제가 많다”는 이유만으로 LinkedList를 고르면 안 된다. 중간 위치를 찾는 비용이 더 클 수 있기 때문이다.

어울리는 상황

이중 연결리스트는 앞뒤 이동이 모두 필요하거나, 노드 참조를 들고 순서를 자주 바꾸는 구조에 잘 맞는다. LRU 캐시, 브라우저 히스토리, 음악 플레이어의 이전/다음 이동 같은 예시가 대표적이다.

반대로 데이터 전체를 순서대로 훑거나 인덱스로 접근하는 일이 많다면 동적 배열이 더 단순하고 빠를 가능성이 높다. 연결리스트를 선택할 때는 포인터 조작이 만들어주는 이득이 캐시 효율과 메모리 오버헤드 손실보다 큰지 봐야 한다.

면접에서 말할 포인트

이중 연결리스트는 prev와 next를 모두 저장하므로 양방향 순회와 특정 노드 삭제가 쉽다. 단일 연결리스트보다 메모리를 더 쓰고 구현도 복잡하지만, 노드 참조를 알고 있을 때 삽입/삭제와 순서 재배치가 O(1)에 가능하다. 다만 인덱스 접근은 여전히 O(n)이므로 ArrayList를 대체하는 만능 구조는 아니다.

Backlinks