前言

假期時間因為為學校開學考試做準備所以一直沒更新博客，今天開始博客會陸續(xù)更新。

雙向鏈表

之前我們說過了順序表和單鏈表，這次介紹雙向鏈表，雙向鏈表在使用上要比單鏈表簡單，結構比單鏈表復雜一些，需要兩個指針域，其結構如下圖，其中頭結點數據域不動（不要存放指針長度一類因為有時候我們不確定鏈表節(jié)點數據類型，如果是char類型而節(jié)點數大于128，那么就會出現bug），帶有頭結點可方便對其操作。

雙向鏈表節(jié)點代碼如下：

typedef int LTDataType;
typedef struct ListNode {struct ListNode* prev;struct ListNode* next;LTDataType data;
}LTNode;

與單鏈表相同無非是雙向鏈表的增刪改查。

鏈表頭結點的創(chuàng)建

ListNode* ListCreate()
{ListNode* head = (ListNode*)malloc(sizeof(ListNode));head->next = head;head->prev = head;return head;
}

這里別忘了是雙向鏈表，要給兩個指針都賦值，因為是頭結點（PS：頭結點數據域一般是垃圾值）所以就指向自己。

節(jié)點尾插與尾刪

// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{ListNode* tail = pHead->prev;ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));newnode->data = x;tail->next = newnode;newnode->prev = tail;newnode->next = pHead;pHead->prev = newnode;
}

這里就體現出雙向鏈表的優(yōu)勢，我們不用遍歷就可以直接找到鏈表的尾結點。

// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{ListNode* tail = pHead->prev;ListNode* TailPrev = tail->prev;free(tail);TailPrev->next = pHead;pHead->prev = TailPrev;
}

尾插時不要忘了讓節(jié)點指向頭結點。

節(jié)點頭插與頭刪

// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));newnode->data = x;newnode->next = pHead->next;pHead->next->prev = newnode;pHead->next = newnode;newnode->prev = pHead;
}

這里注意哈，鏈表的頭插與頭刪是在頭結點之后位置進行，這里例出一幅頭插圖作為參考（藝術細胞為0后續(xù)可能解鎖畫圖軟件，這里先湊合看）。

// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{ListNode* cur = (ListNode*)malloc(sizeof(ListNode));cur = pHead->next;pHead->next = cur->next;cur->next->prev = pHead;free(cur);
}

頭插和頭刪要注意順序，否則可能找不到頭結點的下一個節(jié)點。

特定位置插入或刪除節(jié)點

// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));newnode->data = x;newnode->next = pos;newnode->prev = pos->prev;pos->prev->next = newnode;pos->prev = newnode;
}
// 雙向鏈表刪除pos位置的節(jié)點
void ListErase(ListNode* pos)
{pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);
}

這里還是注意一下代碼順序無其他重點。

鏈表節(jié)點查找

// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{ListNode* cur = pHead->next;while (cur != pHead){if (cur->data == x)return cur;cur = cur->next;}return pHead;
}

若最后沒有找到該數值則返回頭結點。

雙向鏈表的銷毀

// 雙向鏈表銷毀
void ListDestory(ListNode* pHead)
{ListNode* newhead = pHead->next;ListNode* cur = newhead->next;while (cur->next!=pHead){free(newhead);newhead = cur;cur = newhead->next;}free(pHead);pHead == NULL;
}

這里別忘了最后刪除并置空頭結點，置空頭結點的原因是使用者在主函數還有頭結點的地址，但此時頭結點已被釋放（野指針），若再次調用頭結點則可能出現bug。

鏈表的打印

// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{ListNode* newnode = pHead->next;while (newnode!=pHead){printf("%d ", newnode->next->data);newnode = newnode->next;}
}

比較簡單，不做贅述。
雙向鏈表許多函數的while循環(huán)是判斷其節(jié)點是否與頭結點相等，而不是其節(jié)點是否為空，這里要注意與單鏈表區(qū)分，最后代碼其實還應該加上斷言（assert）函數判斷是否為空，但博主這里沒有加（是故意的還是不小心的）。

這里純粹是懶得加了，這個習慣不是很好，大家不要學我，最好還是自己加一下。
最后期待你的三連，若有錯誤歡迎私信或評論區(qū)指出。