[05]C언어 연결리스트 :: 단일연결리스트 데이터 탐색/삭제/출력

• 데이터 탐색

이러한 단일연결리스트가 있을때 데이터 탐색을 해볼까요 ?

탐색은 아주 쉬워요 !

데이터 탐색의 과정은 위 그림처럼

Cur 이라는 노드 포인터로 Head 다음부터 마지막 NULL 까지 차례대로 넘어가면서 찾는 데이터가 있으면 출력하고, 

없으면 원하는 데이터가 없다고 출력합니다.

이 과정을 코드로 나타내보면

void Search(List *L, int number)
{
    Node *cur = L->head; // cur 이 리스트의 head를 가르킨다. 
 
    if (L->head->next == NULL) 
    {
        printf("저장된 데이터가 없습니다 !\n");
    }
    else // 그 외에 ( head 와 NULL 사이에 하나라도 데이터가 있다면 )
    {
        while (cur!=NULL) //cur 이 NULL 을 만나면 while문을 나간다.
        {
            if (cur->data == number) //cur 이 가르키는 데이터가 찾는 데이터이면
            {
                printf("%d\n", number); //출력하고
                return; // 종료한다
            }
            cur = cur->next; // 아니면 다음데이터로
        }
        if (cur == NULL) printf("찾는 데이터가 없습니다!\n"); // NULL 까지 
    }
}

이렇게 나타낼 수 있겠네요 !

• 데이터 삭제

위의 사진에서 20이라는 노드를 삭제하는 과정은,

① 20이라는 노드를 찾는다. ( 위의 데이터 탐색을 사용해서 )

② 20이라는 노드의 뒤에 노드와 앞의 노드를 연결시켜주고

③ 20이라는 노드는 free를 해준다.

이렇게 되겠네요 !

그럼 한 번 그림으로 볼까요 ?

이렇게 cur이라는 포인터가 20을 찾았을 때,

앞의 노드와 뒤의 노드 ( 30 과 10 ) 을 어떻게 연결해 줄 수 있을까요 ?

10은 cur->next 로하면 될거같은데 , 30은 ?

위의 방법처럼 하면 30을 나타낼 수 있는 방법이 없어요 !

그래서

이렇게 cur->next 가 우리가 찾는 20이어야 합니다.

cur은 우리가 찾는 노드의 바로 전 노드로 하면 되겠죠 ?

이 과정을 코드로 나타내보면,

void Remove(List *L, int number)
{
    Node *cur = L->head;
    Node *rpos; // free 될 노드를 가르킬 노드
 
    if (L->head->next == NULL) // 데이터가 하나도없으면
    {
        printf("저장된 데이터가 없습니다 !\n");
    }
    
    else // 데이터가 하나라도 있다면
    {
        while (cur->next != NULL) //cur의 next가 null이 아니면 계속 돈다
        {
            if (cur->next->data == number)
            {
                rpos = cur->next; // cur->next를 free 시켜야 하므로
                cur->next = cur->next->next; // 앞의 노드가 가르키는게(cur->next) 뒤(cur->next->next)의 노드이다.
                free(rpos); // free
                return;
            }
            cur = cur->next;
        }
        if (cur->next == NULL) printf("찾는 데이터가 없습니다!\n");
    }
}

이렇게 되겠네요 ! 위에서 본 탐색과 비슷하죠?

• 데이터 출력

데이터 출력은 정말 쉬운데요 !

이건 따로 설명없이 코드만 보셔도 충분히 이해하실 수 있을것 같습니다 !

코드를 써보자면,

void Print(List *L)
{
    Node *cur;
 
    if (L->head->next == NULL) printf(" 저장된 데이터가 없습니다 !\n");
    else
    {
        cur = L->head->next;
        while (cur != NULL)
        {
            printf(" %d", cur->data);
            cur = cur->next;
        }
    }
}

이렇게 나타낼 수 있겠네요 .

앞에서 봤던 단일연결리스트의 초기화/삽입/탐색/삭제/출력의 모든 코드를 합쳐보면

#include <stdio.h>
#include <stdlib.h>
 
 
typedef struct _Node {
    int data;   // int 형 데이터를 담는공간
    struct _Node *next; // 연결의 도구 ! ( 화살표 )
}Node;
 
typedef struct _List{
    Node *head;
    int numofData;
}List;
 
Node* getNode()
{
    Node *new = (Node*)malloc(sizeof(Node));
    new->next = NULL;
 
    return new;
}
 
List* initList()
{
    List *L = (List*)malloc(sizeof(List));
    L->head = getNode();
    L->numofData = 0;
    return L;
}
 
 
void Insert(List *L, int number)
{
    Node *newNode = getNode();
    newNode->data = number;
 
    if (L->head->next == NULL) // head 의 next가 가르키는것이 NULL 이면
    {
        newNode->next = NULL;
        L->head->next = newNode;
    }
    else // 그 외에 ( head 와 NULL 사이에 하나라도 데이터가 있다면 )
    {
        newNode->next = L->head->next;
        L->head->next = newNode;
    }
}
 
void Search(List *L, int number)
{
    Node *cur = L->head; // cur 이 리스트의 head를 가르킨다. 
 
    if (L->head->next == NULL) 
    {
        printf("저장된 데이터가 없습니다 !\n");
    }
    else // 그 외에 ( head 와 NULL 사이에 하나라도 데이터가 있다면 )
    {
        while (cur!=NULL)
        {
            if (cur->data == number)
            {
                printf("%d\n", number);
                return;
            }
            cur = cur->next;
        }
        if (cur == NULL) printf("찾는 데이터가 없습니다!\n");
    }
}
 
void Remove(List *L, int number)
{
    Node *cur = L->head;
    Node *rpos; // free 될 노드를 가르킬 노드
 
    if (L->head->next == NULL) // 데이터가 하나도없으면
    {
        printf("저장된 데이터가 없습니다 !\n");
    }
    
    else // 데이터가 하나라도 있다면
    {
        while (cur->next != NULL) //cur의 next가 null이 아니면 계속 돈다
        {
            if (cur->next->data == number)
            {
                rpos = cur->next; // cur->next를 free 시켜야 하므로
                cur->next = cur->next->next; // 앞의 노드가 가르키는게(cur->next) 뒤(cur->next->next)의 노드이다.
                free(rpos); // free
                return;
            }
            cur = cur->next;
        }
        if (cur->next == NULL) printf("찾는 데이터가 없습니다!\n");
    }
}
 
void Print(List *L)
{
    Node *cur;
 
    if (L->head->next == NULL) printf(" 저장된 데이터가 없습니다 !\n");
    else
    {
        cur = L->head->next;
        while (cur != NULL)
        {
            printf(" %d", cur->data);
            cur = cur->next;
        }
    }
}

이렇게 되겠네요 !