C語言通用資料結構實作：單向鏈結清單完整介面與程式碼

抽象資料型別 (ADT) 設計：不透明指標、函數指標銷毀、巨集存取、完整測試

實作通用單向鏈結清單，支援任意資料類型，提供標準容器介面：初始化、銷毀、插入、刪除、遍歷、查詢。

介面設計 (list.h)

#ifndef LIST_H
#define LIST_H

#include 

// 前向宣告
typedef struct ListElmt_ ListElmt;
typedef struct List_ List;

// 結點結構 (內部使用)
struct ListElmt_ {
    void *data;
    struct ListElmt_ *next;
};

// 清單結構
struct List_ {
    int size;
    int (*match)(const void *key1, const void *key2); // 比較函數
    void (*destroy)(void *data);                      // 銷毀函數
    ListElmt *head;
    ListElmt *tail;
};

// 公共介面
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);

// 巨集存取 (O(1))
#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)
#define list_is_tail(element)       ((element)->next == NULL)
#define list_data(element)          ((element)->data)
#define list_next(element)          ((element)->next)

#endif

核心實作 (list.c)

#include "list.h"
#include 

void list_init(List *list, void (*destroy)(void *data)) {
    list->size = 0;
    list->destroy = destroy;
    list->head = NULL;
    list->tail = NULL;
}

void list_destroy(List *list) {
    void *data;
    while (list_size(list) > 0) {
        if (list_rem_next(list, NULL, &data) == 0 && list->destroy) {
            list->destroy(data); // 呼叫使用者提供的釋放函數
        }
    }
    memset(list, 0, sizeof(List)); // 防禦性清零
}

int list_ins_next(List *list, ListElmt *element, const void *data) {
    ListElmt *new_elmt = (ListElmt*)malloc(sizeof(ListElmt));
    if (!new_elmt) return -1;
    
    new_elmt->data = (void*)data;
    
    if (element == NULL) { // 插入頭部
        if (list_size(list) == 0)
            list->tail = new_elmt;
        new_elmt->next = list->head;
        list->head = new_elmt;
    } else { // 插入指定節點後
        if (element->next == NULL)
            list->tail = new_elmt;
        new_elmt->next = element->next;
        element->next = new_elmt;
    }
    list->size++;
    return 0;
}

int list_rem_next(List *list, ListElmt *element, void **data) {
    if (list_size(list) == 0) return -1;
    
    ListElmt *old_elmt;
    
    if (element == NULL) { // 移除頭部
        *data = list->head->data;
        old_elmt = list->head;
        list->head = list->head->next;
        if (list_size(list) == 1)
            list->tail = NULL;
    } else { // 移除指定節點後
        if (element->next == NULL) return -1;
        *data = element->next->data;
        old_elmt = element->next;
        element->next = element->next->next;
        if (element->next == NULL)
            list->tail = element;
    }
    
    free(old_elmt);
    list->size--;
    return 0;
}

測試程式 (main.c)

#include 
#include 
#include "list.h"

static void print_list(const List *list) {
    ListElmt *elmt = list_head(list);
    int i = 0;
    while (1) {
        int *data = (int*)list_data(elmt);
        printf("list[%03d] = %03d\n", i++, *data);
        if (list_is_tail(elmt)) break;
        elmt = list_next(elmt);
    }
    printf("Size: %d\n\n", list_size(list));
}

int main() {
    List list;
    list_init(&list, free); // 使用 free 釋放 int*
    
    // 1. 头插法建立 10~1
    for (int i = 10; i > 0; i--) {
        int *data = (int*)malloc(sizeof(int));
        *data = i;
        list_ins_next(&list, NULL, data);
    }
    print_list(&list);
    
    // 2. 移除第 8 個節點後的元素
    ListElmt *elmt = list_head(&list);
    for (int i = 0; i < 7; i++) elmt = list_next(elmt);
    int *removed;
    list_rem_next(&list, elmt, (void**)&removed);
    printf("Removed: %d\n", *removed);
    free(removed);
    print_list(&list);
    
    // 3. 尾部插入 11
    int *data = (int*)malloc(sizeof(int));
    *data = 11;
    list_ins_next(&list, list_tail(&list), data);
    print_list(&list);
    
    // 4. 移除頭部後
    list_rem_next(&list, list_head(&list), (void**)&removed);
    free(removed);
    print_list(&list);
    
    // 5. 頭部插入 12
    *data = 12;
    list_ins_next(&list, NULL, data);
    print_list(&list);
    
    // 6. 移除第 4 個
    elmt = list_head(&list);
    elmt = list_next(elmt); elmt = list_next(elmt);
    list_rem_next(&list, elmt, (void**)&removed);
    free(removed);
    print_list(&list);
    
    // 7. 測試巨集
    printf("is_head(head): %d\n", list_is_head(&list, list_head(&list)));
    printf("is_head(tail): %d\n", list_is_head(&list, list_tail(&list)));
    printf("is_tail(tail): %d\n", list_is_tail(list_tail(&list)));
    printf("is_tail(head): %d\n", list_is_tail(list_head(&list)));
    
    list_destroy(&list);
    return 0;
}

設計亮點

擴展方向

• 雙向鏈結清單 (prev 指標)
• 迭代器抽象 (外部遍歷狀態)
• 排序插入 (配合 match)
• 執行緒安全版本 (鎖/無鎖)
• 記憶體池分配器整合