이 글에서는 LinkedList에서 루프(Loop, 사이클)를 감지하는 방법을 자세히 알아보겠습니다.
연결 리스트(Linked List)는 여러 데이터 구조가 링크(link)로 서로 연결된 일련의 구조입니다. 각 노드는 데이터를 담고 있으며, 다음 노드를 가리키는 참조를 포함합니다. 만약 리스트의 어딘가에서 노드가 이전 노드를 다시 가리킨다면, 순회가 끝나지 않는 '루프'가 발생합니다.
문제 상황
예를 들어 다음과 같이 프로그램을 실행했을 때,
Run the program
다음과 같은 결과를 얻는 것이 목표입니다.
The loop exists in the linked list
알고리즘: 단계별 접근
Step 1 - START Step 2 - 필요한 변수를 선언한다. Step 3 - 값을 정의한다. Step 4 - 관련 멤버를 포함하는 클래스를 정의한다. Step 5 - 클래스의 인스턴스를 생성하고 노드를 초기화한다. Step 6 - 루프 여부를 확인하는 함수를 정의한다. Step 7 - 이를 위해 HashSet을 생성하고 최상위(head) 노드부터 요소를 추가한다. Step 8 - 매 반복마다 노드를 다음 요소로 이동시킨다. Step 9 - main 메서드에서 인스턴스를 생성하고 'push' 메서드로 리스트에 요소를 추가한다. Step 10 - 'check_loop' 메서드를 호출하고 결과 메시지를 콘솔에 출력한다. Step 11 - STOP
루프 감지에는 대표적으로 두 가지 방법이 있습니다. 첫 번째는 HashSet을 이용한 방식, 두 번째는 플로이드의 순환 감지 알고리즘(Floyd's Cycle Detection, 투 포인터 방식)입니다. 각각 살펴보겠습니다.
예제 1 — HashSet을 이용한 루프 감지
첫 번째 방법은 리스트를 순회하면서 지나온 노드들을 HashSet에 저장하는 방식입니다. 이미 방문한 노드를 다시 만난다면 루프가 존재한다는 의미입니다.
import java.util.*;
public class Demo {
static Node head;
static class Node {
int data;
Node next;
Node(int d){
data = d;
next = null;
}
}
static public void push(int new_data){
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
static boolean check_loop(Node head){
HashSet<Node> s = new HashSet<Node>();
while (head != null) {
if (s.contains(head))
return true;
s.add(head);
head = head.next;
}
return false;
}
public static void main(String[] args){
System.out.println("The required packages have been imported");
Demo input_list = new Demo();
input_list.push(45);
input_list.push(60);
input_list.push(75);
input_list.push(90);
// 마지막 노드가 head를 가리키도록 하여 루프 생성
input_list.head.next.next.next.next = input_list.head;
if (check_loop(head))
System.out.println("The loop exists in the linked list");
else
System.out.println("The loop doesnot exists in the linked list");
}
}출력 결과
The required packages have been imported The loop exists in the linked list
동작 원리: check_loop 메서드는 head부터 시작해 한 노드씩 이동하며, 각 노드를 HashSet에 추가합니다. 만약 contains() 호출 시 이미 존재하는 노드라면, 그 노드를 두 번 방문한 것이므로 true(루프 존재)를 반환합니다. 끝까지 순회해도 중복이 없다면 false를 반환합니다. 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다.
예제 2 — 플로이드의 순환 감지 알고리즘 (투 포인터)
두 번째 방법은 객체 지향 프로그래밍(OOP) 스타일로 연산을 함수에 캡슐화하고, 느린 포인터(slow)와 빠른 포인터(fast) 두 개를 사용합니다. 느린 포인터는 한 칸씩, 빠른 포인터는 두 칸씩 이동하며, 두 포인터가 만나면 루프가 존재하는 것입니다. 흔히 '거북이와 토끼 알고리즘'이라고도 불립니다.
public class Demo {
Node head;
static class Node {
int value;
Node next;
Node(int d) {
value = d;
next = null;
}
}
public boolean check_loop() {
Node first_node = head; // 빠른 포인터
Node second_node = head; // 느린 포인터
while(first_node != null && first_node.next != null) {
first_node = first_node.next.next;
second_node = second_node.next;
if(first_node == second_node) {
return true;
}
}
return false;
}
public static void main(String[] args) {
Demo input_list = new Demo();
input_list.head = new Node(45);
Node second_node = new Node(60);
Node third_node = new Node(75);
Node fourth_node = new Node(90);
input_list.head.next = second_node;
second_node.next = third_node;
third_node.next = fourth_node;
fourth_node.next = second_node; // 루프 생성
System.out.print("The elements of the linked list are: ");
int i = 1;
while (i <= 4) {
System.out.print(input_list.head.value + " ");
input_list.head = input_list.head.next;
i++;
}
boolean loop = input_list.check_loop();
if(loop) {
System.out.println("\nThere is a loop in the linked list.");
}
else {
System.out.println("\nThere is no loop in the linked list.");
}
}
}출력 결과
The required packages have been imported The loop exists in the linked list
동작 원리: 빠른 포인터(first_node)는 두 칸씩, 느린 포인터(second_node)는 한 칸씩 앞으로 이동합니다. 리스트에 루프가 있다면 빠른 포인터는 결국 느린 포인터를 따라잡아 두 포인터가 같은 노드에서 만나게 되고, 이때 true를 반환합니다. 루프가 없다면 빠른 포인터가 먼저 리스트의 끝(null)에 도달하므로 false를 반환합니다.
두 방식 비교
HashSet 방식은 직관적이고 구현이 간단하지만, 모든 방문 노드를 저장해야 하므로 O(n)의 추가 메모리가 필요합니다. 반면 플로이드 알고리즘은 포인터 두 개만 사용하므로 O(1)의 공간 복잡도로 루프를 감지할 수 있어, 메모리 효율이 중요한 환경에서 널리 사용됩니다.
이처럼 Java에서는 HashSet 또는 투 포인터 기법을 활용해 LinkedList 내부의 루프를 손쉽게 감지할 수 있습니다. 실무에서는 메모리 효율이 좋은 플로이드 알고리즘이 더 많이 활용되니, 두 방식 모두 익혀두면 큰 도움이 됩니다.