雙向鏈表完整實作：非循環結構的增刪查改與核心邏輯解析

編輯：關於C語言

雙向鏈表在單向鏈表基礎上新增 prev 指標，使節點具備前向與後向導航能力。這對插入、刪除操作帶來便利（無需從頭遍歷尋找前驅），但也增加了指標維護的複雜度。本文實作一個非循環雙向鏈表，涵蓋節點建立、銷毀、查找、尾端插入、指定值刪除、統計與列印等操作。

一、節點結構定義

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

二、建立節點

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

三、銷毀整條鏈表

void delete_all_double_link_node(DOUBLE_LINK_NODE** pDLinkNode) {
    if (NULL == *pDLinkNode) return;
    DOUBLE_LINK_NODE* pNode = *pDLinkNode;
    *pDLinkNode = pNode->next;
    free(pNode);
    delete_all_double_link_node(pDLinkNode);
}

四、查找資料（迭代版）

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

五、尾端插入資料

檢查重複值後，遍歷至尾端並雙向連結新節點：

STATUS insert_data_into_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data) {
    if (NULL == ppDLinkNode) return FALSE;
    if (NULL == *ppDLinkNode) {
        DOUBLE_LINK_NODE* pNode = create_double_link_node(data);
        *ppDLinkNode = pNode;
        pNode->prev = pNode->next = NULL;
        return TRUE;
    }
    if (NULL != find_data_in_double_link(*ppDLinkNode, data)) return FALSE;

    DOUBLE_LINK_NODE* pNode = create_double_link_node(data);
    DOUBLE_LINK_NODE* pIndex = *ppDLinkNode;
    while (NULL != pIndex->next) pIndex = pIndex->next;

    pNode->prev = pIndex;
    pNode->next = pIndex->next; // NULL
    pIndex->next = pNode;
    return TRUE;
}

六、刪除指定值節點

需處理頭節點、中間節點、尾節點三種情況的雙向指標修正：

STATUS delete_data_from_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data) {
    if (NULL == ppDLinkNode || NULL == *ppDLinkNode) return FALSE;
    DOUBLE_LINK_NODE* pNode = find_data_in_double_link(*ppDLinkNode, data);
    if (NULL == pNode) return FALSE;

    if (pNode == *ppDLinkNode) { // 刪除頭節點
        if (NULL == pNode->next) *ppDLinkNode = NULL;
        else {
            *ppDLinkNode = pNode->next;
            (*ppDLinkNode)->prev = NULL;
        }
    } else { // 刪除中間或尾節點
        if (pNode->next) pNode->next->prev = pNode->prev;
        pNode->prev->next = pNode->next;
    }
    free(pNode);
    return TRUE;
}

七、統計與列印

int count_number_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode) {
    int count = 0;
    DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;
    while (NULL != pNode) { count++; pNode = pNode->next; }
    return count;
}

void print_double_link_node(const DOUBLE_LINK_NODE* pDLinkNode) {
    DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;
    while (NULL != pNode) { printf("%d\n", pNode->data); pNode = pNode->next; }
}