C語言，鏈表

C++實現單向鏈表

深入理解Linux內核鏈表

跟單鏈表不同，雙鏈表的節點包含兩個指針，一個指針指向上一個元素，一個指針指向下一個元素。

▌如下圖

學習數據結構的時候，要像認識一個人一樣，要了解這個人有什么特點，比如喜歡打球，喜歡喝酒之類的。學習數據結構也是一樣，要了解數據結構的特點。

我們要學習雙鏈表，需要搞明白鏈表這幾個特點

創建鏈表

往鏈表插入數據

刪除鏈表中的某個數據

刪除整個鏈表

查找鏈表

反轉鏈表

▌先看看如何創建一個鏈表

創建一個鏈表無非就是搞定鏈表頭，沒有頭的鏈表就是死鏈表，有頭就表示這個鏈表是存在的。當然了，可能會存在循環鏈表，只有位置，沒有固定的頭指針。

創建一個pHead，并且以后pHead頭指針保持不動，就表示我們創建好了一個鏈表頭指針。

typedef?struct?Node{struct?Node?*prev;struct?Node?*next;int?elements; }pNode;pNode?*?CreateHead(void) {pNode?*head?=?NULL;head?=?(pNode?*)malloc(sizeof(struct?Node));head->next?=?NULL;head->prev?=?NULL;return?head; }

▌插入元素

插入元素的方式有多種，可以頭插，可以尾插，也可以任意插，我只寫了簡單的插入方式-尾插。

int?InsertElement(pNode?*head,int?element) {if(head?==?NULL){PRINTK_LINK("Head?NULL\n");return?(-1);}pNode?*?pTemp?=?head;while(pTemp->next?!=?NULL){pTemp?=?pTemp->next;}pNode?*?pElement?=?(pNode?*)malloc(sizeof(struct?Node));pElement->elements?=?element;pTemp->next?=?pElement;pElement->prev?=?pTemp;PRINTK_LINK("Element:%d\n",element);return?(0); }

▌遍歷一個鏈表

遍歷鏈表是常規的操作，但是遍歷鏈表的方法有很多種，可以從頭開始遍歷，可以從尾部開始，在涉及二分查找的時候可以從中間某個位置開始遍歷。雖然方法很多，但是我只寫了一種方法，就是從頭開始遍歷鏈表，因為是最簡單的。

int?TraverseLink(pNode?*head) {if(head?==?NULL){PRINTK_LINK("Head?NULL\n");return?(-1);}pNode?*?pTemp?=?head;while(pTemp->next?!=?NULL){pTemp?=?pTemp->next;PRINTK_LINK("Element:%d\n",pTemp->elements);}return?(0); }

▌刪除鏈表

刪除整個鏈表是把鏈表的每個元素都刪除，并且把頭也刪除，并且把頭指針指向NULL。如果需要找到鏈表中的某個元素并刪除，就需要先找到鏈表中的元素，刪除掉，并且把前后的兩個元素連在一起。

int?DeleteLink(pNode?*head) {if(head?==?NULL){PRINTK_LINK("Head?NULL\n");return?(-1);}pNode?*?pTemp?=?head;while(pTemp->next?!=?NULL){pTemp?=?pTemp->next;}while(pTemp?!=?NULL){free(pTemp); pTemp = NULL;pTemp?=?pTemp->prev;}return?(0); }

▌完整代碼

#include?"stdio.h" #include?"string.h" #include?"stdlib.h"#define?LOG_TAG?"[LINK]:?%s()?line:?%d?" #define?PRINTK_LINK(fmt,?args...)??printf(LOG_TAG?fmt,?__FUNCTION__,?__LINE__,??##args)typedef?struct?Node{struct?Node?*prev;struct?Node?*next;int?elements; }pNode;pNode?*?CreateHead(void) {pNode?*head?=?NULL;head?=?(pNode?*)malloc(sizeof(struct?Node));head->next?=?NULL;head->prev?=?NULL;return?head; }int?InsertElement(pNode?*head,int?element) {if(head?==?NULL){PRINTK_LINK("Head?NULL\n");return?(-1);}pNode?*?pTemp?=?head;while(pTemp->next?!=?NULL){pTemp?=?pTemp->next;}pNode?*?pElement?=?(pNode?*)malloc(sizeof(struct?Node));pElement->elements?=?element;pTemp->next?=?pElement;pElement->prev?=?pTemp;PRINTK_LINK("Element:%d\n",element);return?(0); }int?TraverseLink(pNode?*head) {if(head?==?NULL){PRINTK_LINK("Head?NULL\n");return?(-1);}pNode?*?pTemp?=?head;while(pTemp->next?!=?NULL){pTemp?=?pTemp->next;PRINTK_LINK("Element:%d\n",pTemp->elements);}return?(0); }int?DeleteLink(pNode?*head) {if(head?==?NULL){PRINTK_LINK("Head?NULL\n");return?(-1);}pNode?*?pTemp?=?head;while(pTemp->next?!=?NULL){pTemp?=?pTemp->next;}while(pTemp?!=?NULL){free(pTemp);pTemp?=?pTemp->prev;}return?(0); }int?main() {pNode?*?pHead?=?CreateHead();InsertElement(pHead,13);InsertElement(pHead,8);InsertElement(pHead,0);InsertElement(pHead,4);InsertElement(pHead,485);InsertElement(pHead,94);TraverseLink(pHead);DeleteLink(pHead);return?0; }

▌程序輸出

ubuntu1804:~/c$?gcc?shuanglianbiao.c?&&?./a.out [LINK]:?InsertElement()?line:?40?Element:13 [LINK]:?InsertElement()?line:?40?Element:8 [LINK]:?InsertElement()?line:?40?Element:0 [LINK]:?InsertElement()?line:?40?Element:4 [LINK]:?InsertElement()?line:?40?Element:485 [LINK]:?InsertElement()?line:?40?Element:94 [LINK]:?TraverseLink()?line:?56?Element:13 [LINK]:?TraverseLink()?line:?56?Element:8 [LINK]:?TraverseLink()?line:?56?Element:0 [LINK]:?TraverseLink()?line:?56?Element:4 [LINK]:?TraverseLink()?line:?56?Element:485 [LINK]:?TraverseLink()?line:?56?Element:94

▌總結

我上面的代碼只設計了鏈表頭，如果設計鏈表尾部指針，應用會更加靈活。

相比于單鏈表，雙鏈表的操作會更加靈活，當然，每一個節點都需要新增一個指向于上一個位置的指針。

雙鏈表還可以把頭尾連接起來變成一個環形隊列。

鏈表相對于數組來說，插入和刪除數據非常快，因為不需要移動數據，只需要改變指針的指向。

雙鏈表內存利用率高，如果是內存緊張的硬件設備，使用鏈表操作可以節省內存。相對于數組，鏈表可以做到按需分配內存。

鏈表是一種基礎的數據結構，建議做到自己能寫出一個鏈表，不要求十全十美，我曾經面試遇到讓我手擼一個棧。相對于那些C語言基礎，寫代碼更能彰顯程序員的技術。

---

推薦閱讀：

專輯|Linux文章匯總

專輯|程序人生

專輯|C語言

我的知識小密圈

關注公眾號，后臺回復「1024」獲取學習資料網盤鏈接。

歡迎點贊，關注，轉發，在看，您的每一次鼓勵，我都將銘記于心~

總結

以上是生活随笔為你收集整理的手撸双链表，图解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。