[List] 원형 연결 리스트, Circular Linked List

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 원형 연결 리스트 (Circular Linked List)

• 마지막 노드가 첫 노드와 연결된 단순 연결 리스트
• 원형 연결 리스트에서는 마지막 노드의 레퍼런스가 저장된 Last가 단순 연결 리스트의 Head와 같은 역할
• 마지막 노드와 첫 노드를 O(1)에 방문할 수 있다는 장점
• 리스트가 Empty가 아니면 어떤 노드도 None 레퍼런스를 가지고 있지 않으므로 프로그램에서 None 조건을 검사하지 않아도 되는 장점
• 반대 방향으로 노드들을 방문하기 쉽지 않으며, 무한 루프가 발생할 수 있음을 유의

 

- 수행 시간

• 탐색은 연결 리스트의 노드들을 Last로부터 순차적으로 방문해야 하므로 O(n) 소요
• 삽입과 삭제는 각각 O(1) 개의 레퍼런스만을 갱신하므로 O(1) 소요 (단, Insert after나 Delete after의 경우에 특정 노드의 레퍼런스가 주어지지 않으면 Head로부터 노드를 찾기 위하여 탐색을 수행하므로 O(n) 소요)