【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
前面的博客我們介紹了單向鏈表。那麼我們今天介紹的雙向鏈表，顧名思義，就是數據本身具備了左邊和右邊的雙向指針。雙向鏈表相比較單向鏈表，主要有下面幾個特點：
（1）在數據結構中具有雙向指針
（2）插入數據的時候需要考慮前後的方向的操作
（3）同樣，刪除數據的是有也需要考慮前後方向的操作
那麼，一個非循環的雙向鏈表操作應該是怎麼樣的呢？我們可以自己嘗試一下：
（1）定義雙向鏈表的基本結構
typedef struct _DOUBLE_LINK_NODE
{
int data;
struct _DOUBLE_LINK_NODE* prev;
struct _DOUBLE_LINK_NODE* next;
}DOUBLE_LINK_NODE;
typedef struct _DOUBLE_LINK_NODE
{
int data;
struct _DOUBLE_LINK_NODE* prev;
struct _DOUBLE_LINK_NODE* next;
}DOUBLE_LINK_NODE; （2）創建雙向鏈表節點DOUBLE_LINK_NODE* create_double_link_node(int value)
{
DOUBLE_LINK_NODE* pDLinkNode = NULL;
pDLinkNode = (DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE));
assert(NULL != pDLinkNode);
memset(pDLinkNode, 0, sizeof(DOUBLE_LINK_NODE));
pDLinkNode->data = value;
return pDLinkNode;
}
DOUBLE_LINK_NODE* create_double_link_node(int value)
{
DOUBLE_LINK_NODE* pDLinkNode = NULL;
pDLinkNode = (DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE));
assert(NULL != pDLinkNode);
memset(pDLinkNode, 0, sizeof(DOUBLE_LINK_NODE));
pDLinkNode->data = value;
return pDLinkNode;
} （3）刪除雙向鏈表
void delete_all_double_link_node(DOUBLE_LINK_NODE** pDLinkNode)
{
DOUBLE_LINK_NODE* pNode;
if(NULL == *pDLinkNode)
return ;
pNode = *pDLinkNode;
*pDLinkNode = pNode->next;
free(pNode);
delete_all_double_link_node(pDLinkNode);
}
void delete_all_double_link_node(DOUBLE_LINK_NODE** pDLinkNode)
{
DOUBLE_LINK_NODE* pNode;
if(NULL == *pDLinkNode)
return ;
pNode = *pDLinkNode;
*pDLinkNode = pNode->next;
free(pNode);
delete_all_double_link_node(pDLinkNode);
}
（4）在雙向鏈表中查找數據
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;
}
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;
} （5）雙向鏈表中插入數據
STATUS insert_data_into_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)
{
DOUBLE_LINK_NODE* pNode;
DOUBLE_LINK_NODE* pIndex;
if(NULL == ppDLinkNode)
return FALSE;
if(NULL == *ppDLinkNode){
pNode = create_double_link_node(data);
assert(NULL != pNode);
*ppDLinkNode = pNode;
(*ppDLinkNode)->prev = (*ppDLinkNode)->next = NULL;
return TRUE;
}
if(NULL != find_data_in_double_link(*ppDLinkNode, data))
return FALSE;
pNode = create_double_link_node(data);
assert(NULL != pNode);
pIndex = *ppDLinkNode;
while(NULL != pIndex->next)
pIndex = pIndex->next;
pNode->prev = pIndex;
pNode->next = pIndex->next;
pIndex->next = pNode;
return TRUE;
}
STATUS insert_data_into_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)
{
DOUBLE_LINK_NODE* pNode;
DOUBLE_LINK_NODE* pIndex;
if(NULL == ppDLinkNode)
return FALSE;
if(NULL == *ppDLinkNode){
pNode = create_double_link_node(data);
assert(NULL != pNode);
*ppDLinkNode = pNode;
(*ppDLinkNode)->prev = (*ppDLinkNode)->next = NULL;
return TRUE;
}
if(NULL != find_data_in_double_link(*ppDLinkNode, data))
return FALSE;
pNode = create_double_link_node(data);
assert(NULL != pNode);
pIndex = *ppDLinkNode;
while(NULL != pIndex->next)
pIndex = pIndex->next;
pNode->prev = pIndex;
pNode->next = pIndex->next;
pIndex->next = pNode;
return TRUE;
} （6）雙向鏈表中刪除數據
STATUS delete_data_from_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)
{
DOUBLE_LINK_NODE* pNode;
if(NULL == ppDLinkNode || NULL == *ppDLinkNode)
return FALSE;
pNode = find_data_in_double_link(*ppDLinkNode, data);
if(NULL == pNode)
return FALSE;
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 TRUE;
}
STATUS delete_data_from_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)
{
DOUBLE_LINK_NODE* pNode;
if(NULL == ppDLinkNode || NULL == *ppDLinkNode)
return FALSE;
pNode = find_data_in_double_link(*ppDLinkNode, data);
if(NULL == pNode)
return FALSE;
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 TRUE;
} （7）統計雙向鏈表中數據的個數
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;
}
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;
} （8）打印雙向鏈表中數據
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;
}
}
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;
}
} 注意：
今天我們討論的雙向鏈表是非循環的，大家可以考慮一下如果改成循環雙向鏈表，應該怎麼寫？如果是有序的循環雙向鏈表，又該怎麼寫？
