[TIL] 자료구조 - 원형 연결 리스트

※ 원형 연결 리스트

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

 

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

head 에서 시작하여 t == null 이 될 때까지 반복한다면, 시간복잡도는 O(n) 이다.

tail 포인터를 사용하는 경우, 시간복잡도는 O(1) 이다.

 

그리고 next 포인터가 임의의 노드를 가리키는 경우 확인하는 방법은 다음과 같다.

tail에서 시작해 tail 포인터가 다시 나타나는지 확인한다. 시간복잡도는 O(n)이다.

임시 포인터 2개를 사용해 시작점을 잡고 currentSize 만큼 떨어진 노드를 확인하고 시작점을 다음으로 옮겨 동일한 노드가 나올때까지 반복하는데 이 시간복잡도는 O(n^2)이다.