C語言實現通用單鏈表：從接口設計到完整代碼實戰

C語言實現通用單鏈表：從接口設計到完整代碼實戰

單鏈表概述

單向鏈表是鏈表的一種，其特點是鏈接方向單向，訪問必須從頭部順序讀取。概念上可視為一系列連續元素，但由於動態分配（C語言用 malloc），實際記憶體中通常分散分布。

單鏈表接口定義

以下定義了 11 個核心操作接口，涵蓋初始化、銷毀、插入、刪除、查詢等功能：

1. list_init - 初始化鏈表

void list_init(List *list, void (*destroy)(void *data));

描述：初始化 list 指向的鏈表，必須在其他操作前調用。destroy 參數提供釋放動態數據的方法，若用 malloc 則設為 free。
複雜度：O(1)

2. list_destroy - 銷毀鏈表

void list_destroy(List *list);

描述：銷毀鏈表，移除所有元素並調用 destroy 釋放數據。
複雜度：O(n)

3. list_ins_next - 插入元素

int list_ins_next(List *list, ListElmt *element, const void *data);

描述：在 element 後插入元素，element 為 NULL 時插入頭部。成功返回 0，失敗 -1。
複雜度：O(1)

4. list_rem_next - 移除元素

int list_rem_next(List *list, ListElmt *element, void **data);

描述：移除 element 後的元素，element 為 NULL 時移除頭元素。data 指向被移除元素數據。
複雜度：O(1)

5-11. 宏操作：list_size、list_head、list_tail、list_is_head、list_is_tail、list_data、list_next

這些宏提供 O(1) 的快速訪問和檢測能力，如獲取大小、頭尾指針、判斷頭尾節點、獲取數據與下一節點。

單鏈表實現與分析

抽象數據類型頭文件 (list.h)

#ifndef LIST_H
#define LIST_H
#include <stdlib.h>

typedef struct ListElmt_ {
    void *data;
    struct ListElmt_ *next;
} ListElmt;

typedef struct List_ {
    int size;
    int (*match)(const void *key1, const void *key2);
    void (*destroy)(void *data);
    ListElmt *head;
    ListElmt *tail;
} List;

// 公共接口聲明
void list_init(List *list, void (*destroy)(void *data));
void list_destroy(List *list);
int list_ins_next(List *list, ListElmt *element, const void *data);
int list_rem_next(List *list, ListElmt *element, void **data);

#define list_size(list) ((list)->size)
#define list_head(list) ((list)->head)
#define list_tail(list) ((list)->tail)
#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)
#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define list_data(element) ((element)->data)
#define list_next(element) ((element)->next)
#endif

核心函數實現

初始化：將 size 歸零、設置 destroy、head/tail 置 NULL。

銷毀：循環移除頭節點並釋放數據，最後 memset 清零結構體。

插入：分配新節點，處理頭部插入和中間插入兩種情況，更新指針和 size。

刪除：處理刪除頭節點和非頭節點，正確維護 head/tail 指針，釋放節點內存。

完整測試代碼

測試代碼演示了鏈表的創建、插入、刪除、遍歷、查詢頭尾節點等操作，並最終銷毀鏈表。代碼遵循 C99 標準，包含詳細註釋。

補充：基礎單鏈表操作實現

文末還提供了兩個簡化版單鏈表實現：一個純 C 版本（含創建、顯示、查找、插入、刪除），一個 C++ 版本（含查找、插入、刪除、創建、遍歷），適合初學者理解基本原理。