在单链表中，每个元素都附加了一个指针域，指向下一个元素的存储位置。在双向链表中，每个元素都附加了两个指针域，分别指向前驱节点和后继节点。

单链表只能向后操作，不能向前操作。为了向前、向后操作方便，可以给每个元素都附加两个指针域，一个存储前一个元素的地址，一个存储下一个元素的地址。这种链表被称为双向链表，如下图所示。

从上图中可以看出，双向链表的每个节点都包含三个域：数据域和两个指针域。两个指针域分别存储前后两个元素的地址，即指向前驱节点和后继节点。

双向链表的节点结构体定义如下图所示。

（1）插入。单链表只有一个指针域，是向后操作的，不可以向前处理，因此单链表如果要在第 i 个节点之前插入一个元素，则必须先找到第 i -1个节点。在第 i 个节点之前插入一个元素相当于把新节点放在第 i -1个节点之后。而双向链表不需要，因为有两个指针，所以可以向前、后两个方向操作，直接找到第 i 个节点，就可以把新节点插入第 i 个节点之前。注意：这里假设第 i 个节点是存在的，如果第 i 个节点不存在，而第 i -1个节点存在，则还是需要找到第 i -1个节点，将新节点插在第 i -1个节点之后，如下图所示。

其中：

① 指将节点 s 的地址赋值给 p 的前驱节点的next指针域，即 p 的前驱的next指针指向 s ；

② 指将 p 的前驱节点的地址赋值给节点 s 的prior指针域，即节点 s 的prior指针指向p的前驱节点；

③ 指将节点 p 的地址赋值给节点 s 的next指针域，即节点 s 的next指针指向节点 p ；

④ 指将节点 s 的地址赋值给节点 p 的prior指针域，即节点 p 的prior指针指向节点 s 。

因为 p 的前驱节点无标记，一旦修改了节点 p 的prior指针， p 的前驱节点就找不到了，因此最后修改这个指针。修改指针顺序的原则：先修改没有指针标记的那一端。

算法代码：

（2）删除。删除一个节点，实际上是把这个节点跳过去。在单链表中必须先找到第 i -1个节点，才能把第 i 个节点跳过去。双向链表则不必如此，直接找到第 i 个节点，然后修改指针即可，如下图所示。

“ p ->prior->next= p ->next”指将 p 的后继节点的地址赋值给 p 的前驱节点的next指针域。即 p 的前驱节点的next指针指向 p 的后继节点。注意：等号的右侧是节点的地址，等号的左侧是节点的指针域。

“ p ->next->prior= p ->prior”指将 p 的前驱节点的地址赋值给 p 的后继节点的prior指针域。即 p 的后继节点的prior指针指向 p 的前驱节点。此项修改的前提是 p 的后继节点是存在的，如果不存在，则不需要修改此项。

这样，就把节点 p 跳过去了。然后用delete p 释放被删除节点的空间。删除节点修改指针没有顺序，先修改哪个都可以。

算法代码： mBD/NQ9B/Dgor0eHqBQjc7IIt2ZPCeRQwC048qRJOpK9YsD7jBRFTXCBCUJ7/t7+