- 연결리스트의 구조

⇒ 연결리스트는 구조체를 이용하여 만든다. 연결 리스트는 구조체 내에 다른 구조체를 가리키는 포인터를 멤버로 가짐으로서 만들 수 있다.

// 세 개의 구조체로 구성된 연결 리스트를 만드는 프로그램
#include<stdio.h>
typedef struct list
{
        int data;
        struct list *next; // 자기 참조 구조체
}LIST;

int main()
{
        LIST a, b, c;
        a.data = 3;
        b.data = 4;
        c.data = 5;
        a.next = b.next = c.next = NULL;
        printf("a: %d,\tb: %d,\tc: %d\t\n", a.data, b.data, c.data);
        a.next = &b;
        b.next = &c;
        printf("a:%d,\tb:%d,\tc:%d\n", a.data, a.next->data, a.next->next->data);
  
        return 0;
}

⇒ 출력 결과         

⇒ typedef struct list

   {

        int data;

        struct list *next;

   }LIST;

 → list 구조체의 두 번째 멤버 next의 자료형은 그 자신인 list 구조체에 대한 포인터이다. 이렇게 스스로를 참조하는 구조체를 자기 참조 구조체(self referential structure)라고 한다. 여기서 next는 포인터이므로 4바이트를 차지한다.

⇒ LIST a, b, c;

 → list 형의 변수 a, b, c를 위한 공간이 할당된다. data 필드와 next 필드는 각각 4바이트를 차지한다.

⇒ a.data = 3, b.data = 4, c.data = 5;

 → 구조체 변수의 data 필드의 초기화로 부여받은 값이 다음과 같이 저장된다.

< 구조체의 next 필드의 초기화 >

⇒ a.next = b.next = c.next = NULL

 → next 필드의 값이 NULL 값으로 초기화시킨다. 포인터 변수가 NULL 값을 가지는 것은 아무 곳도 가리키지 않는다는 의미로 미정값과는 다르다. 연결리스트내의 포인터변수는 일단 선언 후에는 NULL 값으로 초기화시켜 주는 것이 좋다. 연결 리스트에서 포인터는 다음 노드를 연결시키는 중요한 역할을 하는데, 프로그램내에서 포인터변수는 가리키는 대상을 잃어버리는 경우가 많기 때문에 먼저 NULL로 초기화 시키는 것이 안전하다. 아래 그림에서 대각선은 NULL 값을 의미한다.

< 구조체의 next 필드의 초기화 >

⇒ a.next = &b;

   b.next = &c;

 → 이 명령문의 수행으로 a의 멤버 next는 b의 시작주소를 가지고, b의 멤버 next는 c의 시작주소를 가지게 되어 연결리스트를 만들게 된다. 연결리스트에서 각 구조체 변수를 노드(node)라고 부른다.

⇒ a.next는 주소값을 가지고

⇒ a.next -> 는 a.next가 가리키는 대상물을 의미하는데, b에 해당한다. 따라서

⇒ a.next -> data는 b.data와 같고, 값은 b의 data 멤버의 값인 4가 되고,

⇒ b.data와 같고, 값은 b의 data 멤버의 값인 4가 되고,

⇒ a.next -> next -> data의 값은 c.data의 값인 5가 된다.

- 연결리스트의 작성

// 간단한 연결리스트를 작성하는 프로그램
#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
        char data;
        struct node *next;
}NODE;

int main()
{
        NODE *list, *temp;

        list = (NODE *)malloc(sizeof(NODE));
        list->data = 'a';
        list->next = (NODE *)malloc(sizeof(NODE));
        list->next->data = 'b';
        list->next->next = (NODE *)malloc(sizeof(NODE));
        list->next->next->data = 'c';    
        list->next->next->next = NULL;

          // 연결 리스트의 출력
        temp = list;
        while(temp != NULL)
        {
                printf("%5c\n", temp->data);
                temp = temp->next;
        }

        free(temp);

        free(list -> next);

        free(temp);
        return 0;
} 

⇒ 출력 결과

⇒ list = (NODE *) malloc (sizeof(NODE));

 → 새로운 NODE 구조체를 위한 메모리를 할당받고, list가 가리킨다.

⇒ list -> data = 'a';

 → 구조체의 data 필드가 값을 받는다.

⇒ list -> next = (NODE *)malloc(sizeof(NODE));

 → 새로운 구조체를 위한 메모리를 할당받고, list -> next 가 가리킨다.

⇒ 프로그램의 실행이 끝났을 때 다음과 같은 리스트가 만들어진다. 연결리스트의 마지막을 표시하기 위해서 마지막 노드의 next 필드는 항상 NULL 값을 가진다. 

- 앞의 프로그램에서는 포인터 필드인 next를 계속해서 사용함으로써 연결리스트가 길어질 경우 프로그램의 작성이 복잡해진다. 다음 프로그램은 임시 변수를 사용하여 간단히 연결리스트를 만드는 예이다.

// 간단한 연결리스트를 작성하는 프로그램
#include<stdio.h>
#include<stdlib.h> // malloc() 함수
typedef struct node
{
        char data;
        struct node *next;
}NODE;

int main()
{
        NODE *list, *temp;

        list = (NODE *)malloc(sizeof(NODE));
        list -> data = 'a';
        temp = list;
        temp -> next = (NODE *)malloc(sizeof(NODE));
        temp = temp -> next;
        temp -> data = 'b';
        temp -> next = (NODE *)malloc(sizeof(NODE));
        temp = temp -> next;
        temp -> data = 'c';
        temp ->next = NULL;

        //연결리스트의 출력
        temp = list;
        while(temp != NULL)
        {
                printf("%5c\n", temp -> data);
                temp = temp -> next;
        }

        free(temp);

        free(list -> temp);

        free(list);
        return 0;
} 

⇒ 출력 결과         

⇒ list = (NODE *) malloc (sizeof(NODE));

 → 이때 malloc은 메모리 공간을 heap 영역에 생성하고 주소를 반환한다. 이때 list가 주소를 받지 않으면 영원히 malloc이 생성한 메모리 공간을 찾을 수 없다.

 → 형이 아무것도 없을 때는 void 형을 사용하며, void* 는 주소를 반환한다. 이 둘은 다르다.