前言

假期時(shí)間因?yàn)闉閷W(xué)校開學(xué)考試做準(zhǔn)備所以一直沒更新博客，今天開始博客會(huì)陸續(xù)更新。

雙向鏈表

之前我們說過了順序表和單鏈表，這次介紹雙向鏈表，雙向鏈表在使用上要比單鏈表簡單，結(jié)構(gòu)比單鏈表復(fù)雜一些，需要兩個(gè)指針域，其結(jié)構(gòu)如下圖，其中頭結(jié)點(diǎn)數(shù)據(jù)域不動(dòng)（不要存放指針長度一類因?yàn)橛袝r(shí)候我們不確定鏈表節(jié)點(diǎn)數(shù)據(jù)類型，如果是char類型而節(jié)點(diǎn)數(shù)大于128，那么就會(huì)出現(xiàn)bug），帶有頭結(jié)點(diǎn)可方便對其操作。

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

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

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

鏈表頭結(jié)點(diǎn)的創(chuàng)建

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

這里別忘了是雙向鏈表，要給兩個(gè)指針都賦值，因?yàn)槭穷^結(jié)點(diǎn)（PS：頭結(jié)點(diǎn)數(shù)據(jù)域一般是垃圾值）所以就指向自己。

節(jié)點(diǎn)尾插與尾刪

// 雙向鏈表尾插
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;
}

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

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

尾插時(shí)不要忘了讓節(jié)點(diǎn)指向頭結(jié)點(diǎn)。

節(jié)點(diǎn)頭插與頭刪

// 雙向鏈表頭插
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;
}

這里注意哈，鏈表的頭插與頭刪是在頭結(jié)點(diǎn)之后位置進(jìn)行，這里例出一幅頭插圖作為參考（藝術(shù)細(xì)胞為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é)點(diǎn)的下一個(gè)節(jié)點(diǎn)。

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

// 雙向鏈表在pos的前面進(jìn)行插入
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é)點(diǎn)
void ListErase(ListNode* pos)
{pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);
}

這里還是注意一下代碼順序無其他重點(diǎn)。

鏈表節(jié)點(diǎn)查找

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

若最后沒有找到該數(shù)值則返回頭結(jié)點(diǎn)。

雙向鏈表的銷毀

// 雙向鏈表銷毀
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;
}

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

鏈表的打印

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

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

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