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 && ./listlinked list เทียบ dynamic array
| linked list | dynamic array (บทที่ 40) | |
|---|---|---|
| เพิ่ม/ลบหัว | O(1) | O(n) (เลื่อนของ) |
| เพิ่มท้าย | O(n) (หรือ O(1) ถ้าเก็บ tail) | O(1) amortized |
| เข้าถึง index i | O(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; }—Nodetypedef ยังไม่เสร็จตอนนั้น ต้อง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