C언어 구조체 연결 리스트 - 공부하는 도비

연결 리스트란, 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입니다. 아래 그림처럼 Link 필드(포인터 필드)에 다음이나 이전 노드의 주소 값을 저장하여 각 노드를 연결합니다.

---

오늘은 구조체를 사용하여 연결 리스트를 구현해보겠습니다.

 

C언어에서 연결리스트의 노드 종류는 크게 머리 노드와 일반 노드로 나뉩니다. 

 

- 머리노드(head node) : 단일 연결 리스트의 기준점이며, 첫 번째 노드를 가리키는 용도로 사용됩니다. 이 노드엔 데이터를 저장하지 않습니다. 

- 일반 노드 : 연결 리스트에서 데이터가 저장되는 실제 노드를 의미합니다. 

 

맨 마지막 노드의 Link 필드엔 NULL 값이 들어갑니다. 

 

구조체를 이용하여 연결 리스트 구현

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

struct Node {   // 연결 리스트의 노드 구조체
    struct Node *next;  // 다음 노드의 주소를 저장할 포인터
    int data;   // 데이터를 저장할 멤버 변수 
};

int main()
{
    struct Node *head = malloc(sizeof(struct Node));    // 머리 노드 : 단일 연결 리스트의 기준점.
    						       // 첫 번째 노드를 가리키는 용도이며 데이터를 저장하지 않음
     
    struct Node *node1 = malloc(sizeof(struct Node));	// node1
    head->next = node1;
    node1->data = 10;
    
    struct Node *node2 = malloc(sizeof(struct Node));	// node2
    node1->next = node2;
    node2->data = 20;
    
    node2->next = NULL;		// 마지막 노드엔 NULL 값 저장
    
    //struct Node *curr = head->next; // 연결 리스트 순회용 포인터 curr 생성 
    struct Node *curr = head;
    
    while(curr != NULL)
    {
        printf("%d\n", curr->data);
        curr = curr->next;
    }
    
    free(node2);
    free(node1);
    free(head);

    return 0;
}

 

 

* 연결 리스트에 노드를 추가하는 규칙*

1. 노드에 메모리 할당 

2. next 멤버변수에 다음 노드의 메모르 주소를 저장

3. data 멤버 변수에 데이터 저장

4. 마지막 노드라면 next 멤버 변수에 NULL 저장