[c언어] 연결 리스트의 삽입과 삭제

26 Dec 2023

c언어

이번에는 연결 리스트에서 데이터를 삽입하고 삭제하는 방법에 대해 알아보겠습니다. 연결 리스트는 데이터 요소들을 순차적으로 저장하는 자료구조이며, 각 요소는 다음 요소를 가리키는 포인터를 가지고 있습니다.

연결 리스트의 삽입

연결 리스트에 데이터를 삽입할 때는 다음과 같은 단계를 거칩니다.

새로운 노드 생성: 새로운 데이터를 저장할 새로운 노드를 생성합니다.
포인터 업데이트: 새로운 노드가 삽입될 위치를 찾은 후, 해당 위치의 포인터를 새로운 노드로 업데이트합니다.

다음은 C언어로 작성한 연결 리스트에 데이터를 삽입하는 예제 코드입니다.

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

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

// 연결 리스트에 데이터를 삽입하는 함수
void insertNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}

연결 리스트의 삭제

연결 리스트에서 데이터를 삭제할 때는 다음과 같은 단계를 거칩니다.

삭제할 노드 검색: 삭제할 데이터가 저장된 노드를 찾습니다.
포인터 업데이트: 삭제할 노드의 이전 노드가 삭제할 노드를 건너뛰도록 포인터를 업데이트합니다.
메모리 해제: 삭제할 노드의 메모리를 해제합니다.

이제 C언어로 작성한 연결 리스트에서 데이터를 삭제하는 예제 코드를 살펴보겠습니다.

// 연결 리스트에서 데이터를 삭제하는 함수
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);
}

이제 연결 리스트에서 데이터를 삽입하고 삭제하는 방법에 대해 알아보았습니다. 이러한 기본적인 연산들을 바탕으로 연결 리스트를 활용하여 다양한 자료구조와 알고리즘을 구현할 수 있습니다.

참고 문헌: GeeksforGeeks