CS 공부 & 면접 대비 0x04 [자료구조] : 원형 연결 리스트를 확인하는 방법

원형 연결 리스트를 확인하는 방법: 두 포인터 활용

---

질문

원형 연결 리스트인지 확인하려면 어떻게 해야 하나요?

---

답변

원형 연결 리스트인지 확인하려면 투 포인터(Two Pointer) 기법을 사용할 수 있습니다.

• 한 포인터는 **한 칸씩 이동(slow pointer)**하고,
• 다른 포인터는 **두 칸씩 이동(fast pointer)**합니다.
  이동을 반복하다가 두 포인터가 같은 노드에서 만나게 된다면, 해당 연결 리스트는 원형임을 확인할 수 있습니다.

---

질문과 답변에 대한 설명

1. 원형 연결 리스트란?

원형 연결 리스트는 마지막 노드가 다시 처음 노드를 가리키는 연결 리스트입니다.

• 일반 연결 리스트의 끝은 None 또는 null로 표시되지만, 원형 연결 리스트는 끝이 없고 계속 순환합니다.
• 예: 노드 A → 노드 B → 노드 C → 다시 노드 A

원형 연결 리스트는 큐와 같은 자료구조 구현에 사용되며, 원소를 순환하며 처리할 때 유용합니다.

---

2. 원형 연결 리스트 확인 알고리즘

이 알고리즘은 두 포인터를 사용하여 원형 여부를 확인합니다:

• 느린 포인터(slow): 한 번에 한 칸씩 이동.
• 빠른 포인터(fast): 한 번에 두 칸씩 이동.

작동 원리:

1. 두 포인터를 리스트의 **헤드(head)**에 배치합니다.
2. 두 포인터를 각각 한 칸, 두 칸씩 이동시킵니다.
3. 만약 두 포인터가 만난다면, 리스트가 원형입니다.
4. 빠른 포인터가 None에 도달하면 리스트는 원형이 아닙니다.

이 방법은 Floyd's Cycle Detection Algorithm으로 알려져 있습니다.

---

3. Python 코드 예시

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def add(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # 원형 연결 리스트 확인 함수
    def is_circular(self):
        if not self.head:
            return False
        
        slow = self.head
        fast = self.head

        while fast and fast.next:
            slow = slow.next           # 한 칸 이동
            fast = fast.next.next      # 두 칸 이동

            if slow == fast:           # 두 포인터가 만난다면 원형
                return True
        
        return False                   # 빠른 포인터가 None이면 원형 아님

# 원형 연결 리스트 생성 및 확인
ll = LinkedList()
ll.add(3)
ll.add(2)
ll.add(1)

# 원형으로 만들기
ll.head.next.next.next = ll.head

print("원형 연결 리스트인가?", ll.is_circular())  # Output: True

---

4. 이 방법의 시간 및 공간 복잡도

• 시간 복잡도: O(n)
  리스트를 한 번만 순회하며, 빠른 포인터가 리스트 끝에 도달하거나 사이클을 발견합니다.
• 공간 복잡도: O(1)
  추가 메모리 없이 포인터 두 개만 사용합니다.

---

5. 원형 연결 리스트를 처리할 때 주의할 점

• 무한 루프 방지: 원형 연결 리스트를 순회할 때, 종료 조건을 명확히 지정하지 않으면 무한 루프에 빠질 수 있습니다.
• 실제 사용 사례:
  • 라운드 로빈 스케줄링: 프로세스 관리에서 순환적으로 작업을 처리.
  • 데이터 스트림 처리: 연속적인 데이터를 순환하며 처리.

---

결론

원형 연결 리스트인지 확인하는 문제는 효율적인 알고리즘 설계를 배우기에 좋은 예제입니다.

• 두 포인터를 사용한 방법은 빠르고 간단하며, 원형 여부를 O(n) 시간 안에 확인할 수 있습니다.
• Floyd's Cycle Detection Algorithm은 연결 리스트에서 사이클 확인 외에도 다양한 문제에 적용할 수 있는 기본적인 알고리즘입니다.