1 線性表

1.4 雙向鏈表（Double Linked List）

雙向鏈表的結點中有兩個指針域，一個指向直接后繼，另一個指向直接前驅，主要是為了解決前向查找的問題。

雙向鏈表結構：

書籍和視頻教程都只講解了插入和刪除的算法，這里也實現這兩個算法。

一些常量和元素和前面類似，結點需要多一個前驅指針，結點結構代碼如下：

// 雙向鏈表的結點結構
typedef struct DuLNode
{ElemType data;                // 結點數據，ElemType類型struct DuLNode *prior, *next; // 指向下一個結點的指針
} DuLNode, *DuLinkList;           // DuLinkList 是指向 DuLNode 結構的指針類型，表示單鏈表的頭結點指針

另外為了方便查看插入的效果，需要初始化雙向鏈表，和插入一些數據方便測試，這里使用尾插法進行處理，尾插法的實現和前面基本類似，就是新結點要設置相應的前驅：

// 尾插法創建雙向鏈表
Status CreateListTail(DuLinkList *L, int n)
{*L = (DuLinkList)malloc(sizeof(DuLNode)); // 創建頭結點if (*L == NULL){return OVERFLOW;}(*L)->next = NULL; // 初始化頭結點的next指針為NULLDuLNode *p = *L; // p 指向頭結點for (int i = 1; i <= n; i++){// 創建一個新結點DuLNode *newNode = (DuLNode *)malloc(sizeof(DuLNode));if (!newNode) // 如果內存分配失敗return OVERFLOW;newNode->data.x = i; // 將數據賦值給新結點// 插入新結點newNode->next = NULL; // 新結點的后繼指針置空newNode->prior = p;   // 新結點的前驅指針指向當前結點p->next = newNode;    // 當前結點的后繼指針指向新結點p = newNode;          // p 指向新插入的結點}return OK;
}

還有插入和刪除都涉及另外一個算法——獲取第 i 個結點，這里補充一下：

// 獲取第 i 個結點，并返回結點指針
DuLNode *GetElem_Dul(DuLinkList *L, int i)
{if (i < 1) // i 值不合法return NULL;DuLNode *p = (*L)->next; // 從頭結點的下一個結點開始遍歷int j = 1;               // 計數器，從1開始while (p != NULL && j < i) // 遍歷到第i個結點 并且 當前結點不為空{p = p->next; // 移動到下一個結點j++;}if (p == NULL || j > i)return NULL;return p;
}

1.4.1 插入

插入的步驟要比單鏈表多設置幾個指針指向，主要的難點在于順序很重要，如果順序不對，可能導致實際的指針被提前修改，無法獲取到對應的結點。

【算法步驟】

1. 將新結點的前驅指針指向當前結點的前驅結點。①
2. 將當前結點的前驅結點的后繼指針指向新結點。②
3. 將新結點的后繼指針指向當前結點。③
4. 將當前結點的前驅指針指向新結點。④

【代碼實現】

// 插入結點，在 i-1 和 i 之間插入一個結點，新結點的位置就是 i
Status ListInsert(DuLinkList *L, int i, ElemType e)
{DuLNode *p;if (!(p = GetElem_Dul(L, i))) // 獲取第 i 個結點return ERROR;DuLNode *newNode = (DuLNode *)malloc(sizeof(DuLNode)); // 創建新結點if (newNode == NULL)return OVERFLOW;newNode->data = e;         // 設置新結點的數據newNode->prior = p->prior; // 將新結點的前驅指針指向當前結點的前驅結點p->prior->next = newNode;  // 將當前結點的前驅結點的后繼指針指向新結點newNode->next = p;         // 將新結點的后繼指針指向當前結點p->prior = newNode;        // 將當前結點的前驅指針指向新結點return OK;
}

【算法分析】

時間復雜度主要受 GetElem_Dul 影響，因此為 O(n) 。

1.4.2 刪除

【算法步驟】

1. 將前驅結點的后繼指針指向當前結點的后繼結點。①
2. 如果當前結點不是最后一個結點，將后繼結點的前驅指針指向當前結點的前驅結點。②

【代碼實現】

// 刪除第 i 個結點
Status ListDelete(DuLinkList *L, int i)
{DuLNode *p;if (!(p = GetElem_Dul(L, i))) // 獲取第 i 個結點return ERROR;p->prior->next = p->next;      // 將前驅結點的后繼指針指向當前結點的后繼結點if (p->next != NULL)           // 如果當前結點不是最后一個結點p->next->prior = p->prior; // 將后繼結點的前驅指針指向當前結點的前驅結點free(p); // 釋放當前結點內存return OK;
}

【算法分析】

時間復雜度主要受 GetElem_Dul 影響，因此為 O(n) 。