C語言雙向鏈表基礎操作完整實作指南

編輯：關於C語言

C語言雙向鏈表基礎操作完整實作指南

雙向鏈表是資料結構中極為重要的線性結構，每個節點同時擁有指向前驅與後繼節點的指標，使得正向與反向遍歷、任意位置插入刪除都能在 O(1) 時間內完成（已知位置前提下）。本文提供一份完整、可編譯執行的雙向鏈表實作，涵蓋初始化、節點建立、頭尾插刪、指定位置插刪、查找、反轉與銷毀等核心操作，並附上詳細註解與測試範例。

資料結構定義

// 頭文件 LinkList.h
#pragma once
typedef int DataType;

typedef struct LinkList {
    DataType _data;
    struct LinkList* _next;
    struct LinkList* _prev;
} LinkList, *pLinkList;

// 函數宣告
void InitList(pLinkList pNode);
pLinkList _BuyNode(pLinkList& pNode, DataType x);
void PrintList(pLinkList pHead);
void PushBack(pLinkList& pHead, DataType x);
void PopBack(pLinkList& pHead);
void PushFront(pLinkList& pHead, DataType x);
void PopFront(pLinkList& pHead);
pLinkList Find(pLinkList pHead, DataType x);
void Insert(pLinkList pos, DataType x);
void Erase(pLinkList& pHead, pLinkList pos);
void Reverse(pLinkList& pHead);
void DestroyList(pLinkList& pHead);

核心函數實作精要

節點建立與初始化

// 建立新節點
pLinkList _BuyNode(pLinkList& pNode, DataType x) {
    pNode = (pLinkList)malloc(sizeof(LinkList));
    pNode->_data = x;
    pNode->_next = NULL;
    pNode->_prev = NULL;
    return pNode;
}

// 初始化（傳入頭節點指標的指標）
void InitList(pLinkList pNode) {
    assert(pNode);
    if (pNode->_next == NULL) {
        pNode->_prev = NULL;
    }
}

尾插與尾刪

// 尾插
void PushBack(pLinkList& pHead, DataType x) {
    pLinkList head = pHead;
    if (head == NULL) {
        _BuyNode(pHead, x);
        return;
    }
    while (head->_next) {
        head = head->_next;
    }
    head->_next = _BuyNode(head->_next, x);
    head->_next->_prev = head;
}

// 尾刪
void PopBack(pLinkList& pHead) {
    pLinkList head = pHead;
    pLinkList tmp = NULL;
    if (pHead == NULL) {
        printf("鏈表已空！\n");
        return;
    }
    if (head->_next == NULL) {  // 僅一個節點
        free(head);
        pHead = NULL;
        return;
    }
    while (head->_next) {
        head = head->_next;
    }
    tmp = head->_prev;
    tmp->_next = NULL;
    free(head);
}

頭插與頭刪

// 頭插
void PushFront(pLinkList& pHead, DataType x) {
    pLinkList head = pHead;
    pLinkList tmp = pHead;
    if (pHead == NULL) {
        _BuyNode(pHead, x);
        return;
    }
    pHead = _BuyNode(head->_prev, x);
    pHead->_next = tmp;
}

// 頭刪
void PopFront(pLinkList& pHead) {
    pLinkList tmp = pHead;
    if (pHead == NULL) {
        printf("鏈表已空！\n");
        return;
    }
    pHead = pHead->_next;
    if (pHead) {
        pHead->_prev = NULL;
    }
    free(tmp);
}

指定位置插入與刪除

// 在 pos 節點之後插入
void Insert(pLinkList pos, DataType x) {
    pLinkList tmp = pos->_next;
    assert(pos);
    _BuyNode(pos->_next, x);
    pos->_next->_prev = pos;
    pos->_next->_next = tmp;
}

// 刪除 pos 節點
void Erase(pLinkList& pHead, pLinkList pos) {
    pLinkList tmp = pos;
    assert(pos);
    if (pos->_next == NULL) {  // 尾節點
        pos->_prev->_next = NULL;
        free(tmp);
        return;
    }
    if (pos == pHead) {  // 頭節點
        pHead = pHead->_next;
        pHead->_prev = NULL;
        free(pos);
        return;
    }
    tmp->_prev->_next = tmp->_next;
    tmp->_next->_prev = tmp->_prev;
    free(pos);
}

鏈表反轉與銷毀

// 反轉雙向鏈表
void Reverse(pLinkList& pHead) {
    pLinkList head = pHead;
    pLinkList tmp = pHead;
    if (pHead == NULL && pHead->_next == NULL) return;
    while (head) {
        tmp = head->_next;
        head->_next = head->_prev;
        head->_prev = tmp;
        if (head->_prev == NULL) pHead = head;
        head = tmp;
    }
}

// 銷毀整個鏈表
void DestroyList(pLinkList& pHead) {
    while (pHead) {
        PopFront(pHead);
    }
}

完整測試範例

// 主函數測試
#include "LinkList.h"
#include <stdio.h>

void test1() {
    pLinkList pHead = NULL;
    PushFront(pHead, 1);
    PushFront(pHead, 2);
    PushFront(pHead, 3);
    PushFront(pHead, 4);
    PushFront(pHead, 5);
    PrintList(pHead);  // 輸出: 5 4 3 2 1
    
    Insert(Find(pHead, 1), 6);  // 在 1 後插入 6
    Erase(pHead, Find(pHead, 2));  // 刪除節點 2
    PrintList(pHead);  // 輸出: 5 4 3 6 1
    
    Reverse(pHead);
    PrintList(pHead);  // 輸出: 1 6 3 4 5
    
    DestroyList(pHead);
    PrintList(pHead);  // 輸出: 鏈表為空!
}

int main() {
    test1();
    return 0;
}

常見錯誤與除錯技巧

指標參數傳遞：所有修改頭指標的函數必須傳遞 pLinkList&（指標的引用）或 pLinkList*（指標的指標），否則修改無法反映到呼叫端。
記憶體洩漏：刪除節點前務必 free，銷毀鏈表時逐一釋放所有節點。
空指標解引用：操作 _prev、_next 前必須檢查節點是否為 NULL。
邊界條件：單節點、空鏈表、頭尾節點操作需分開處理，避免邏輯錯誤。