연결 리스트 (linked list)

#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입력값 전체 출력\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 *delNext = head->next;
        printf("%d를 삭제\n",head->data);
        free(delNode);

        while(delNext != NULL)
        {
            delNode = delNext;
            delNext = delNext->next;
            printf("%d를 삭제\n",delNode->data);
            free(delNode);
        }
    }

    return 0;
}

 


 Node로 사용할 구조체를 정의한다. Node는 데이터 값을 가져야하고 다음 Node를 가르킬 수 있어야 하므로 데이터 값을 저장할 변수와 Node에 대한 포인터 변수를 멤버로 정의한다.



<그림 1>


 Node를 도식화 하면 아래 그림 1처럼 표현 할 수 있다.

Node라는 변수는 구조체로 만든 사용자 정의형 변수이다. 해당 멤버 변수로 data와 next가 존재하며 next는 포인터 변수이다.



<그림 2>


    Node *head = NULL;
    Node *tail = NULL;
    Node *cur = NULL;
    Node * newNode = NULL; 

 그림 2는 각 Node들의 초기 상태로 위 코드에 의한 것이다.


<그림 3>


        newNode->data = readData;
        newNode->next = NULL;

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

        tail = newNode; 

 newNode에는 입력한 값이 들어갈 것이고 next는 아직 NULL이므로 가르키는 Node가 없다. (즉, tail이다.)

만약 head가 NULL이면 아직 head가 없는 것이므로 newNode가 첫번째 Node 즉, head가 된다. 또한 현재 Node가 하나뿐이므로 이것은 head이면서 tail이 된다. 처음이자 끝.


<그림 4>


 여기서 새로운 Node가 또 추가 되면 head가 NULL이 아니므로 기존의 tail은 새로운 Node를 가르키고 그 새로운 Node가 tail이 된다. 이렇게 tail 뒷부분에 Node가 추가되고 추가된 Node는 tail이 되는 과정을 반복하면서 연결 리스트가 된다.


+ Recent posts