双向链表，我们曾经拿了一幅非常形象的图片来形容他，就像几个人手拉手围成一个圈一样。在我们代码中的呈现就是每个节点都有一个指向下一个节点的指针，同时也有一个指向上一个节点的指针。就因为新增了这个指向上一个节点指针的特性，它解决了单向循环链表的诸多问题，如下：

  1. 单链表的结点都只有一个指向下一个结点的指针
  2. 单链表的数据元素无法直接访问其前驱元素
  3. 逆序访问单链表中的元素是极其耗时的操作！（如图）

2015-05-28_214912 双向链表图形表示： 2015-05-28_215039

【实现代码】

因为插入和删除节点的步骤跟单向循环链表差不多，只是多了一个前驱指针，我们这里值给出代码，具体的插入和删除操作的示例图就不一一列举了。大家也可以从代码中看详细的注释来了解插入和删除节点时需要注意的事项。

#ifndef _DLINK_LIST_H
#define _DLINK_LIST_H

//自定义双向链表数据类型
typedef void DLinkList;
//自定义双向链表节点数据类型
typedef struct tag_dLinkListNode
{
struct tag_dLinkListNode *prev;
struct tag_dLinkListNode *next;
}DLinkListNode;

//创建链表
DLinkList* DLinkList_Create();

//销毁链表
void DLinkList_Destroy(DLinkList* list);

//清空链表
void DLinkList_Clear(DLinkList* list);

//获取链表长度
int DLinkList_Length(DLinkList* list);

//获取第pos个元素操作
DLinkListNode* DLinkList_Get(DLinkList* list, int pos);

//插入元素到位置pos
int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos);

//删除位置pos处的元素
DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);

//获取当前游标指向的数据元素
DLinkListNode* DLinkList_Current(DLinkList* list);

//将游标重置指向链表中的第一个数据元素
DLinkListNode* DLinkList_Reset(DLinkList* list);

//将游标移动指向到链表中的下一个数据元素
DLinkListNode* DLinkList_Next(DLinkList* list);

//将游标移动指向到链表中的上一个数据元素
DLinkListNode* DLinkList_Prev(DLinkList* list);

//直接指定删除链表中的某个数据元素
DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);

#endif //_DLINK_LIST_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include “DLinkList.h”

//定义管理双向链表的结构体
typedef struct _tag_dlinklist
{
DLinkListNode head;
DLinkListNode *slider;
int length;
}TDLinkList;

//创建链表
DLinkList* DLinkList_Create()
{
//定义结构体类型指针变量,并分配内存空间
TDLinkList* dlist = (TDLinkList*)malloc(sizeof(TDLinkList));
//如果分配内存成功,则初始化变量
if (dlist != NULL)
{
dlist->head.next = NULL;
dlist->slider = NULL;
dlist->length = 0;
return (DLinkList*)dlist;
}
//失败返回空
printf(“分配内存失败\n”);
return NULL;
}

//销毁链表
void DLinkList_Destroy(DLinkList* list)
{
//判断list是否为有效指针
if (list != NULL)
{
//释放内存空间
free(list);
}
}

//清空链表
void DLinkList_Clear(DLinkList* list)
{
//判断list是否为有效指针
if (list != NULL)
{
//定义结构体类型指针,并给其赋值
TDLinkList* dlist = (TDLinkList*)list;
//数据重置
dlist->length = 0;
dlist->head.next = NULL;
dlist->slider = NULL;
}
}

//获取链表长度
int DLinkList_Length(DLinkList* list)
{
//判断list是否为有效指针
if (list != NULL)
{
//定义结构体类型指针,并给其赋值
TDLinkList* dlist = (TDLinkList*)list;
return dlist->length;
}
printf(“DLinkList_Length error: list 指针无效\n”);
return -1;
}

//获取第pos个元素操作
DLinkListNode* DLinkList_Get(DLinkList* list, int pos)
{
//判断list是否为有效指针
if (list != NULL)
{
//定义结构体类型指针,并给其赋值
TDLinkList* dlist = (TDLinkList*)list;
//定义辅助指针变量, 并初始化,指向头节点
DLinkListNode* currNode = &dlist->head;
//循环查找pos位置元素
for (int i = 0; i <= pos; ++i)
{
currNode = currNode->next;
}
return currNode;
}

printf(“DLinkList_Get error: list 指针无效\n”);
return NULL;
}

//插入元素到位置pos
int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos)
{
//判断list是否为有效指针
if (list != NULL)
{
//定义结构体类型指针,并给其赋值
TDLinkList* dlist = (TDLinkList*)list;
//定义辅助指针变量, 并初始化,指向头节点
DLinkListNode* currNode = &dlist->head;
//定义辅助指针变量
DLinkListNode* posNode = NULL;
//循环查找pos-1位置元素
for (int i = 0; i < pos; ++i)
{
//判断是否有后继节点
if (currNode->next != NULL)
{
//指针后移
currNode = currNode->next;
}
else
{
//没有后继节点,结束循环
break;
}
}
//赋值,辅助指针变量指向pos位置节点
posNode = currNode->next;

//开始插入元素
//step1: 将新节点的next域指针指向pos位置节点的地址
node->next = posNode;
//step2: 将当前节点的next域指针指向新插入节点的地址
currNode->next = node;
//step3: 将pos位置的节点的prev域指针指向新插入节点的地址
//********** 特殊处理 **********
if (posNode != NULL)//当链表插入第一个元素需要特殊处理
{
posNode->prev = node;
}
//step4: 将新插入节点的地址指向当前节点的地址
node->prev = currNode;
//********** 特殊处理 **********
if (currNode == &dlist->head)//如果链表为空
{
//将第一个节点的前驱节点设为空
node->prev = NULL;
//游标指向第一个节点
dlist->slider = node;
}
//step4: 链表长度加1
dlist->length++;

return 0;
}

printf(“DLinkList_Insert error: list 指针无效\n”);
return -1;
}

//删除位置pos处的元素
DLinkListNode* DLinkList_Delete(DLinkList* list, int pos)
{
//判断list是否为有效指针
if (list != NULL && pos >= 0)
{
//定义结构体类型指针,并给其赋值
TDLinkList* dlist = (TDLinkList*)list;
//定义辅助指针变量, 并初始化,指向头节点
DLinkListNode* currNode = &dlist->head;
//定义辅助指针变量
DLinkListNode* delNode = NULL;
DLinkListNode* nextNode = NULL;
//循环查找pos-1位置元素
for (int i = 0; i < pos; ++i)
{
currNode = currNode->next;
}
//赋值
delNode = currNode->next;
nextNode = delNode->next;

//开始删除元素
//step1: 将当前节点的next域指针指向被删除节点的后继节点
currNode->next = nextNode;
//****** 需要特殊处理 ******
if (nextNode != NULL)
{
//step2: nextNode节点的prev域指针指向当前节点的地址
nextNode->prev = currNode;
//****** 需要特殊处理 ******
if (currNode == &dlist->head)//如果当前节点为头结点
{
//将nextNode节点指向空
nextNode->prev = NULL;
}
}
//step 3: 链表长度减1
dlist->length–;

//判断删除的元素是不是当前游标指向的位置
if (dlist->slider == delNode)
{
//如果是,游标后移
dlist->slider = nextNode;
}

return delNode;
}

printf(“DLinkList_Delete error: list指针 或 pos位置无效\n”);
return NULL;
}

//获取当前游标指向的数据元素
DLinkListNode* DLinkList_Current(DLinkList* list)
{
//判断list是否为有效指针
if (list != NULL)
{
//定义结构体类型指针,并给其赋值
TDLinkList* dlist = (TDLinkList*)list;
return dlist->slider;
}

printf(“DLinkList_Current error: list 指针无效\n”);
return NULL;
}

//将游标重置指向链表中的第一个数据元素
DLinkListNode* DLinkList_Reset(DLinkList* list)
{
//判断list是否为有效指针
if (list != NULL)
{
//定义结构体类型指针,并给其赋值
TDLinkList* dlist = (TDLinkList*)list;
dlist->slider = dlist->head.next;
return dlist->slider;
}

printf(“DLinkList_Reset error: list 指针无效\n”);
return NULL;
}

//将游标移动指向到链表中的下一个数据元素
DLinkListNode* DLinkList_Next(DLinkList* list)
{
//判断list是否为有效指针
if (list != NULL)
{
//定义结构体类型指针,并给其赋值
TDLinkList* dlist = (TDLinkList*)list;
//定义链表节点指针保存当前游标地址
DLinkListNode* currSlider = dlist->slider;
//游标后移
dlist->slider = dlist->slider->next;
return currSlider;
}

printf(“DLinkList_Next error: list 指针无效\n”);
return NULL;
}

//将游标移动指向到链表中的上一个数据元素
DLinkListNode* DLinkList_Prev(DLinkList* list)
{
//判断list是否为有效指针
if (list != NULL)
{
//定义结构体类型指针,并给其赋值
TDLinkList* dlist = (TDLinkList*)list;
//定义链表节点指针保存当前游标地址
DLinkListNode* currSlider = dlist->slider;
//游标前移
dlist->slider = dlist->slider->prev;
return currSlider;
}

printf(“DLinkList_Prev error: list 指针无效\n”);
return NULL;
}

//直接指定删除链表中的某个数据元素
DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node)
{
//判断list是否为有效指针
if (list != NULL)
{
int nPos = 0;
//定义结构体类型指针,并给其赋值
TDLinkList* dlist = (TDLinkList*)list;
//查找与node节点相等的节点
for (int i = 0; i < dlist->length; ++i)
{
if (node == DLinkList_Get(list, i))
{
//保存位置
nPos = i;
//跳出循环
break;
}
}
//删除指定nPos位置节点
DLinkListNode* delNode = DLinkList_Delete(list, nPos);
return delNode;
}

printf(“DLinkList_DeleteNode error: list or node 指针无效\n”);
return NULL;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include “DLinkList.h”

//定义数据结构体
typedef struct tag_value
{
//包含双向链表的一个节点
DLinkListNode head;
int value;
}Value;

//双向链表测试程序
void dLinkListTest()
{
int i;
//定义结构体数组
Value val[10];
//创建双向链表
DLinkList *dlist = DLinkList_Create();
//判断是否创建成功
if (dlist == NULL)
{
printf(“双向链表创建失败\n”);
return;
}
//初始化并向链表中插入数据
for (i = 0; i < sizeof(val) / sizeof(Value); ++i)
{
val[i].value = i + 10;
//向尾部插入元素
DLinkList_Insert(dlist, (DLinkListNode*)&val[i], i);
}
//遍历双向链表
printf(“遍历双向链表\n”);
for (int i = 0; i < DLinkList_Length(dlist); ++i)
{
//获取指定位置元素
Value* val = (Value*)DLinkList_Get(dlist, i);
printf(“%d\t”, val->value);
}
printf(“\n”);

//删除最后一个节点
DLinkList_Delete(dlist, DLinkList_Length(dlist) - 1);
//删除第一节点
DLinkList_Delete(dlist, 0);
//再次遍历链表
printf(“再次遍历双向链表\n”);
for (int i = 0; i < DLinkList_Length(dlist); ++i)
{
//获取指定位置元素
Value* val = (Value*)DLinkList_Get(dlist, i);
printf(“%d\t”, val->value);
}
printf(“\n”);

//重置游标
DLinkList_Reset(dlist);
//游标后移
DLinkList_Next(dlist);
//获取当前游标指向的节点
Value* pVal = (Value*)DLinkList_Current(dlist);
//打印当前节点的value值
printf(“DLinkList_Next — 打印当前节点的value值: value = %d\n”, pVal->value);
//删除游标指向的当前节点
DLinkList_DeleteNode(dlist, (DLinkListNode*)pVal);
//再次获取当前游标指向的节点
pVal = (Value*)DLinkList_Current(dlist);
//再次打印当前节点的value值
printf(“DLinklist_DeleteNode — 再次打印当前节点的value值: value = %d\n”, pVal->value);

//向前移动游标
DLinkList_Prev(dlist);
//第三次获取当前游标指向的节点
pVal = (Value*)DLinkList_Current(dlist);
//第三次打印当前节点的value值
printf(“DLinkList_Prev — 再次打印当前节点的value值: value = %d\n”, pVal->value);

//打印链表的长度
printf(“打印链表的长度, Length = %d\n”, DLinkList_Length(dlist));

//销毁双向链表
DLinkList_Destroy(dlist);
}

void main()
{
dLinkListTest();
system(“pause”);
}

双向链表增加了前驱的指针，在功能上完全是可以替代单向链表的，并且通过前驱指针我们可以更高效的遍历所有元素，正着、逆着随你处置。但代码的复杂度相对要比单向链表高出不止一个层级。