二、双链表

单链表的主要不足之处是：link字段仅仅指向后继结点，不能有效地找到前驱。为弥补了上述不足之处，引入了双链表。其思路是：为每个结点增加一个指向前驱的指针。双链表示意图如下图：

双链表及其结点类型的说明如下：
struct DblListNode {
        ELEM data;
        DblListNode *rlink;
        DblListNode *llink;
};
struct DoubleList {
        DblListNode * first，* last;
};
      双链表删除结点时，如果要删除指针变量p所指的结点，只需修改该结点前驱的rlink字段和该结点后继的llink字段，即
p->llink->rlink = p->rlink;
p->rlink->llink = p->llink;
    然后把变量p所指内容清空，再把p所指空间释放即可。
p->rlink = NULL;
p->llink = NULL;
delete p;
      双链表插入结点时，如果要在p所指结点后插入一个新结点，首先执行new q开辟结点空间。然后，让该新结点的rlink填入p所指的后继地址，新结点的llink填入p所指结点的后继的llink字段，即
new q;
q->rlink = p->rlink;
q->llink = p->rlink->llink;
    此外，要把新结点的地址填入原p所指结点的rlink字段，而且新结点后继的llink字段也应该回指新结点。
p->rlink = q;
q->rlink->llink = q;