雙向鏈表完整實作指南：從結構定義到增刪查改

雙向鏈表在每個節點增設 prev 指標，實現雙向遍歷。相較單向鏈表，插入/刪除操作無需從頭查找前驅，時間複雜度從 O(N) 降為 O(1)（已知目標節點時），是高頻增刪場景的首選。本文提供非循環雙向鏈表的完整 C 語言實作，涵蓋八大核心操作。

一、節點結構定義

typedef struct _DOUBLE_LINK_NODE {
    int data;
    struct _DOUBLE_LINK_NODE* prev;
    struct _DOUBLE_LINK_NODE* next;
} DOUBLE_LINK_NODE;

二、核心操作實作

1. 建立節點

DOUBLE_LINK_NODE* create_double_link_node(int value) {
    DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE));
    assert(pNode);
    memset(pNode, 0, sizeof(DOUBLE_LINK_NODE));
    pNode->data = value;
    return pNode;
}

2. 刪除整個鏈表（遞迴）

void delete_all_double_link_node(DOUBLE_LINK_NODE** ppHead) {
    if (!*ppHead) return;
    DOUBLE_LINK_NODE* pNext = (*ppHead)->next;
    free(*ppHead);
    delete_all_double_link_node(&pNext);
}

3. 查找資料

DOUBLE_LINK_NODE* find_data_in_double_link(const DOUBLE_LINK_NODE* pHead, int data) {
    const DOUBLE_LINK_NODE* pCur = pHead;
    while (pCur) {
        if (pCur->data == data) return (DOUBLE_LINK_NODE*)pCur;
        pCur = pCur->next;
    }
    return NULL;
}

4. 插入資料（尾插法）

STATUS insert_data_into_double_link(DOUBLE_LINK_NODE** ppHead, int data) {
    if (!ppHead) return FALSE;

    if (!*ppHead) { // 空表
        *ppHead = create_double_link_node(data);
        (*ppHead)->prev = (*ppHead)->next = NULL;
        return TRUE;
    }

    if (find_data_in_double_link(*ppHead, data)) return FALSE; // 唯一性

    DOUBLE_LINK_NODE* pNew = create_double_link_node(data);
    DOUBLE_LINK_NODE* pTail = *ppHead;
    while (pTail->next) pTail = pTail->next; // 找尾節點

    pNew->prev = pTail;
    pNew->next = NULL;
    pTail->next = pNew;
    return TRUE;
}

5. 刪除資料（核心優勢：O(1) 前驅存取）

STATUS delete_data_from_double_link(DOUBLE_LINK_NODE** ppHead, int data) {
    if (!ppHead || !*ppHead) return FALSE;

    DOUBLE_LINK_NODE* pTarget = find_data_in_double_link(*ppHead, data);
    if (!pTarget) return FALSE;

    if (pTarget == *ppHead) { // 刪除頭節點
        *ppHead = pTarget->next;
        if (*ppHead) (*ppHead)->prev = NULL;
    } else {
        pTarget->prev->next = pTarget->next; // 關鍵：直接訪問前驅
        if (pTarget->next) pTarget->next->prev = pTarget->prev;
    }

    free(pTarget);
    return TRUE;
}

6. 統計節點數

int count_number_in_double_link(const DOUBLE_LINK_NODE* pHead) {
    int count = 0;
    const DOUBLE_LINK_NODE* pCur = pHead;
    while (pCur) { ++count; pCur = pCur->next; }
    return count;
}

7. 列印資料

void print_double_link_node(const DOUBLE_LINK_NODE* pHead) {
    const DOUBLE_LINK_NODE* pCur = pHead;
    while (pCur) { printf("%d\n", pCur->data); pCur = pCur->next; }
}

三、進階思考：循環雙向鏈表與有序變體

本文實作的是非循環雙向鏈表。若改為循環雙向鏈表，需注意：

• 頭節點 prev 指向尾節點，尾節點 next 指向頭節點
• 空表時頭指標可指向哨兵節點，簡化邊界判斷
• 遍歷終止條件改為 pCur->next != pHead

若進一步要求有序循環雙向鏈表，插入時需從頭（或尾）查找合適位置，維持資料有序性，查找可優化為二分搜尋（配合跳表或平衡樹索引）。

雙向鏈表以空間換時間，雙向指標帶來的操作便利性，使其成為許多高效能資料結構（如 LRU Cache、Deque）的基石。