이 글에서는 단 한 번의 반복(single iteration)만으로 연결 리스트(LinkedList)의 중간 요소를 구하는 방법을 알아봅니다. Java의 java.util.LinkedList 클래스는 이중 연결 리스트(doubly-linked list)에서 기대할 수 있는 모든 연산을 지원하며, 인덱스를 기반으로 하는 연산은 지정된 인덱스에 더 가까운 쪽, 즉 리스트의 처음 또는 끝부터 탐색을 시작합니다.
핵심 원리: 두 포인터(Two Pointer) 기법
리스트의 전체 길이를 미리 알지 못한 상태에서 중간 요소를 찾으려면 두 개의 포인터를 활용하는 것이 가장 효과적입니다.
- 빠른 포인터(pointer_1) – 반복할 때마다 두 개의 노드를 앞으로 이동합니다.
- 느린 포인터(pointer_2) – 반복할 때마다 한 개의 노드를 앞으로 이동합니다.
빠른 포인터가 리스트의 끝에 도달하는 순간, 느린 포인터는 정확히 리스트의 중간에 위치하게 됩니다. 이 덕분에 리스트를 두 번 순회하지 않고도 단일 반복만으로 중간 요소를 얻을 수 있습니다.
아래는 그 동작 방식을 보여주는 예시입니다.
입력이 다음과 같다고 가정하면 −
입력 연결 리스트: 100 200 330
원하는 출력 결과는 다음과 같습니다 −
리스트의 중간 요소: 200
알고리즘
1단계 - 시작(START) 2단계 - input_list라는 이름의 LinkedList를 선언하고, head, first_node, second_node, pointer_1, pointer_2라는 다섯 개의 노드 객체를 선언합니다. 3단계 - 노드에 들어갈 값들을 정의합니다. 4단계 - while 루프를 사용해 연결 리스트를 순회하며, pointer_1.next가 null이 아닐 때까지 pointer_1과 pointer_2를 이동시켜 중간 요소를 찾습니다. 5단계 - pointer_2가 가리키는 값을 결과로 출력합니다. 6단계 - 종료(STOP)
예제 1: main 함수에서 모든 로직 처리하기
첫 번째 예제에서는 모든 연산을 하나의 'main' 함수 안에 함께 작성합니다.
public class LinkedList {
Node head;
static class Node {
int value;
Node next;
Node(int d) {
value = d;
next = null;
}
}
public static void main(String[] args) {
LinkedList input_list = new LinkedList();
input_list.head = new Node(100);
Node second_node = new Node(200);
Node third_node = new Node(330);
input_list.head.next = second_node;
second_node.next = third_node;
Node current_node = input_list.head;
System.out.print("The linked list is defined as: " );
while (current_node != null) {
System.out.print(current_node.value + " ");
current_node = current_node.next;
}
Node pointer_1 = input_list.head;
Node pointer_2 = input_list.head;
while (pointer_1.next != null) {
pointer_1 = pointer_1.next;
if(pointer_1.next !=null) {
pointer_1 = pointer_1.next;
pointer_2 = pointer_2.next;
}
}
System.out.println("\nThe middle element of the list is: " + pointer_2.value);
}
}
실행 결과
The linked list is defined as: 100 200 330 The middle element of the list is: 200
예제 2: 함수로 캡슐화한 객체 지향 방식
두 번째 예제에서는 중간 요소를 찾는 로직을 별도의 함수로 분리하여 객체 지향 프로그래밍(OOP) 스타일로 구현합니다. 이렇게 하면 코드의 재사용성과 가독성이 크게 향상됩니다.
public class LinkedList {
Node head;
static class Node {
int value;
Node next;
Node(int d) {
value = d;
next = null;
}
}
static void get_middle_item(LinkedList input_list){
Node pointer_1 = input_list.head;
Node pointer_2 = input_list.head;
while (pointer_1.next != null) {
pointer_1 = pointer_1.next;
if(pointer_1.next !=null) {
pointer_1 = pointer_1.next;
pointer_2 = pointer_2.next;
}
}
System.out.println("\nThe middle element of the list is: " + pointer_2.value);
}
public static void main(String[] args) {
LinkedList input_list = new LinkedList();
input_list.head = new Node(100);
Node second_node = new Node(200);
Node third_node = new Node(330);
input_list.head.next = second_node;
second_node.next = third_node;
Node current_node = input_list.head;
System.out.print("The linked list is defined as: " );
while (current_node != null) {
System.out.print(current_node.value + " ");
current_node = current_node.next;
}
get_middle_item(input_list);
}
}
실행 결과
The linked list is defined as: 100 200 330 The middle element of the list is: 200
시간 및 공간 복잡도
위 방식의 시간 복잡도는 O(n)이며, 별도의 추가 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다. 리스트 길이를 먼저 계산한 후 다시 순회하는 2회 반복 방식보다 효율적이므로, 코딩 테스트나 면접에서 자주 활용되는 대표적인 기법입니다.