C언어를 사용한 단일 링크드 리스트 (Single Linked List)

링크드 리스트는 데이터 요소들을 노드라 부르는 객체로 유지하는 자료구조이다. 이 노드들은 각자 다음 노드를 가리키는 포인터를 갖고 있어, 연결 리스트를 형성한다.

링크드 리스트의 기본 개념

링크드 리스트는 순차적 접근이 용이하며, 동적 크기를 가지기 때문에 유연하게 데이터를 삽입 및 삭제할 수 있다.

노드 구조체

링크드 리스트의 노드는 데이터와 다음 노드를 가리키는 포인터로 구성된 구조체이다. 예제 코드를 통해 쉽게 이해할 수 있다.

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

메모리 레이아웃

링크드 리스트의 메모리 레이아웃은 다음과 같은 형태로 시각화할 수 있다:

[Head] -> [Data|Next] -> [Data|Next] -> [Data|Next] -> NULL

링크드 리스트의 초기화

링크드 리스트를 구현하기 위해 먼저 리스트를 초기화해야 한다. 초기화하는 방법은 매우 간단하다.

struct Node* head = NULL;

노드 추가

새로운 노드를 링크드 리스트에 추가하는 과정 역시 중요하다. 우리는 리스트의 끝에 노드를 추가하는 예제를 살펴볼 것이다.

가장 끝에 노드 추가하기

리스트 끝에 노드를 추가하는 함수는 다음과 같다:

void append(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;
    new_node->data = new_data;
    new_node->next = NULL;
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
    while (last->next != NULL)
        last = last->next;
    last->next = new_node;
}

노드 삭제

링크드 리스트에서 노드를 삭제하는 방법도 중요하다. 특정 값을 가진 노드를 삭제하는 예제를 보자.

특정 값의 노드 삭제하기

삭제 함수는 다음과 같다:

void deleteNode(struct Node** head_ref, int key) {
    struct Node* temp = *head_ref, *prev;
    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}

링크드 리스트의 검색

마지막으로, 링크드 리스트에서 특정 값을 가진 노드를 검색하는 방법을 알아보자.

노드 검색하기

검색 함수는 다음과 같다:

struct Node* search(struct Node* head, int key) {
    struct Node* current = head;
    while (current != NULL) {
        if (current->data == key)
            return current;
        current = current->next;
    }
    return NULL;
}

예제 코드 종합

위의 예제를 종합하여 통합적인 예제 코드를 작성해보자:

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

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

void append(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;
    new_node->data = new_data;
    new_node->next = NULL;
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
    while (last->next != NULL)
        last = last->next;
    last->next = new_node;
}

void deleteNode(struct Node** head_ref, int key) {
    struct Node* temp = *head_ref, *prev;
    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}

struct Node* search(struct Node* head, int key) {
    struct Node* current = head;
    while (current != NULL) {
        if (current->data == key)
            return current;
        current = current->next;
    }
    return NULL;
}

int main() {
    struct Node* head = NULL;
    append(&head, 1);
    append(&head, 2);
    append(&head, 3);

    printf("Linked List created: ");
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");

    deleteNode(&head, 2);
    printf("Linked List after deletion of 2: ");
    temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");

    struct Node* found = search(head, 3);
    if (found != NULL) printf("Element 3 found in the list.\n");
    else printf("Element 3 not found in the list.\n");

    return 0;
}

kaspyx