연결리스트의 개념적인 이해

"배열은 메모리의 특성이 정적이어서 (길이의 변경이 불가능해서) 메모리의 길이를 변경하는것이 불가능하다."

 

그래서 등장한것이 '동적인 메모리 구성'이다.

 

아래는 연결리스트를 진짜 구현한 것이 아니라, 개념적인 이해를 위한 예제이다.

아래를 보면  Node 구조체를 만들고

그 구조체는 data와 다음 주소를 가리키는 next로 구성되어있음을 알 수 있다.

 

데이터 입력받는 과정: malloc을통해 동적으로 Node구조체를 생성해주고, 헤드랑 테일이 가리키게 한다.

입력을 받을때마다 tail의 next가 새로 할당받은 Node를 가리키가 만들고 tail을 Node로 변경해준다.

 

출력과정 : cur에 처음 head를 지정해 주고, cur -> next가 존재하면 하나씩 밀어가며 출력한다.

 

삭제과정 : delNode와 delNextNode Node를 만들어주고 free를 통해 할당 해제할 녀석의 정보를 delNextNode에 저장해준뒤 delNode를 해제시켜준다. 그 이유는 delNode를 먼저 없애게 되면 다음 Node의 주소를 알 수 있는 방법이 없어지기 때문이다.

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

typedef struct _node
{
    int data;
    struct _node *next;
} Node;

int main(void)
{
    Node * head = NULL;
    Node * tail = NULL;
    Node * cur = NULL;

    Node * newNode = NULL;
    int readData;

    //데이터를 입력 받는 과정//
    while(1)
    {
        printf("자연수 입력: ");
        scanf("%d",&readData);
        if(readData < 1) break;

        newNode = (Node *)malloc(sizeof(Node));
        newNode -> data = readData;
        newNode -> next = NULL;

        if(head == NULL) head = newNode;
        else tail -> next = newNode;

        tail = newNode;
    }
    printf("\n");

    //입력받은 데이터의 출력과정
    printf("입력받은 데이터의 전체 출력! \n");
    if(head == NULL)
    {
        printf("저장된 자연수가 존재하지 않습니다. \n");
    }
    else
    {
        cur = head;
        printf("%d ", cur -> data);

        while(cur -> next != NULL)
        {
            cur = cur -> next;
            printf("%d ", cur->data);
        }
    }
    printf("\n\n");

    //메모리의 해제과정
    if(head == NULL)
    {
        return 0;
    }
    else
    {
        Node * delNode = head;
        Node * delNextNode = head->next;

        printf("%d를 삭제합니다 \n",head->data);
        free(delNode);

        while(delNextNode != NULL)
        {
            delNode = delNextNode;
            delNextNode = delNextNode -> next;

            printf("%d를 삭제합니다. \n", delNode->data);
            free(delNode);
        }
    }

    return 0;
}