[04]C언어 연결리스트 :: 단일리스트 초기화/삽입

연결리스트에는

① 단일연결리스트

② 이중연결리스트

등이 있는데, 이번에는 단일리스트에 대해 설명해보겠습니다.

단일연결리스트

단일리스트는 바로 이런 구조를 가지고 있습니다.

이 단일리스트를 뜯어보면

바로 이런 모양이 나오게 되는데요.

이걸 우리는 "노드 ( Node )" 라고 부릅니다.

노드는 

① Data : 데이터를 저장하는 장소

② 화살표 : 다른 변수를 가리키기 위한 장소

이렇게 두가지로 이루어져 있어요. 

우리가 데이터를 리스트에 저장할 때 마다, 이 노드라는 바구니에 데이터를 넣어두고 바구니끼리 연결하면 됩니다.

바구니끼리 연결하는 건 화살표를 이용해서 연결하면 되겠죠 ?

그럼 여기서 일단 노드라는 구조체를 만들어 볼까요 ?

• 노드 구조체 만들기

#include <stdio.h>
 
typedef struct _Node {
    int data;   // int 형 데이터를 담는공간
    struct _Node *next; // 연결의 도구 ! ( 화살표 )
}Node;

※여기서 next 포인터가 _Node 타입을 가지는 이유는

포인터는 가리키는 대상과 같은 형식이여야만 그 대상을 가르킬 수 있습니다 !

여기서 next 포인터는 Node를 가르키므로 같은 _Node 형식을 가져야 하겠죠 ?

Node 구조체를 만든 후 , 다음 할 일은 List 라는 구조체를 만들어야 합니다.

• List 구조체 만들기

List 구조체는 Head 라는 이름의 노드포인터가 null을 가리키고 있는 모습인데요.

이 모양대로 코드를 작성하면

#include <stdio.h>
 
typedef struct _List{
    Node *head;
    int numofData; // 저장된 데이터의 갯수
}List;

가 되겠네요 !

• List 구조체의 초기화

이제 List 구조체의 초기화가 필요한데요.

Node* getNode() // 빈노드를 하나씩 만들어 주는 함수
{
    Node *new = (Node*)malloc(sizeof(Node)); // Node 크기만큼 동적할당
    new->next = NULL; 
 
    return new;
}
 
List* initList()
{
    List *L = (List*)malloc(sizeof(List)); // List 크기만큼 동적할당
    L->head = getNode(); // List 의 Head 노드를 만든다.
    
    return L;
}

이렇게 하면 List 구조체가 초기화 되었습니다.

※여기서 getNode() 함수는 빈 노드를 하나씩 만들어주는 함수라고 생각해 주시면 될 것 같아요 !

• 노드의 삽입

노드의 삽입에서는 위에 볼수있듯이, 10 ,20, 30 으로 입력하면

head 부터 30,20,10 이렇게 반대로 추가되게 됩니다 .

1. 제일 처음 10이 추가 될 때는

이런 과정을 거치게 됩니다.

① 새로만든 노드의 next가 null 을 가르키게

② head 노드의 next가 새로운 노드를 가르키게

이 과정을 말로 좀 풀어보자면

1-① newNode의 next 는 NULL 로

1-② head의 next 는 newNode 로

2. 그 다음 20이 추가 될 때는

① 새로만든 노드의 next가 10을 가르키게

② head 노드의 next가 새로운 노드를 가르키게

이 과정을 말로 풀어보자면

2-① newNode의 next 는 head의 next로  ( head 가 가르키고있던값을 새로운노드가 가르키게 함 )

2-② head의 next 는 newNode 로

이런 과정이 연속됩니다.  (여기서 ①번 과정이 코드로 쓰면 어려울 수 있음 ! )

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

void Insert(List *L, int number)
{
    Node *newNode = getNode();
    newNode->data = number;
 
    if (L->head->next == NULL) // head 의 next가 가르키는것이 NULL 이면
    {
        newNode->next = NULL; //1-1 과정
        L->head->next = newNode; //1-2 과정
    }
    else // 그 외에 ( head 와 NULL 사이에 하나라도 데이터가 있다면 )
    {
        newNode->next = L->head->next; //2-1 과정
        L->head->next = newNode; //2-2 과정
    }
}

이렇게 나타내면 되겠네요 !

다음에는 단일연결리스트의 탐색, 삭제 등에 대해서 알아보겠습니다 !