C สร้าง linked list



linked list เป็นโครงสร้างข้อมูลแรกที่ต้องใช้ pointer + malloc/free เต็มรูปแบบ — เป็นบทฝึกที่ดีมาก

แนวคิด

แต่ละ node เก็บข้อมูล + pointer ไป node ถัดไป node สุดท้ายชี้ NULL

head ──► [1|•] ──► [2|•] ──► [3|NULL]

ต่างจากอาร์เรย์: node ไม่ได้อยู่ติดกันในหน่วยความจำ เพิ่ม/ลบตรงหัวได้เร็ว (ไม่ต้องเลื่อนของ) แต่เข้าถึง index ที่ i ต้องเดินจากหัว

นิยาม node

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

typedef struct Node {
    int value;
    struct Node *next;      // ต้องเป็น "struct Node *" — typedef ยังไม่เสร็จตรงนี้
} Node;

สร้าง node

Node *node_create(int value)
{
    Node *n = malloc(sizeof(Node));
    if (n == NULL) {
        return NULL;
    }
    n->value = value;
    n->next = NULL;
    return n;
}

เพิ่มที่หัว — O(1)

// รับ Node** เพราะต้องแก้ตัว head ของผู้เรียก
void list_push_front(Node **head, int value)
{
    Node *n = node_create(value);
    if (!n) return;
    n->next = *head;       // node ใหม่ชี้ไปหัวเดิม
    *head = n;             // หัวใหม่คือ node นี้
}

เพิ่มที่ท้าย — O(n)

void list_push_back(Node **head, int value)
{
    Node *n = node_create(value);
    if (!n) return;

    if (*head == NULL) {          // ลิสต์ว่าง
        *head = n;
        return;
    }

    Node *cur = *head;
    while (cur->next != NULL) {   // เดินไปตัวสุดท้าย
        cur = cur->next;
    }
    cur->next = n;
}

วนทั้งลิสต์

void list_print(const Node *head)
{
    for (const Node *cur = head; cur != NULL; cur = cur->next) {
        printf("%d -> ", cur->value);
    }
    printf("NULL\n");
}

size_t list_length(const Node *head)
{
    size_t count = 0;
    for (const Node *cur = head; cur != NULL; cur = cur->next) {
        count++;
    }
    return count;
}

ค้นหา

Node *list_find(Node *head, int value)
{
    for (Node *cur = head; cur != NULL; cur = cur->next) {
        if (cur->value == value) {
            return cur;
        }
    }
    return NULL;
}

ลบ node ตามค่า

จุดที่พลาดบ่อย — ต้องเก็บ pointer ไป node ก่อนหน้า เพื่อเชื่อมข้าม node ที่ลบ:

int list_remove(Node **head, int value)
{
    Node *cur = *head;
    Node *prev = NULL;

    while (cur != NULL) {
        if (cur->value == value) {
            if (prev == NULL) {       // ลบหัว
                *head = cur->next;
            } else {
                prev->next = cur->next;   // ข้าม cur
            }
            free(cur);
            return 1;                 // ลบสำเร็จ
        }
        prev = cur;
        cur = cur->next;
    }
    return 0;                          // ไม่เจอ
}

free ทั้งลิสต์ — สำคัญมาก

void list_free(Node *head)
{
    Node *cur = head;
    while (cur != NULL) {
        Node *next = cur->next;   // ** เก็บ next ก่อน free cur **
        free(cur);
        cur = next;
    }
}

ต้องเก็บ cur->next ไว้ก่อน free(cur) — ถ้า free ก่อนแล้วอ่าน cur->next = use-after-free

ใช้งานครบวงจร

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

    list_push_back(&head, 1);
    list_push_back(&head, 2);
    list_push_back(&head, 3);
    list_push_front(&head, 0);

    list_print(head);             // 0 -> 1 -> 2 -> 3 -> NULL
    printf("ความยาว: %zu\n", list_length(head));

    list_remove(&head, 2);
    list_print(head);             // 0 -> 1 -> 3 -> NULL

    Node *found = list_find(head, 3);
    if (found) printf("เจอ %d\n", found->value);

    list_free(head);
    head = NULL;
    return 0;
}

รันด้วย ASan เสมอ:

gcc -std=c17 -Wall -Wextra -g -fsanitize=address list.c -o list && ./list

linked list เทียบ dynamic array

linked listdynamic array (บทที่ 40)
เพิ่ม/ลบหัวO(1)O(n) (เลื่อนของ)
เพิ่มท้ายO(n) (หรือ O(1) ถ้าเก็บ tail)O(1) amortized
เข้าถึง index iO(n) (เดินจากหัว)O(1)
หน่วยความจำ+8 ไบต์/node (pointer) + malloc แยกต่อเนื่อง cache-friendly
การใช้จริงเมื่อเพิ่ม/ลบตรงกลางบ่อย, ไม่รู้ขนาดค่าเริ่มต้น — เร็วกว่าในเคสส่วนใหญ่

ในทางปฏิบัติ dynamic array เร็วกว่าเกือบทุกกรณีเพราะ cache — ใช้ linked list เมื่อมีเหตุผลเฉพาะ

เรื่องที่คนมักพลาด

  • free(cur) แล้วอ่าน cur->next — use-after-free เก็บ next ไว้ก่อน
  • ลบ node แล้วไม่เชื่อม prev->next — ลิสต์ขาด, node ที่เหลือ leak
  • ลืม list_free — leak ทุก node (ASan/valgrind จับได้)
  • Node **head แต่ส่ง head ไม่ใช่ &head — ฟังก์ชันแก้ head ของผู้เรียกไม่ได้
  • struct Node { Node *next; } — Node typedef ยังไม่เสร็จตอนนั้น ต้อง struct Node *next
  • ไม่เช็ค node_create คืน NULL — malloc ล้มเหลวแล้ว deref NULL
  • loop while (cur->next) เมื่อ cur เป็น NULL (ลิสต์ว่าง) — crash เช็ค cur != NULL ก่อน

สรุป

  • node = struct { data; struct Node *next; }, สร้างด้วย malloc, ตัวสุดท้าย next = NULL
  • เพิ่มหัว O(1), เพิ่มท้าย O(n), เข้าถึง index O(n)
  • ฟังก์ชันที่แก้ head ต้องรับ Node **head และเรียกด้วย &head
  • ลบ: เก็บ prev, เชื่อม prev->next = cur->next, แล้ว free(cur)
  • list_free: เก็บ next ก่อน free(cur) เสมอ
  • dynamic array มักเร็วกว่า linked list ในทางปฏิบัติ (cache)

บทถัดไปว่าด้วย function pointer และ callback — ส่งฟังก์ชันเป็น argument, qsort และ dispatch table