雙向鏈結串列 (C 語言) 完整詳解：結構、操作、通用實現與巨集擴展技巧

編輯：關於C語言

一、雙向鏈結串列基本概念

每個節點包含三個域：data (資料)、prior (前驅指標)、next (後繼指標)。兩條鏈向相反方向，支援雙向遍歷，插入/刪除操作更靈活 (O(1))。通常帶「頭節點」簡化邊界處理，頭尾相連可形成「雙向循環鏈結串列」。

二、節點結構與型別定義

typedef struct DListNode {
    DataType data;                 // 資料型別自定
    struct DListNode *prior, *next; // 前驅、後繼指標
} DListNode, *DLinkList;

DLinkList head; // 頭指標

三、核心操作算法 (帶頭節點)

1. 前插操作：在節點 `*p` 前插入值為 `x` 的新節點

void DInsertBefore(DListNode *p, DataType x) {
    DListNode *s = (DListNode*)malloc(sizeof(DListNode)); // ① 分配
    s->data = x;                      // ② 賦值
    s->prior = p->prior;              // ③ 新節點前驅指向 p 原前驅
    s->next = p;                      // ④ 新節點後繼指向 p
    p->prior->next = s;               // ⑤ 原前驅節點的後繼指向 s
    p->prior = s;                     // ⑥ p 的前驅指向 s
}

關鍵：步驟 ⑤⑥ 順序不可顛倒。先斷開原連結再建立新連結會導致丟失鏈結。

2. 刪除節點 `*p` (非終端節點)

void DDeleteNode(DListNode *p) {
    p->prior->next = p->next; // ① 前驅節點跳過 p 指向後繼
    p->next->prior = p->prior; // ② 後繼節點跳過 p 指向前驅
    free(p);                  // ③ 釋放記憶體
}

雙向鏈結串列插入/刪除必須同時維護 prior 和 next 兩個方向，時間複雜度 O(1)。

四、通用雙向鏈結串列實現：巨集擴展技巧 (精華)

將「鏈結串列節點」與「業務資料」解耦，透過巨集將標準節點嵌入任意結構體，實現零侵入式複用。

核心資料結構

typedef struct tagSTDNODE { STDNODE *lpPrev, *lpNext; } STDNODE, *LPSTDNODE;
typedef struct tagSTDLIST { LPSTDNODE lpHead, lpTail; } STDLIST, *LPSTDLIST;

// 初始化巨集
#define NODE_INITIALIZER ((STDNODE){ .lpPrev=NULL, .lpNext=NULL })
#define LIST_INITIALIZER ((STDLIST){ .lpHead=NULL, .lpTail=NULL })
#define DECLARELISTNODE() STDNODE __snStdNode
#define INIT_LISTNODE()   __snStdNode = NODE_INITIALIZER

核心 API (部分)

// 头插、尾插、指定節點後插、頭彈、尾彈、刪除節點、合併鏈結串列...
void StdListPushFront(LPSTDLIST lpList, LPSTDNODE lpNode);
void StdListPushBack (LPSTDLIST lpList, LPSTDNODE lpNode);
void StdListInsert   (LPSTDLIST lpList, LPSTDNODE lpAfter, LPSTDNODE lpNode);
LPSTDNODE StdListPopFront(LPSTDLIST lpList);
LPSTDNODE StdListPopBack (LPSTDLIST lpList);
LPSTDNODE StdListRemove  (LPSTDLIST lpList, LPSTDNODE lpNode);
LPSTDLIST StdListCombine (LPSTDLIST lpList1, LPSTDLIST lpList2);

應用範例：訊息佇列

// 定義業務節點，嵌入標準節點
typedef struct tagMSGNODE {
    DECLARELISTNODE(); // 嵌入標準節點
    HWND hWnd; UINT uMsg; WPARAM wParam; LPARAM lParam;
} MSGNODE, *LPMSGNODE;

// 訊息佇列直接用標準鏈結串列結構
STDLIST lstMsgQueue;

// 使用
LPMSGNODE lpMsgNode = (LPMSGNODE)MemAlloc(sizeof(MSGNODE));
INIT_LISTNODE(); // 初始化嵌入節點
lpMsgNode->hWnd = hWnd; lpMsgNode->uMsg = WM_PAINT;
StdListPushBack(&lstMsgQueue, (LPSTDNODE)lpMsgNode); // 入佇列

LPMSGNODE lpMsgNode = (LPMSGNODE)StdListPopFront(&lstMsgQueue); // 出佇列