[자료구조] Linked List- 삭제

Linked List에서 삭제는 다음과 같은 순서로 이루어진다.

 

1) 삭제할 노드의 앞 노드를 찾는다. 앞 노드를 찾는 이유는 크게 두가지인데, 연결관계를 해제하기 위해서이자 노드를 효율적으로 찾아 해제시키는 방법이기 때문이다.

 

2) 앞 노드의 링크필드에 삭제할 노드의 링크 필드값을 저장한다.

 

3) 삭제할 노드를 삭제하고, 메모리를 해제한다.

 

 

삭제 연산을 c로 구현하면 다음과 같다.

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

// 단일 연결 리스트의 노드 정의
struct Node {
    int data;
    struct Node* next;
};

// 연결 리스트의 헤드를 전역 변수로 선언
struct Node* head = NULL;

// 연결 리스트에 노드 추가
void insertNode(int val) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = val;
    newNode->next = head;
    head = newNode;
}

// 연결 리스트에서 특정 값을 갖는 노드 삭제
void deleteNode(int val) {
    struct Node* current = head;
    struct Node* previous = NULL;

    // 헤드 노드부터 시작하여 삭제할 노드 찾기
    while (current != NULL && current->data != val) {
        previous = current;
        current = current->next;
    }

    // 삭제할 노드를 찾은 경우
    if (current != NULL) {
        // 삭제할 노드가 헤드 노드인 경우
        if (previous == NULL) {
            head = current->next;
        } else {
            previous->next = current->next;
        }

        // 메모리 해제
        free(current);
    } else {
        printf("삭제할 노드가 없습니다.\n");
    }
}

// 연결 리스트 출력
void printList() {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    // 연결 리스트에 노드 추가
    insertNode(3);
    insertNode(5);
    insertNode(7);
    insertNode(9);

    // 연결 리스트 출력
    printf("연결 리스트: ");
    printList();

    // 특정 값을 갖는 노드 삭제
    deleteNode(5);

    // 삭제 후 연결 리스트 출력
    printf("삭제 후 연결 리스트: ");
    printList();

    return 0;
}