data structure(자료 구조) - Singly Linked List(단일 연결 리스트)의 삭제 연산과 출력 기능 구현::FBTT

https://readytoearndon.tistory.com/31

data structure(자료 구조) - Singly Linked List(단일 연결 리스트)의 노드 정의, 탐색 연산 구현::FBTT

https://readytoearndon.tistory.com/32

data structure(자료 구조) - Singly Linked List(단일 연결 리스트)의 추가 연산 구현::FBTT

이번 글은 지난 두 글에 이어집니다.

 

저번에는 data의 추가에 대해 알아보았으니 이번에는 data의 삭제에 대해 알아보고 리스트의 자료들을 출력하는 함수를 구현해보도록 하겠습니다.

 

delete(삭제) 연산

우선 삭제를 하기 위해서는 탐색을 통해 삭제하려는 노드를 찾아야 합니다.

 

그래서 처음 탐색을 구현한 후에 삭제 연산을 구현하는 것입니다.

 

먼저 코드부터 봅시다.

 

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node* next;
}node;
 
node* init = NULL;
 
node* linear_search(int key)
{
    node* current = init;
 
    while (current != NULL)
    {
        if (current->data == key)
            return current;
        current = current->next;
    }
 
    return NULL;
}
 
//init부분에 추가
void insert(int data)
{
    node* newnode = (node*)malloc(sizeof(node));
    newnode->data = data;
 
    if (init == NULL)
    {
        init = newnode;
        init->next = NULL;
    }
    else
    {
        newnode->next = init;
        init = newnode;
    }
}
 
void node_delete(int data)
{
    node* current = init;
 
    if (init->data == data)
    {
        node* dnode = init;
        init = init->next;
        free(dnode);
        return 0;
    }
 
    while (current->next != NULL)
    {
        if (current->next->data == data)
            break;
        current = current->next;
    }
 
    node* dnode = current->next;
    current->next = dnode->next;
 
    free(dnode);
}

이번에도 역시 저번 코드에 이어붙여서 가져왔습니다.

 

삭제를 구현한 부분은 43line~66line입니다.(node_delete 함수)

 

45line~52line은 탐색을 구현할 때 설명했던 부분이니 넘어가겠습니다.

(이 부분에 대해서 모르시는 분은 이 글 상단의 링크를 따라가 주세요.)

 

62~63line은 노드를 삭제하기 전 연결을 고치는 부분입니다.

 

dnode는 삭제해야 할 노드를 가리킵니다.(현재 노드의 다음 노드)

 

그리고 현재 가리키는 노드의 next를 삭제해야 할 노드의 다음 노드(현재 노드의 다음 다음 노드)를 가리키게 합니다.

 

그리고 free()를 통해 동적 할당으로 얻은 저장 공간을 반납함으로써 노드를 삭제합니다.

 

if문은 만약 삭제하려는 data가 init 즉, 가장 앞에 있는 노드일 때 init이 가리키는 노드를 삭제하고 init을 다시 가리키게 하는 과정입니다. 

 

탐색 과정을 보면 반복문을 빠져나올 때 삭제해야 할 노드에서 빠져나오는 것이 아닌 삭제하고 싶은 노드 전의 노드에서 빠져나옵니다.

 

그리고 삭제해야 할 노드(dnode)를 current의 다음 노드로 하고 있습니다.

 

어째서 삭제하려고 하는 노드를 current로 두지 않는걸까요?

 

그 이유는 만약 current를 삭제하려고 한다면 다시 연결하는 과정에서 삭제하는 노드(current)의 앞뒤 노드를 연결해주어야 하는데 단일 연결 리스트는 자신의 뒤에 있는 노드에 접근할 방법이 없습니다.

 

그렇기에 삭제하려는 노드의 하나 전 노드에서 삭제 과정을 진행합니다.

 

단일 연결 리스트 삭제 과정

출력 기능

이제 마지막으로 노드들의 data를 출력하는 기능을 구현해보겠습니다.

 

이 기능은 이전에 추가 연산을 구현하면서 한번 보여드린 적이 있습니다. 그러면서 간단히 설명을 드렸었죠.

 

'리스트의 init부터 연결된 노드의 끝까지 출력하는 기능입니다.'

 

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node* next;
}node;
 
node* init = NULL;
 
node* linear_search(int key)
{
    node* current = init;
 
    while (current != NULL)
    {
        if (current->data == key)
            return current;
        current = current->next;
    }
 
    return NULL;
}
 
//init부분에 추가
void insert(int data)
{
    node* newnode = (node*)malloc(sizeof(node));
    newnode->data = data;
 
    if (init == NULL)
    {
        init = newnode;
        init->next = NULL;
    }
    else
    {
        newnode->next = init;
        init = newnode;
    }
}
 
void node_delete(int data)
{
    node* current = init;
 
    if (init->data == data)
    {
        node* dnode = init;
        init = init->next;
        free(dnode);
        return 0;
    }
 
    while (current->next != NULL)
    {
        if (current->next->data == data)
            break;
        current = current->next;
    }
 
    node* dnode = current->next;
    current->next = dnode->next;
 
    free(dnode);
}
 
void print()
{
    node* current = init;
    while (current != NULL)
    {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

출력을 구현한 print 함수입니다.(68~77line)

 

간단히 코드에 대한 설명을 하자면 current에 init(첫 노드)을 가리키게 하고 마지막 노드까지 돌면서 data를 출력하는 코드입니다.

 

다른 탐색, 추가, 삭제보다 이해하기 편할 것입니다.

 

그러면 구현이 제대로 되는지 보겠습니다.

int main(void) 
{
    insert(10);
    insert(12);
    insert(13);
    insert(14);
    insert(15);
    insert(16);
    print();
    node_delete(12);
    node_delete(14); 
    node_delete(16);
    print();
}

실행 결과

이렇게 실행이 되는 것을 확인할 수 있습니다.

 

 

 

이번 글까지를 통해 삭제와 출력을 구현해보았습니다. 단순 연결 리스트에 먼저 익숙해지기 위해 구현해야 할 기능들을 단순하게 했습니다. 나중에 기회가 된다면 좀더 구체화된 연결 리스트의 구현을 해보도록 하겠습니다.