您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言雙向鏈表完整實作：核心操作、反轉與記憶體管理

編輯：關於C

節點結構

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

核心操作函式

函式	功能	關鍵點
`_BuyNode`	配置並初始化節點	雙向指標皆設 NULL
`PushBack`	尾插	維護 `_prev` 指向前驅
`PushFront`	頭插	新節點 `_next` 指向舊頭，舊頭 `_prev` 指向新節點
`PopBack`	尾刪	透過 `_prev` 直接定位倒數第二節點
`PopFront`	頭刪	頭節點後移，新頭 `_prev` 設 NULL
`Insert(pos, val)`	指定節點後插入	四個指標重組：pos, pos->_next, newNode
`Erase(pos)`	刪除指定節點	處理頭/尾/中間三種情況
`Reverse`	整表反轉	交換每個節點 `_next`/`_prev`，更新頭指標
`DestroyList`	銷毀整表	反覆呼叫 `PopFront` 或雙指標遍歷釋放

關鍵操作圖解與程式碼

尾插 PushBack

void PushBack(pLinkList *pHead, int x) {
    pLinkList newNode = _BuyNode(x);
    if (!*pHead) { *pHead = newNode; return; }
    pLinkList tail = *pHead;
    while (tail->_next) tail = tail->_next;
    tail->_next = newNode;
    newNode->_prev = tail;
}

頭插 PushFront

void PushFront(pLinkList *pHead, int x) {
    pLinkList newNode = _BuyNode(x);
    newNode->_next = *pHead;
    if (*pHead) (*pHead)->_prev = newNode;
    *pHead = newNode;
}

中間插入 Insert（在 pos 之後）

void Insert(pLinkList pos, int x) {
    assert(pos);
    pLinkList newNode = _BuyNode(x);
    newNode->_next = pos->_next;
    newNode->_prev = pos;
    if (pos->_next) pos->_next->_prev = newNode;
    pos->_next = newNode;
}

刪除節點 Erase

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

整表反轉 Reverse

void Reverse(pLinkList *pHead) {
    pLinkList cur = *pHead;
    pLinkList tmp = NULL;
    while (cur) {
        tmp = cur->_next;       // 保存下一個
        cur->_next = cur->_prev; // 交換 next/prev
        cur->_prev = tmp;
        if (!cur->_prev) *pHead = cur; // 當 prev 為 NULL 時，cur 是新頭
        cur = tmp;
    }
}

測試驗證

int main() {
    pLinkList head = NULL;
    PushFront(&head, 5); PushFront(&head, 4); PushFront(&head, 3);
    PushFront(&head, 2); PushFront(&head, 1); // 1 2 3 4 5
    PrintList(head);

    Insert(Find(head, 1), 6); // 1 6 2 3 4 5
    Erase(&head, Find(head, 2)); // 1 6 3 4 5
    PrintList(head);

    Reverse(&head); // 5 4 3 6 1
    PrintList(head);

    DestroyList(&head);
    PrintList(head); // 空
    return 0;
}

雙向 vs 單向鏈表比較

操作	單向	雙向
尾插	O(n)	O(n) / O(1) 若維護尾指標
尾刪	O(n) 需找前驅	O(1) 透過 _prev
指定節點前插	O(n) 需找前驅	O(1) 透過 _prev
反轉	三指標法	交換 next/prev
空間	1 指標	2 指標