C 語言資料結構實作：雙向鏈表完整原始碼與操作詳解

資料結構定義

typedef int Item;

typedef struct Node {
    Item data;
    struct Node *prev;
    struct Node *next;
} Node, *PNode, *Position;

typedef struct {
    PNode head;   // 虛擬頭節點
    PNode tail;   // 指向尾節點
    int size;     // 節點數
} DList;

採用帶虛擬頭節點的雙向鏈表，簡化邊界條件處理。

核心操作函數原型

關鍵演算法實作精要

初始化：建立虛擬頭節點

DList *InitList() {
    DList *list = malloc(sizeof(DList));
    PNode head = MakeNode(0); // data 無意義
    list->head = list->tail = head;
    list->size = 0;
    return list;
}

頭插法 InsFirst

PNode InsFirst(DList *list, PNode node) {
    node->next = list->head->next;
    node->prev = list->head;
    if (list->head->next) list->head->next->prev = node;
    list->head->next = node;
    if (list->tail == list->head) list->tail = node; // 空表情況
    list->size++;
    return node;
}

尾刪除 Remove

PNode Remove(DList *list) {
    if (list->size == 0) return NULL;
    PNode node = list->tail;
    node->prev->next = node->next; // node->next 為 NULL
    list->tail = node->prev;
    list->size--;
    return node; // 呼叫者負責 FreeNode
}

指定位置前插入 InsBefore

PNode InsBefore(DList *list, Position pos, PNode node) {
    node->prev = pos->prev;
    node->next = pos;
    pos->prev->next = node;
    pos->prev = node;
    list->size++;
    return node;
}

位置查找 LocatePos (1-based)

PNode LocatePos(DList *list, int i) {
    if (i < 1 || i > list->size) return NULL;
    PNode p = list->head;
    while (i--) p = p->next;
    return p;
}

遍歷框架

void ListTraverse(DList *list, void (*visit)(Item)) {
    for (PNode p = list->head->next; p; p = p->next)
        visit(p->data);
}

測試主程式流程

1. InitList() 建立空表
2. 輸入節點數 n 及各節點資料
3. InsFirst 建立首節點，後續 InsAfter 尾部追加
4. ListTraverse 列印驗證
5. DestroyList 釋放所有記憶體

記憶體管理提醒

• MakeNode → malloc，FreeNode → free
• ClearList 從尾部向前逐個 free
• DestroyList 先 ClearList 再 free(head) 最後 free(list)
• 所有公開函數均檢查空指標，健壯性較好

延伸練習

1. 實作 ReverseTraverse 反向列印
2. 新增 DeleteByValue(Item val) 刪除首個匹配節點
3. 將 Item 改為 void* 實現泛型容器
4. 對比單向鏈表、循環鏈表、陣列實現的優劣

總結

雙向鏈表透過 prev/next 雙向連結，支援 O(1) 頭尾插刪、雙向遍歷。虛擬頭節點統一邊界邏輯，是教學與工程常用技巧。掌握指標操作、記憶體管理、訪問者模式遍歷，即可靈活應用於各類動態資料集合。