C++로 단일 연결 리스트(Singly Linked List)에서 특정 요소 검색하기

단일 연결 리스트(Singly Linked List)가 주어졌을 때, 해당 리스트 안에서 특정 요소를 검색하는 문제입니다. 요소를 찾으면 "Present"를 출력하고, 찾지 못하면 "Not Present"를 출력해야 합니다.

예시 1

입력:

1 → 2 → 3 → 4 → 5 → 6

검색 대상: '7'

출력:

Not Present

설명: 주어진 단일 연결 리스트에는 '7'이 존재하지 않으므로 "Not Present"를 반환합니다.

예시 2

입력:

1 → 2 → 3 → 4 → 5

검색 대상: '2'

출력:

Present

설명: 주어진 단일 연결 리스트에 '2'가 존재하므로 "Present"를 반환합니다.

문제 해결 접근 방법

연결 리스트에서 특정 요소를 검색하는 방법은 크게 두 가지가 있습니다.

재귀(Recursion) 방식: 연결 리스트가 비어 있으면 false를 반환하고, 현재 노드의 데이터 값이 찾고자 하는 요소와 일치하면 true를 반환합니다. 일치하지 않으면 다음 노드를 대상으로 함수를 다시 호출합니다.
반복(Iteration) 방식: 헤드 포인터부터 시작해 각 노드의 값을 순차적으로 비교하면서, 일치하면 true를, 끝까지 탐색해도 없으면 false를 반환합니다.

알고리즘 단계

입력을 받아 노드를 삽입하는 방식으로 단일 연결 리스트를 초기화합니다.
불리언(Boolean) 재귀 함수 searchRecursive(node* head, int key)는 연결 리스트의 헤드 포인터와 검색할 키 값을 매개변수로 받습니다.
헤드가 NULL, 즉 연결 리스트가 비어 있으면 false를 반환합니다.
검색하려는 요소가 현재 헤드 노드의 데이터와 같으면 true를 반환합니다.
그렇지 않으면 다음 노드(head->next)를 인자로 하여 함수를 재귀적으로 호출합니다.

C++ 구현 예제

#include <iostream>
using namespace std;

class node {
public:
    int data;
    node* next;
    node(int d) {
        data = d;
        next = NULL;   // 다음 노드를 NULL로 초기화
    }
};

// 새 노드를 리스트 맨 앞에 삽입
void insertAt(node*& head, int data) {
    node* n = new node(data);
    n->next = head;
    head = n;
}

// 재귀적으로 키 값 검색
bool searchRecursive(node* head, int key) {
    if (head == NULL) {
        return false;          // 리스트 끝에 도달: 요소 없음
    }
    if (head->data == key) {
        return true;           // 요소 발견
    }
    return searchRecursive(head->next, key); // 다음 노드로 이동
}

// 연결 리스트 출력
void printNode(node* head) {
    while (head != NULL) {
        cout << head->data << "->";
        head = head->next;
    }
    cout << endl;
}

int main() {
    node* head = NULL;
    insertAt(head, 5);
    insertAt(head, 4);
    insertAt(head, 3);
    insertAt(head, 2);
    insertAt(head, 1);

    printNode(head);

    if (searchRecursive(head, 7)) {
        cout << "Present" << endl;
    } else {
        cout << "Not Present" << endl;
    }
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

1->2->3->4->5->
Not Present

주어진 연결 리스트 1 → 2 → 3 → 4 → 5에는 '7'이 존재하지 않으므로 "Not Present"가 출력됩니다. 만약 searchRecursive(head, 3)처럼 리스트에 있는 값을 검색하면 "Present"가 출력됩니다.

복잡도 분석

시간 복잡도: 최악의 경우 모든 노드를 한 번씩 방문해야 하므로 O(n)입니다.
공간 복잡도: 재귀 호출 시 호출 스택이 노드 수만큼 쌓이므로 O(n)이며, 반복문으로 구현하면 O(1)로 줄일 수 있습니다.