Circular Linked List

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

원형 연결 리스트는 마지막 next 포인터가 연결 리스트의 노드를 가리키는 연결 리스트입니다.

원형 연결 리스트의 마지막 next 포인터가 head를 가리키는지 확인하는 방법은 다음과 같습니다.

• head에서 시작하여 t==null이 될 때까지 반복한다면, 시간복잡도는 $O(n)$ 입니다.
• tail 포인터를 사용할 경우, 시간복잡도는 $O(1)$ 입니다.

마지막 next 포인터가 임의의 노드를 가리킨다면 확인하는 방법은 다음과 같습니다.

• tail에서 시작하여 tail 포인터가 다시 나타나는지 확인합니다. 시간복잡도는 $O(n)$ 입니다.
• 임시 포인터 2개를 사용하여 시작점을 잡고 currentSize만큼 떨어진 노드까지 확인한 후 시작점을 다음으로 옮겨 같은 노드가 나타날 때까지 반복합니다. 시간복잡도는 $O(n^2)$ 입니다.