📌 Chapter 16 - 동적 메모리와 연결 리스트 - 연결 리스트

2. 연결 리스트(Linked List)

• 데이터를 포인터로 연결하여 관리하는 자료구조이다.
• 각각의 연결 리스트는 노드(node)로 구성되며, 노드는 두 부분으로 나뉜다.
  · 데이터를 저장하는 데이터 필드(data field)
  · 다음 노드를 가리키는 포인터인 링크 필드(link field)
• 노드들이 포인터로 연결되어 node1 -> node2 -> node3처럼 순차적으로 연결된다.
• 마지막 노드는 NULL을 저장해 더 이상 연결된 노드가 없음을 표시한다.
• ⚠️ 포인터로 연결하기 때문에 메모리가 연속된 공간일 필요가 없어 메모리 관리에 유연하다.

반응형

---

1) 자기 참조 구조체 (Self-Referential Structure)

• 자기 참조 구조체란 구조체 멤버 중에 자기 자신과 동일한 구조체 타입의 포인터가 포함된 구조체이다.
• 연결 리스트에서 노드를 정의할 때 사용한다.

struct node {

    int data;           // 데이터 필드

    struct node* p;     // 다음 노드를 가리키는 포인터 (링크 필드)

};

• 위 구조체는 struct node 타입의 노드를 가리키는 포인터 p를 멤버로 포함한다.

---

2) 노드(node)의 생성과 연결

• 보통 typedef를 활용하여 구조체를 간단히 선언한다.

typedef struct node {

    int data;          // 데이터 필드

    struct node* p;    // 링크 필드

} nd;

• 노드 생성은 malloc()으로 동적 할당한다.

 

nd* node1 = (nd*)malloc(sizeof(nd));  // 노드 1 생성

node1->data = 1;                       // 데이터 설정

node1->p = NULL;                      // 링크 필드 초기화 (끝 노드)

 

nd* node2 = (nd*)malloc(sizeof(nd));  // 노드 2 생성

node2->data = 2;

node2->p = NULL;

 

node1->p = node2;  // 노드1의 다음 노드를 노드2로 연결

• 마지막 노드는 항상 p에 NULL을 저장한다.

---

3) 메모리 해제

• 할당한 노드는 작업이 끝난 후 반드시 free() 함수로 메모리를 반납해야 한다.

free(node1);

free(node2);

• 메모리 누수를 방지하기 위해 연결 리스트를 완전히 해제할 때는 모든 노드를 순회하며 해제해야 한다.

---

💻 예제 코드 - 연결 리스트 생성 함수 예제

#include <stdio.h>

#include <stdlib.h>

 

typedef struct node {

    int data;          // 데이터 필드

    struct node* p;    // 링크 필드

} nd;

 

// 노드 생성 함수

nd* create_node(int value) {

    nd* new_node = (nd*)malloc(sizeof(nd));

    if (new_node == NULL) {

        printf("메모리 할당 실패\n");

        return NULL;

    }

    new_node->data = value;

    new_node->p = NULL;

    return new_node;

}

 

// 연결 리스트 메모리 해제 함수

void free_list(nd* head) {

    nd* temp;

    while (head != NULL) {

        temp = head;

        head = head->p;

        free(temp);

    }

}

 

int main() {

    // 첫 번째 노드 생성

    nd* head = create_node(1);

    if (head == NULL) return 1;

 

    // 두 번째 노드 생성 및 연결

    nd* node2 = create_node(2);

    if (node2 == NULL) {

        free_list(head);

        return 1;

    }

    head->p = node2;

 

    // 세 번째 노드 생성 및 연결

    nd* node3 = create_node(3);

    if (node3 == NULL) {

        free_list(head);

        return 1;

    }

    node2->p = node3;

 

    // 리스트 출력

    nd* current = head;

    while (current != NULL) {

        printf("데이터: %d\n", current->data);

        current = current->p;

    }

 

    // 메모리 해제

    free_list(head);

 

    return 0;

}

---

✅ 마무리 정리

1️⃣ 연결 리스트는 데이터를 포인터로 연결하여 메모리를 유연하게 관리하는 자료구조이다.
2️⃣ 노드는 데이터 필드와 다음 노드를 가리키는 포인터인 링크 필드로 구성된다.
3️⃣ 자기 참조 구조체는 동일 타입 포인터를 포함한 구조체로 연결 리스트 노드 정의에 사용한다.
4️⃣ 노드는 malloc()으로 동적 할당하며, NULL 포인터로 연결 종료를 표시한다.
5️⃣ 연결 리스트 사용 후에는 free() 함수를 이용해 할당한 메모리를 반드시 해제해야 한다.
6️⃣ 사용자 정의 함수로 노드 생성과 리스트 해제를 구현하는 것이 코드 관리에 유리하다.