聲明：版權所有，歡迎轉載。 聯系信箱：[email protected]】
自之前寫的兩篇關於“數據結構與算法”的博文發表以後，就有兩個博友發私信給我探討我的這個分類，有博友說數據結構怎麼能和算法在一起呢？其實吧，我倒感覺數據結構跟算法的關系就好比好基友是一輩子的關系。他們患難見真情、他們生死不相棄……事實上，數據結構和算法也有類似的關系。只談數據結構，我們可以在很短的時間內就把幾種重要的數據結構介紹完。不過聽完後，你可能沒啥感覺，不知道這些數據結構有啥用處。但如果我們把相應的算法結合起來講一講，演示一下，你就會發現，甚至開始感慨：原來解決計算機問題是如此的美妙！
這篇文章我主要聊一下雙向鏈表。
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點。雙向鏈表是指在前驅和後繼方向都能游歷(遍歷)的線性鏈表。雙向鏈表每個結點結構：
雙向鏈表通常采用帶表頭結點的循環鏈表形式。
其通常的數據結構如下：
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
有很多人不解，為何要有雙向鏈表的存在呢？下面我們可以再看一幅圖：
這貨我們叫它火車，我記得我第一次做火車的時候遇到過一個現象，就是火車正在往前走，到達一個站後，又往後走了一站，但是當時讓我吃驚的是為什麼火車並沒有掉頭就能往回走，在後來我才明白原來是火車是兩個頭都可以連接火車頭的，這也許就是一個最簡單的雙向鏈表的實例吧。
雙向鏈表的插入操作
說起插入操作相對於單鏈表而言要稍微復雜一點，我們要做的第一步就是找到要插入的位置，而後將帶插入的結點的後驅指向當前結點的後驅，將插入結點的前驅指向當前結點。將當前結點的後驅重新指向帶插入結點，當前結點的後驅結點的前驅指向待插入結點，是不是聽起來有點太繞了？沒關系！用圖來說明問題吧：
代碼如下：
//創建雙向鏈表節點
_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;
}雙向鏈表的刪除操作，其實我們掌握了插入操作以後，對於別的刪除、查找操作就相對來說要容易的多了，那就直接上代碼了：
//雙向鏈表中刪除數據
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;
}
}基本的操作也就這麼多了，當然了，對於我們自己寫程序來說一定要記得寫測試程序，這個是非常非常重要的。
本文出自 “驿落黃昏” 博客，請務必保留此出處http://yiluohuanghun.blog.51cto.com/3407300/1262417
