C++로 구현하는 단일 연결 리스트 이진 탐색: 개념부터 코드까지

단일 연결 리스트(Singly Linked List)는 각 노드가 자신의 값과 다음 노드의 메모리 주소를 저장하며, 한 방향으로만 순회할 수 있는 연결 리스트 자료구조입니다.

이진 탐색(Binary Search)은 분할 정복(Divide and Conquer) 기법에 기반한 탐색 알고리즘으로, 자료구조의 가운데 요소를 찾아 목표 값과 비교한 뒤, 일치하지 않으면 같은 알고리즘을 재귀적으로 호출하여 절반씩 탐색 범위를 좁혀 나갑니다.

이 글에서는 단일 연결 리스트와 찾으려는 값이 주어졌을 때, 이진 탐색으로 해당 값을 찾는 방법을 다룹니다.

단일 연결 리스트에서 이진 탐색이 어려운 이유

단일 연결 리스트는 포인터를 하나만 사용하는 자료구조이기 때문에 중간 요소를 바로 찾기가 쉽지 않습니다. 배열과 달리 인덱스로 임의 접근(random access)이 불가능하기 때문입니다. 따라서 단일 연결 리스트의 중간 노드를 찾으려면 두 포인터(two pointer) 기법, 즉 느린 포인터(slow pointer)와 빠른 포인터(fast pointer)를 활용해야 합니다.

알고리즘

전체 동작 과정은 다음과 같습니다.

1단계: 시작 노드(start_node, 리스트의 head), 마지막 노드(last_node), 중간 노드(mid_node)를 초기화합니다.

2단계: mid_node와 찾으려는 값을 비교합니다.

• 2-1단계: mid_node == 값이면 "찾음"을 반환합니다.
• 2-2단계: mid_node > 값이면 하위 절반(lower half)에 대해 이진 탐색을 재귀 호출합니다.
• 2-3단계: mid_node < 값이면 상위 절반(upper half)에 대해 이진 탐색을 재귀 호출합니다.

3단계: 리스트 전체를 순회할 때까지 찾지 못하면 "찾지 못함"을 반환합니다.

C++ 구현 예제

#include<stdio.h>
#include<stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

Node *newNode(int x) {
    struct Node* temp = new Node;
    temp->data = x;
    temp->next = NULL;
    return temp;
}

// 두 포인터 기법으로 중간 노드를 찾는 함수
struct Node* mid_node(Node* start, Node* last) {
    if (start == NULL)
        return NULL;

    struct Node* slow = start;
    struct Node* fast = start -> next;

    while (fast != last) {
        fast = fast -> next;
        if (fast != last) {
            slow = slow -> next;
            fast = fast -> next;
        }
    }
    return slow;
}

struct Node* binarySearch(Node *head, int value) {
    struct Node* start = head;
    struct Node* last = NULL;

    do {
        Node* mid = mid_node(start, last);
        if (mid == NULL)
            return NULL;
        if (mid -> data == value)
            return mid;
        else if (mid -> data < value)
            start = mid -> next;
        else
            last = mid;
    }
    while (last == NULL || last != start);

    return NULL;
}

int main() {
    Node *head = newNode(54);
    head->next = newNode(12);
    head->next->next = newNode(18);
    head->next->next->next = newNode(23);
    head->next->next->next->next = newNode(52);
    head->next->next->next->next->next = newNode(76);

    int value = 52;

    if (binarySearch(head, value) == NULL)
        printf("Value is not present in linked list\n");
    else
        printf("The value is present in linked list\n");

    return 0;
}

코드 설명

mid_node 함수는 느린 포인터(slow)와 빠른 포인터(fast)를 사용합니다. 빠른 포인터는 한 번에 두 칸씩, 느린 포인터는 한 칸씩 이동하므로 빠른 포인터가 끝에 도달하면 느린 포인터는 정확히 중간에 위치하게 됩니다.

binarySearch 함수는 반복문을 통해 중간 노드의 값과 찾으려는 값을 비교합니다. 중간 값이 더 작으면 시작 지점을 중간 노드의 다음 노드로 옮겨 상위 절반을 탐색하고, 더 크면 마지막 지점을 중간 노드로 설정하여 하위 절반을 탐색합니다.

실행 결과

The value is present in linked list

값 52가 연결 리스트 안에 존재하므로 위와 같은 결과가 출력됩니다.

마무리

배열에서의 이진 탐색은 O(log n)의 시간 복잡도를 가지지만, 단일 연결 리스트에서는 중간 노드를 찾는 데 매번 O(n)의 시간이 걸릴 수 있어 효율이 떨어집니다. 그럼에도 불구하고 이 기법은 연결 리스트 기반 문제에서 분할 정복 사고방식을 익히는 데 매우 유용하며, 면접에서도 자주 등장하는 주제입니다. 두 포인터 기법과 함께 익혀두면 다양한 연결 리스트 문제 해결에 큰 도움이 됩니다.