双链表：双链表的优点、插入节点、删除节点

单链表结点中只有一个指向其后继的指针，这使得单链表只能从头结点依次顺序地向后遍历。若要访问某个结点的前驱结点（插入、删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)。

为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点，如图2-8所示。 

图2-8  双链表示意图

双链表中结点类型的描述如下：

typedef struct DNode {  //定义双链表结点类型
    ElemType data;  //数据域
    struct DNode *prior, *next;  //前驱和后继指针
}DNode, *DLinklist;

双链表仅仅是在单链表的结点中增加了一个指向其前驱的prior指针，因此，在双链表中执行按值查找和按位查找的操作和单链表相同。但双链表在插入和删除操作的实现上，和单链表有着较大的不同。这是因为“链”变化时也需要对prior指针做出修改，其关键在于保证在修改的过程中不断链。此外，双链表可以很方便地找到其前驱结点，因此，插入、删除结点算法的时间复杂度仅为O(1)。

双链表的插入操作

在双链表中p所指的结点之后插入结点*s，其指针的变化过程如图2-9所示。

插入操作的代码片段如下：

s->next=p->next;  // 语句①，将结点*s插入到结点*p之后
p->next->prior=s;  // 语句②
s->prior=p;  // 语句③
p->next=s;  // 语句④

图2-9  双链表插入结点过程

上述代码的语句顺序不是唯一的，但也不是任意的，①②两步必须在④步之前，否则*p 的后继结点的指针就丢掉了，导致插入失败。为了加深理解，读者可以在纸上画出示意图。若问题改成要求在结点*p之前插入结点*s，请读者思考具体的操作步骤。

双链表的删除操作

删除双链表中结点*p的后继结点*q，其指针的变化过程如图2-10所示。 

图2-10  双链表删除结点过程

删除操作的代码片段如下：

p->next=q->next;  // 图2-10中步骤①①
q->next->prior=p;  //图 2-10 中步骤②
free (q) ; //释放结点空间

若问题改成要求删除结点*q的前驱结点*p，请读者思考具体的操作步骤。

建立双链表的操作中，也可以采用如同单链表的头插法和尾插法，但是在操作上需要注意指针的变化和单链表有所不同。