이중 연결 리스트 (Doubly Linked List)
쉽게 풀면
일반 연결 리스트가 한쪽 방향으로만 갈 수 있는 편도 기차라면, 이중 연결 리스트는 앞뒤로 자유롭게 오갈 수 있는 기차라고 볼 수 있습니다. 각 칸(노드)이 "다음 칸이 어디인지"뿐 아니라 "이전 칸이 어디인지"도 함께 기억하고 있기 때문에, 뒤에서 앞으로 거슬러 가거나 특정 노드를 삭제할 때 앞뒤를 다시 연결하는 작업이 훨씬 간단해집니다. 다만 노드마다 화살표(포인터)를 하나 더 저장해야 하므로 메모리는 조금 더 사용합니다.
왜 중요한가
이중 연결 리스트는 임의의 위치에서 노드를 즉시 삭제하거나 양방향으로 순회해야 하는 자료구조 문제에서 시간 복잡도를 크게 낮춰주기 때문에, 시스템 소프트웨어나 알고리즘 논문에서 효율적인 자료구조 설계의 기본 구성요소로 자주 등장합니다. 특히 캐시 정책, 실행취소(undo) 기능, 텍스트 편집기의 커서 이동처럼 "최근 사용 순서"나 "앞뒤 이동"이 핵심인 문제를 다룰 때, 이중 연결 리스트를 다른 자료구조와 결합한 설계가 성능 개선의 근거로 제시되는 경우가 많습니다.
논문에서는 이렇게 쓰입니다
이 문장은 "최근 사용 순서를 리스트의 양 끝으로 옮기거나 중간에서 바로 빼낼 수 있어야 하는데, 이때 이전 노드 정보까지 알고 있는 이중 연결 리스트를 쓰면 이런 삭제·이동 작업을 즉시 처리할 수 있다"는 뜻입니다.
편집기나 브라우저 히스토리처럼 사용자가 과거와 미래 상태를 오가야 하는 인터페이스 설계에서 이중 연결 리스트가 자연스러운 선택이 됨을 보여줍니다.
운영체제나 메모리 할당기 구현 논문에서도, 인접한 자원을 빠르게 참조하고 병합해야 하는 문제에 이중 연결 리스트가 활용됨을 보여줍니다.
조금 더 깊게 보면
실제 구현에서는 리스트의 맨 앞과 맨 뒤에 데이터를 담지 않는 더미(sentinel) 노드를 두어, 삽입·삭제 시 리스트가 비어 있는지 등을 매번 예외로 처리하지 않도록 코드를 단순화하는 기법이 흔히 쓰입니다. 또한 이중 연결 리스트는 각 방향 포인터를 저장하는 오버헤드가 있으므로, 무작위 접근이 중요하지 않고 순차 삽입·삭제 위주인 경우에만 배열 기반 구조 대신 선택하는 것이 일반적으로 권장됩니다. 캐시나 LRU 정책 논문에서는 이중 연결 리스트가 해시맵과 결합되어, 키로 노드를 즉시 찾고(O(1) 조회) 그 노드를 리스트 양 끝으로 옮기는(O(1) 이동) 두 연산을 함께 지원하는 형태로 자주 설계됩니다.
주의할 점
이중 연결 리스트는 연결 리스트보다 노드 하나당 저장 공간을 더 쓰고, 삽입·삭제 시 앞뒤 두 방향의 연결을 모두 갱신해야 하므로 구현이 조금 더 복잡합니다. 단순히 한 방향으로만 순회하면 되는 경우라면 굳이 이중 연결 리스트를 쓰지 않고 일반 연결 리스트로 충분한 경우가 많습니다.