원형 이중 연결 리스트란?
원형 이중 연결 리스트(Circular Doubly Linked List)는 일반적인 이중 연결 리스트를 변형한 자료구조입니다. 일반적인 이중 연결 리스트에서는 마지막 노드의 next 포인터가 null을 가리키지만, 원형 이중 연결 리스트에서는 마지막 노드의 next 포인터가 첫 번째 노드를 가리키고, 반대로 첫 번째 노드의 prev 포인터가 마지막 노드를 가리킵니다. 그 결과 리스트가 양방향으로 순환하는 원형 구조를 갖게 됩니다.
이러한 구조 덕분에 어떤 노드에서 출발하더라도 양쪽 방향 모두로 끝없이 순회할 수 있으며, 첫 번째 노드와 마지막 노드 사이를 상수 시간(O(1))에 오갈 수 있다는 장점이 있습니다.
삽입과 삭제 연산
원형 이중 연결 리스트에서의 삽입과 삭제는 다른 연결 리스트와 기본적으로 동일한 방식으로 수행됩니다. 핵심 차이점은 리스트의 양끝에서 연산을 수행할 때 마지막 링크(last link)를 정확히 추적하고 갱신해야 한다는 점입니다.
- 삽입 시: 새 노드의 prev와 next 포인터를 설정한 뒤, 인접 노드들의 포인터도 함께 업데이트해야 순환이 유지됩니다.
- 삭제 시: 삭제 대상 노드의 앞뒤 노드가 서로를 가리키도록 포인터를 재연결하고, 삭제된 노드가 헤드나 테일이었다면 해당 참조도 갱신해야 합니다.
포인터 갱신 순서를 잘못 처리하면 순환 고리가 끊어질 수 있으므로, 특히 경계 조건(노드가 하나뿐인 경우, 빈 리스트인 경우 등)을 꼼꼼하게 확인하는 것이 중요합니다.
구현 방법
JavaScript로 원형 이중 연결 리스트를 직접 구현해 보고 싶다면, 원형 연결 리스트 알고리즘(Circular Linked List Algorithm)을 가이드 삼아 단계별로 따라 해 보는 것을 추천합니다. 노드 클래스(Node)와 리스트 클래스를 정의하고, 삽입(insert), 삭제(delete), 순회(traverse) 메서드를 하나씩 추가하면서 동작 원리를 익힐 수 있습니다.
주요 활용 사례
원형 이중 연결 리스트는 실제로도 다양한 곳에서 활용됩니다. 음악 플레이어의 반복 재생 목록, 운영체제의 라운드 로빈(Round-Robin) CPU 스케줄링, 이미지 캐러셀과 같은 UI 컴포넌트 등 끝없이 순환하는 데이터 흐름이 필요한 경우에 적합합니다.