数据结构双向链表

双向链表较单向链表有更好的灵活性，具备前后指针，可以更方便的对链表进行操作，但程序设计也更复杂，需要同时考虑前后指针。这里同样对照单链表的基础操作，讨论链表的创建、尾端添加元素、指定位置插入元素、删除指定单个元素节点、删除指定元素所有节点、删除指定位置节点等基础操作。
1、双向链表的数据结构

typedef struct _Node
{
	int value;
	struct _Node *prev;
	struct _Node *next;
}Node;

2、创建一个双向非循环链表

void createDoubleList(Node **ppDoubleList, int val)
{
	Node *pDoubleList = NULL;
	pDoubleList = (Node *)malloc(sizeof(Node));
	assert(NULL != pDoubleList);

​	memset(pDoubleList, NULL, sizeof(Node));
​	pDoubleList->value = val;
​	 
​	*ppDoubleList = pDoubleList;
​	 
​	return;

}

3、链表尾端添加元素
异常情况：链表不存在

void addToTail(Node **ppDoubleList, int val)
{
	Node *pNew = (Node *)malloc(sizeof(Node));
	memset(pNew, NULL, sizeof(Node));
	pNew->value = val;

​	if (NULL == ppDoubleList)
​		return;
​	 
​	if (NULL == *ppDoubleList)
​	{
​		*ppDoubleList = pNew;
​		return;
​	}
​	else
​	{
​		Node *pNode = *ppDoubleList;
​	 
​		while (NULL != pNode->next)
​			pNode = pNode->next;
​	 
​		pNode->next = pNew;
​		pNew->prev = pNode;
​	 
​		return;
​	}

}

4、指定位置插入元素
异常情况:

1) 链表为空

2) 插入位置为0

3) 插入位置大于链表长度

void insertNode(Node **ppDoubleList, int pos, int val)
{
	if ((NULL == ppDoubleList) || (pos < 0))
		return;
	if (NULL == *ppDoubleList)        //链表为空，直接创建新链表  
		createDoubleList(ppDoubleList, val);

​	Node *pNode, *pNew;
​	pNode = *ppDoubleList;
​	 
​	pNew = (Node *)malloc(sizeof(Node));
​	memset(pNew, NULL, sizeof(Node));
​	pNew->value = val;
​	 
​	if (0 == pos)    //插入链表首位置
​	{
​		pNode->prev = pNew;
​		pNew->next = pNode;
​		*ppDoubleList = pNew;
​	 
​		return;
​	}
​	 
​	while (--pos)
​	{
​		pNode = pNode->next;
​		if (NULL == pNode)  //插入位置大于链表长度
​			return;
​	}
​	 
​	pNew->next = pNode->next;
​	pNode->next->prev = pNew;
​	pNode->next = pNew;
​	pNew->prev = pNode;
​	 
​	return;

}

5、删除单个指定元素节点
异常情况：

1) 链表为空

2) 待删除元素为头结点元素

3) 链表仅一个节点，恰好为指定元素节点

4) 待删除节点是尾节点
5) 元素不存在链表中

/*删除单个指定元素节点*/
void deleteValue(Node **ppDoubleList, int value)
{
	Node *pNode = *ppDoubleList;
	if ((NULL == ppDoubleList) || (NULL == *ppDoubleList))
		return;

​	/*删除元素在头节点*/
​	if (value == pNode->value)
​	{
​		*ppDoubleList = pNode->next;
​		if (*ppDoubleList)  //链表仅一个节点
​			(*ppDoubleList)->prev = NULL;
​	}
​	else
​	{
​		/*查找指定待删除元素节点*/
​		while (pNode->value != value)
​		{
​			pNode = pNode->next;
​			if (NULL == pNode)    //元素不存在
​				return;
​		}
​		if (pNode->next)    //待删除元素是非尾节点
​		{
​			pNode->prev->next = pNode->next;
​			pNode->next->prev = pNode->prev;
​		}
​		else
​		{     //待删除元素为尾节点
​			pNode->prev->next = pNode->next;
​		}
​	}
​	free(pNode);
​	pNode = NULL;
​	 
​	return;

}

6、删除所有指定元素

异常情况同删除节点
/*删除所有指定元素节点*/
void deleteAllValue(Node **ppDoubleList, int value)
{
	Node *pNode = *ppDoubleList;
	if ((NULL == ppDoubleList) || (NULL == *ppDoubleList))
		return;

​	/*删除元素在头节点*/
​	if (value == pNode->value)
​	{
​		*ppDoubleList = pNode->next;
​		if (*ppDoubleList)
​			(*ppDoubleList)->prev = NULL;
​	}
​	else
​	{
​		/*查找指定待删除元素节点*/
​		while (pNode->value != value)
​		{
​			pNode = pNode->next;
​			if (NULL == pNode)    //元素不存在
​				return;
​		}
​		if (pNode->next)    //待删除元素是非尾节点
​		{
​			pNode->prev->next = pNode->next;
​			pNode->next->prev = pNode->prev;
​		}
​		else
​		{     //待删除元素为尾节点
​			pNode->prev->next = pNode->next;
​		}
​	}
​	free(pNode);
​	pNode = NULL;
​	 
​	return deleteAllValue(ppDoubleList, value);

}

7、删除指定位置的节点

异常情况：

1) 链表不存在

2) 删除位置为头结点位置

3) 删除节点位置大于链表长度

4) 删除节点为尾节点

void deleteNode(Node **ppDoubleList, int pos)
{
	Node *pNode = *ppDoubleList;   //pNode为待删除节点
	if ((NULL == ppDoubleList) || (NULL == *ppDoubleList) || (pos < 0))
		return;

​	/*删除首节点情况*/
​	if (0 == pos)
​	{
​		*ppDoubleList = pNode->next;
​		(*ppDoubleList)->prev = NULL;
​	}
​	else
​	{   /*找到待删除节点*/
​		while (pos--)
​		{
​			pNode = pNode->next;
​			if (NULL == pNode)  //位置大于长度返回
​				return;
​		}
​		pNode->prev->next = pNode->next;
​		if (pNode->next)    //如果删除节点不是最后一个节点
​			pNode->next->prev = pNode->prev;
​	}
​	free(pNode);
​	pNode = NULL;
​	 
​	return;

}

至于打印链表以及统计链表节点个数和前面的单链表是一样的，这里就不赘述了