双链表

1、双向链表（Double Linked List）

    双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。

注意：

    ①双链表由头指针head惟一确定的。

    ②带头结点的双链表的某些运算变得方便。

    ③将头结点和尾结点链接起来，为双（向）循环链表。

2、双向链表的结点结构和形式描述

①结点结构(见上图a)

②形式描述 

    typedef struct dlistnode{

         DataType data;

         struct dlistnode *prior,*next;

      }DListNode;

    typedef DListNode *DLinkList;

    DLinkList head;

3、双向链表的前插和删除本结点操作

    由于双链表的对称性，在双链表能能方便地完成各种插入、删除操作。

①双链表的前插操作

    void DInsertBefore(DListNode *p,DataType x)

      {//在带头结点的双链表中，将值为x的新结点插入*p之前，设p≠NULL

        DListNode *s=malloc(sizeof(DListNode));//①

        s->data=x;//②

        s->prior=p->prior;//③

        s->next=p;//④

        p->prior->next=s;//⑤

        p->prior=s;//⑥

       }

②双链表上删除结点*p自身的操作

    void DDeleteNode(DListNode *p)

      {//在带头结点的双链表中，删除结点*p，设*p为非终端结点

          p->prior->next=p->next;//①

          p->next->prior=p->prior;//②

          free(p);//③

      } 

注意：

    与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。

    上述两个算法的时间复杂度均为O(1)。