[자료구조] 단일 연결 리스트(Singly Linked List) 노드 삭제(Delete) 구현 - C

이전 코드를 바탕으로 노드를 삭제하는 함수를 작성하겠다.

 

고려해야 할 사항은 아래와 같다.

• 원래 노드가 빈 노드인 경우
• 삭제해야할 값이 첫번째 노드인 경우
• 삭제해야할 값이 중간에 있는 노드인 경우
• 삭제해야할 값이 마지막 노드인 경우

 

void deleteNode(Node **head, int data)
{
    if (*head == NULL) // 원래 노드가 빈 노드인 경우(삭제할 값이 없음)
    {
        printf("빈 연결리스트입니다. \n");
        return;
    }
    Node *cur = *head;

    if (cur->data == data) // 첫 노드가 삭제할 노드인 경우
    {
        *head = cur->link; // head 노드를 한칸 옮김(노드 삭제)
        free(cur);         // 할당 해제
        return;
    }

    Node *pre = *head;
    while (cur->link != NULL) // cur가 마지막 노드가 아닌 경우
    {
        if (cur->data == data) // 노드를 찾은 경우
        {
            pre->link = cur->link; // 이전 노드의 링크를 현재 노드의 다음 값으로 연결
            free(cur);             // 할당 해제
            return;
        }
        pre = cur; // 못찾은 경우에는 pre와 cur 각각 한칸씩 이동
        cur = cur->link;
    }
    if (cur->link == NULL && cur->data == data) // 마지막 노드에서 찾은 경우
    {
        pre->link = NULL; // 이전 노드의 링크를 NULL로 설정(마지막 노드로 만들기))
        free(cur);        // 할당 해제
    }
}

 

노드를 삭제하려면 우선 연결리스트, 삭제할 값을 알아야한다.

이동하면서 삭제할 값(val)을 찾아야 하므로, 현재 노드를 나타내는 cur와 이전 노드를 나타내는 bef를 생성한다.

 

 

위 코드처럼 각 경우에 맞게 설계하면 된다.

 

실행 결과

 

 

삭제가 정상적으로 진행되는 것을 확인할 수 있다.