又來博客留下我的足跡了，哈哈哈，這次是對于雙向鏈表的理解

目錄

創建雙向鏈表：

申請結點：

雙向鏈表初始化：

雙向鏈表插入結點：

雙向鏈表刪除結點：

雙向鏈表的打印：

雙向鏈表的查找：

雙向鏈表的銷毀：

結語：

---

在雙向鏈表中有頭雙向循環，無頭雙向循環，有頭雙向不循環，無頭雙向不循環，而我將要介紹的是有頭雙向循環，別看名字長，其實就是只紙老虎，只要我們理解它的結構，問題自然迎刃而解了結構圖如下：

創建雙向鏈表：

從上面的結構圖我們不然發現，我們創建需要定義什么指針域和數據域

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;//指針域struct ListNode* next;//指針域LTDataType data;//數據域
}LTNode;

申請結點：

與單鏈表代碼差不多，將其指針域置空，就不再過多贅述

LTNode* BuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//申請空間if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;//賦值newnode->next = NULL;newnode->prev = NULL;return newnode;//返回創建的結點
}

雙向鏈表初始化：

我們只需將自己連向自己，下一個指向上一個，上一個指向下一個，如圖：

LTNode* LTInit()
{LTNode* phead = BuyNode(-1);//傳空，為phead申請空間phead->next = phead->prev;phead->prev = phead->next;return phead;//返回頭結點
}

雙向鏈表插入結點：

頭插：

我們先將新結點的后指針指向第一個結點的數據域，第一個結點的前指針指向新結點的數據域，新結點的前指針亦然，可能文字可能形容有點模糊，所以我們看下圖：

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);LTNode* Next = phead->next;//保存下一個結點的地址，防止丟失//新結點與后結點鏈接newnode->next = Next;Next->prev = newnode;//新結點與頭節點鏈接newnode->prev = phead;phead->next = newnode;
}

溫馨提示：如果沒有保存下一個結點的地址，則需先跟后結點鏈接，在與頭結點相連

尾插：

雙鏈表尾插相對于單鏈表的尾插來說要容易許多，因為我們可以輕松找到尾，然后改變指針指向即可，如下圖：

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);//創建新結點LTNode* tail = phead->prev;//找尾//尾結點與新結點相連newnode->prev = tail;tail->next = newnode;//新結點與頭結點相連newnode->next = phead;phead->prev = newnode;
}

在指定位置插入：

我們通常會在指定位置之前插入，找到指定位置前一個，然后改變指針方向即可，如圖：

void LTInsert(LTNode* phead, LTNode* pos, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);LTNode* front = pos->prev;//找到指定位置前一個結點//新結點與指定結點相連newnode->next = pos;pos->prev = newnode;//新節點與指定結點前一個結點相連front->next = newnode;newnode->prev = front;
}

雙向鏈表刪除結點：

頭刪：

我們先要判斷鏈表是否為空，如果為空就不用刪除了；因為之后要釋放刪除的結點，所以我們還需保存一下，這樣就可以了

bool LTEmpty(LTNode* phead)
{return phead == phead->next;
}
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//判斷鏈表是否為空LTNode* del = phead->next;LTNode* Next = phead->next->next;//第一結點的下一個結點與頭結點相連Next->prev = phead;phead->next = Next;free(del);//釋放掉這個結點del = NULL;
}

尾刪：

尾刪就比較容易了，將尾結點釋放，然后改變指針指向，就這樣完成了^ - ^

void LTPopBack(LTNode* phead)
{assert(phead);assert(phead != phead->next);//或assert(!LTEmpty(phead))LTNode* tail = phead->prev;LTNode* Pretail = tail->prev;//頭節點與尾結點的前一個結點相連Pretail->next = phead;phead->next = Pretail;free(tail);//釋放尾結點tail = NULL;
}

在指定位置刪除：

找到要刪除結點的前一個和后一個，然后兩個結點相互鏈接，這樣就能夠刪除了，如圖：

void LTErase(LTNode* phead, LTNode* pos)
{assert(phead);LTNode* front = pos->prev;//找到前結點LTNode* back = pos->next;//找到后結點//前結點和后結點相連front->next = back;back->prev = front;free(pos);//釋放指定節點pos = NULL;
}

雙向鏈表的打印：

提到打印，我們會用到遍歷循環，那循環結束的標志是什么呢？有一個好主意，我們可以先從第一個結點開始打印，然后向后循環遍歷，直至遍歷到頭結點，循環結束^_^，如下圖：

void LTPrint(LTNode* phead)
{LTNode* begin = phead->next;while (begin != phead)//循環繼續條件{printf("%d<=>", begin->data);begin = begin->next;}printf("\n");
}

雙向鏈表的查找：

遍歷一遍鏈表，然后找要查找的元素

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;//沒找到
}

雙向鏈表的銷毀：

將動態申請的空間釋放掉，并循環釋放每一個結點，防止內存泄漏的風險

void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;LTNode* next = cur->next;while (cur != phead){LTNode* next = cur->next;//防止找不到下一個結點free(cur);cur = next;}free(phead);//釋放頭結點
}

結語：

紙短情長，不盡依依，謝謝觀看！