이중 연결 리스트란?
이중 연결 리스트(Doubly Linked List)는 모든 연산 측면에서 단일 연결 리스트(Singly Linked List)와 거의 동일하지만, 각 노드마다 하나의 추가 링크를 관리해야 한다는 점이 다릅니다. 단일 연결 리스트의 노드에는 next 링크만 존재하는 반면, 이중 연결 리스트의 노드에는 next(다음 노드)와 prev(이전 노드) 두 개의 링크가 있습니다.
이러한 양방향 구조 덕분에 리스트를 앞에서 뒤로, 뒤에서 앞으로 모두 순회할 수 있다는 장점이 있습니다. 반면 각 노드가 포인터를 하나 더 저장해야 하므로 메모리 사용량은 약간 증가합니다.
이중 연결 리스트의 구조
이중 연결 리스트는 일반적으로 다음과 같이 표현됩니다.
위 그림에서 확인할 수 있듯이, 각 노드는 데이터(data), 이전 노드를 가리키는 prev 포인터, 다음 노드를 가리키는 next 포인터로 구성됩니다. 첫 번째 노드(head)의 prev는 null을, 마지막 노드(tail)의 next는 null을 가리켜 리스트의 시작과 끝을 판별할 수 있습니다.
구현 시 주의사항
이중 연결 리스트 클래스를 구현할 때는 head뿐만 아니라 tail(마지막 요소)도 함께 추적해야 한다는 점에 유의해야 합니다. tail 참조를 유지하면 리스트 끝에 새 요소를 추가하는 작업을 O(1) 시간 복잡도로 처리할 수 있어 전체적인 성능이 크게 향상됩니다.