환형 연결 리스트

환형 연결 리스트(Circular Linked List)

 

단순 연결 리스트와 차이점 :

 - 구조 : 같은 노드 구조이나 연결 리스트의 제일 마지막 노드는 가장 처음의 노드를 가리키고 있다는 것이다.

   

    이로 인해, 연결 리스트는 머리가 꼬리를 뱀모양으로 둥근 모양을 하게 된다.

 

 - 조작함수 : 환형 연결 리스트는 tail이라는 개념이 없다.

 

장   점	단   점
임의의 노드로부터 모든 노드로의 접근이 용이하다. 리스트에 노드를 삽입하거나 삭제할 때 노드 수에 관계없이 거의 일정한 시간이 소요되므로, 노드의 삽입과 삭제 연산이 편리하다. 리스트의 결합(combining), 분리(splitting) 작업을 효율적으로 수행할 수 있다.	리스트를 구성하는 특정 노드를 검색하고자 할 때 잘못하면 무한 루프(infinite loop)에 빠질 가능성이 있으므로, 검색을 끝낼 수 있는 노드가 존재하여야 하며 이런 목적으로 추가된 노드를 HEAD노드라고 한다.

 

요셉의 문제(Joseph's Problem)