[자료구조] Linked Lists- Search

연결리스트에서 탐색은 다음과 같은 과정으로 이루어진다.

 

1. 헤드에서 시작 :  검색을 시작하기 위해 연결리스트의 헤드부터 탐색을 시작한다.

2. 노드 순회: 각 노드를 순차적으로 방문하면서 원하는 값을 찾을 때까지 계속 진행한다.

3. 비교 연산: 각 노드에서 찾고자 하는 값을 현재 노드의 데이터와 비교한다.

 

값을 찾을 경우 검색을 종료하고 노드의 위치를 반환하지만, 찾지 못할 경우에는 검색이 실패했다고 출력하게 된다.

 

다음은 자료구조 상에서 search 연산 예제이다.

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

// 연결 리스트의 노드 구조체 정의
struct Node {
    int data;
    struct Node* next;
};

// 연결 리스트에서 값 검색하는 함수
struct Node* search(struct Node* head, int key) {
    struct Node* current = head;

    // 연결 리스트를 끝까지 순회하면서 값 비교
    while (current != NULL) {
        if (current->data == key) {
            // 값을 찾았을 경우 해당 노드 반환
            return current;
        }
        current = current->next;
    }

    // 값을 찾지 못했을 경우 NULL 반환
    return NULL;
}

int main() {
    // 연결 리스트 생성
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    // 연결 리스트에서 값 2를 검색
    int key = 2;
    struct Node* result = search(head, key);

    // 검색 결과 출력
    if (result != NULL) {
        printf("값 %d을(를) 찾았습니다.\n", key);
    } else {
        printf("값 %d을(를) 찾지 못했습니다.\n", key);
    }

    return 0;
}