【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：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;