연결 리스트에서 사이클(cycle), 즉 순환이 존재하는지 감지해야 하는 경우가 종종 있습니다. 이를 위해서는 먼저 연결 리스트에 노드를 추가하는 메서드와 특정 인덱스의 노드를 가져오는 메서드를 정의한 뒤, 두 개의 포인터를 활용해 사이클 여부를 검사하는 메서드를 구현하면 됩니다.
여기서 사용하는 핵심 기법은 플로이드의 순환 감지 알고리즘(Floyd's Cycle Detection Algorithm), 일명 '거북이와 토끼 알고리즘'입니다. 한 칸씩 이동하는 느린 포인터(slow pointer)와 두 칸씩 이동하는 빠른 포인터(fast pointer)를 동시에 출발시켰을 때, 리스트에 사이클이 있다면 두 포인터는 반드시 언젠가 같은 노드에서 만나게 됩니다.
아래는 전체 구현 예제입니다.
예제 코드
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList_structure:
def __init__(self):
self.head = None
self.last_node = None
def add_vals(self, data):
if self.last_node is None:
self.head = Node(data)
self.last_node = self.head
else:
self.last_node.next = Node(data)
self.last_node = self.last_node.next
def get_node_val(self, index):
curr = self.head
for i in range(index):
curr = curr.next
if curr is None:
return None
return curr
def check_cycle(my_list):
slow_val = my_list.head
fast_val = my_list.head
while (fast_val != None and fast_val.next != None):
slow_val = slow_val.next
fast_val = fast_val.next.next
if slow_val == fast_val:
return True
return False
my_linked_list = LinkedList_structure()
my_list = input('연결 리스트에 넣을 요소들을 입력하세요: ').split()
for elem in my_list:
my_linked_list.add_vals(int(elem))
my_len = len(my_list)
if my_len != 0:
vals = '0-' + str(my_len - 1)
last_ptr = input('마지막 노드가 가리킬 노드의 인덱스 [' + vals + ']를 입력하세요'
' (입력하지 않으면 None을 가리킵니다): ').strip()
if last_ptr == '':
my_linked_list.last_node.next = None
else:
last_ptr = my_linked_list.get_node_val(int(last_ptr))
my_linked_list.last_node.next = last_ptr
if check_cycle(my_linked_list):
print("이 연결 리스트에는 사이클이 존재합니다")
else:
print("이 연결 리스트에는 사이클이 없습니다")실행 결과
연결 리스트에 넣을 요소들을 입력하세요: 56 78 90 12 4 마지막 노드가 가리킬 노드의 인덱스 [0-4]를 입력하세요 (입력하지 않으면 None을 가리킵니다): 이 연결 리스트에는 사이클이 없습니다
코드 설명
'Node' 클래스: 각 노드는 데이터(
data)와 다음 노드를 가리키는 참조(next)를 가집니다.'LinkedList_structure' 클래스: 연결 리스트 자체를 나타내며, 첫 번째 노드인
head와 마지막 노드인last_node를 속성으로 가집니다.'add_vals' 메서드: 리스트 끝에 새로운 값을 추가합니다. 리스트가 비어 있으면 새 노드를 head로 지정하고, 그렇지 않으면 마지막 노드 뒤에 연결합니다.
'get_node_val' 메서드: 주어진 인덱스에 해당하는 노드를 반환합니다. 범위를 벗어나면
None을 반환합니다.'check_cycle' 함수: 느린 포인터는 한 칸씩, 빠른 포인터는 두 칸씩 이동시킵니다. 두 포인터가 같은 노드에서 만나면 사이클이 존재한다는 의미이므로
True를 반환하고, 빠른 포인터가 리스트 끝에 도달하면 사이클이 없으므로False를 반환합니다.사용자로부터 요소들을 입력받아 연결 리스트를 구성하고, 마지막 노드가 가리킬 노드의 인덱스를 지정할 수 있습니다. 아무것도 입력하지 않으면 마지막 노드는
None을 가리켜 정상적인 리스트가 됩니다.마지막으로
check_cycle함수를 호출해 결과를 콘솔에 출력합니다.
참고: 시간 복잡도
이 알고리즘은 시간 복잡도 O(n), 공간 복잡도 O(1)로 매우 효율적입니다. 별도의 집합(set)에 방문한 노드를 저장하는 방식(O(n) 추가 메모리)과 달리, 두 포인터만 사용하기 때문에 메모리 제약이 있는 환경에서도 유용하게 활용됩니다.