【 聲明：版權所有，歡迎轉載。 ?聯系信箱：yiluohuanghun@gmail.com】

? 自之前寫的兩篇關于“數據結構與算法”的博文發表以后，就有兩個博友發私信給我探討我的這個分類，有博友說數據結構怎么能和算法在一起呢？其實吧，我倒感覺數據結構跟算法的關系就好比好基友是一輩子的關系。他們患難見真情、他們生死不相棄……事實上，數據結構和算法也有類似的關系。只談數據結構，我們可以在很短的時間內就把幾種重要的數據結構介紹完。不過聽完后，你可能沒啥感覺，不知道這些數據結構有啥用處。但如果我們把相應的算法結合起來講一講，演示一下，你就會發現，甚至開始感慨：原來解決計算機問題是如此的美妙！

這篇文章我主要聊一下雙向鏈表。

? ?雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。雙向鏈表是指在前驅和后繼方向都能游歷(遍歷)的線性鏈表。雙向鏈表每個結點結構：

? ?雙向鏈表通常采用帶表頭結點的循環鏈表形式。

? ?其通常的數據結構如下：

1 2 3 4 5 6

typedef?struct?_DOUBLE_LINK_NODE { ????int?data; ????struct?_DOUBLE_LINK_NODE? *prev; ????struct?_DOUBLE_LINK_NODE? *next; };

? ?鏈表中的每個結點至少有三個域：一個雙向鏈表有一個表頭結點，由鏈表的表頭指針first指示，它的data域或者不放數據，或者存放一個特殊要求的數據；它的lLink指向雙向鏈表的最后一個結點，它的lLink指向雙向鏈表的最前端的第一個結點。

結點指向 p == p→lLink→rLink == p→rLink→lLink

? ?有很多人不解，為何要有雙向鏈表的存在呢？下面我們可以再看一幅圖：

? ?這貨我們叫它火車，我記得我第一次做火車的時候遇到過一個現象，就是火車正在往前走，到達一個站后，又往后走了一站，但是當時讓我吃驚的是為什么火車并沒有掉頭就能往回走，在后來我才明白原來是火車是兩個頭都可以連接火車頭的，這也許就是一個最簡單的雙向鏈表的實例吧。

雙向鏈表的插入操作

? ?說起插入操作相對于單鏈表而言要稍微復雜一點，我們要做的第一步就是找到要插入的位置，而后將帶插入的結點的后驅指向當前結點的后驅，將插入結點的前驅指向當前結點。將當前結點的后驅重新指向帶插入結點，當前結點的后驅結點的前驅指向待插入結點，是不是聽起來有點太繞了？沒關系！用圖來說明問題吧：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

代碼如下： //創建雙向鏈表節點 _DOUBLE_LINK_NODE? *CreateDoubleLink(int?data) { ????_DOUBLE_LINK_NODE? *head = (_DOUBLE_LINK_NODE? *)malloc(sizeof (_DOUBLE_LINK_NODE)); ????ASSERT(head != NULL); ????head->data = data; ????head->prev = NULL; ????head->next = NULL; ????return?head; } //雙向鏈表中插入數據 int?insert_data_into_double_link (_DOUBLE_LINK_NODE** ppDLinkNode,?int?data) { ????_DOUBLE_LINK_NODE* pNode; ????_DOUBLE_LINK_NODE* pIndex; ????if(NULL == ppDLinkNode) ????????return?0; ????if(NULL == *ppDLinkNode){ ????????pNode = CreateDoubleLink (data); ????????ASSERT(NULL != pNode); ????????*ppDLinkNode = pNode; ????????(*ppDLinkNode)->prev = (*ppDLinkNode)->next = NULL; ????????return?1; ????} ????if(NULL != find_data_in_double_link (*ppDLinkNode, data)) ????????return?FALSE; ????pNode = CreateDoubleLink(data); ????ASSERT(NULL != pNode); ????pIndex = *ppDLinkNode; ????while(NULL != pIndex->next) ????????pIndex = pIndex->next; ????pNode->prev = pIndex; ????pNode->next = pIndex->next; ????pIndex->next = pNode; ????return?1; }

? ?雙向鏈表的刪除操作，其實我們掌握了插入操作以后，對于別的刪除、查找操作就相對來說要容易的多了，那就直接上代碼了：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

//雙向鏈表中刪除數據 int?delete_data_from_double_link (_DOUBLE_LINK_NODE** ppDLinkNode,?int?data) { ????_DOUBLE_LINK_NODE* pNode; ????if(NULL == ppDLinkNode || NULL == *ppDLinkNode) ????????return?0; ????pNode = find_data_in_double_link (*ppDLinkNode, data); ????if(NULL == pNode) ????????return?0; ????if(pNode == *ppDLinkNode){ ????????if(NULL == (*ppDLinkNode)- >next){ ????????????*ppDLinkNode = NULL; ????????}else{ ????????????*ppDLinkNode = pNode->next; ????????????(*ppDLinkNode)- >prev = NULL; ????????} ????}else{ ????????if(pNode->next) ????????????pNode->next->prev = pNode->prev; ????????pNode->prev->next = pNode->next; ????} ????free(pNode); ????return?1; } //在雙向鏈表中查找數據 _DOUBLE_LINK_NODE* find_data_in_double_link (const?_DOUBLE_LINK_NODE* pDLinkNode,?int?data) { ????_DOUBLE_LINK_NODE* pNode = NULL; ????if(NULL == pDLinkNode) ????????return?NULL; ????pNode = (_DOUBLE_LINK_NODE*) pDLinkNode; ????while(NULL != pNode){ ????????if(data == pNode->data) ????????????return?pNode; ????????pNode = pNode ->next; ????} ??????????????????????????????????????? ????return?NULL; } //統計雙向鏈表中數據的個數 int?count_number_in_double_link(const _DOUBLE_LINK_NODE* pDLinkNode) { ????int?count = 0; ????_DOUBLE_LINK_NODE* pNode = (_DOUBLE_LINK_NODE*)pDLinkNode; ????while(NULL != pNode){ ????????count ++; ????????pNode = pNode->next; ????} ????return?count; } //打印雙向鏈表中數據 void?print_double_link_node(const _DOUBLE_LINK_NODE* pDLinkNode) { ????_DOUBLE_LINK_NODE* pNode = (_DOUBLE_LINK_NODE*)pDLinkNode; ????while(NULL != pNode){ ????????printf("%d\n", pNode->data); ????????pNode = pNode ->next; ????} }

? ?基本的操作也就這么多了，當然了，對于我們自己寫程序來說一定要記得寫測試程序，這個是非常非常重要的。

? ? ?本文轉自 驛落黃昏 51CTO博客，原文鏈接：http://blog.51cto.com/yiluohuanghun/1262417，如需轉載請自行聯系原作者

總結

以上是生活随笔為你收集整理的“chaos“的算法--之双向链表的全部內容，希望文章能夠幫你解決所遇到的問題。

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