[자료구조 리스트] 원형 연결 리스트(Circular Linked List)

  원형 연결 리스트(Circular Linked List)란 마지막 노드가 첫 노드와 연결된 단순 연결 리스트입니다. 마지막 노드의 레퍼런스가 저장된 last가 단순 연결 리스트의 head와 유사한 역할을 합니다.

  여러 사람이 차례로 돌아가며 하는 게임을 구현하는 데 적합한 자료구조이며, 많은 사용자가 동시에 사용하는 컴퓨터에서 cpu 시간을 분할하여 작업에 할당하는 운영체제에도 쓰입니다. 이항 힙이나 피보나치 힙과 같은 우선순위 큐를 구현하는 데에도 원형 연결 리스트가 부분적으로 사용됩니다.

  삽입이나 삭제 연산 각각 상수 개의 레퍼런스를 갱신하므로 O(1)시간에 수행됩니다. 탐색 연산은 단순 연결 리스트의 탐색과 같이 last로부터 노드들을 순차적으로 탐색해야 하므로 O(n) 시간이 소요됩니다.

 

  원형 연결 리스트의 장단점

• 장점
  • 마지막 노드를 O(1) 시간에 접근할 수 있음
• 단점
  • 반대 방향으로 노드들을 방문하기 쉽지 않음
  • 무한 루프가 발생할 수 있음

 

  ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.