单链表中只有一个指向其后继结点的指针，使得单链表只能从前向后依次遍历，若要访问某个结点的前驱结点（或插入，删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为O(1)，而访问前驱结点时，其事件复杂度为O(n)。
为了克服单链表的上述缺点，引入了双链表。

一.双链表的定义

在双链表中引入了两个指针，分别为指向前驱结点的指针prior和指向后继结点的指针next。如下图所示：

对于双链表结点的描述如下：

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *DLinkList;

双链表仅仅在单链表的基础上增加了一个指向前驱的prior指针，因此，在双链表执行按值查找和按位查找时的操作与单链表无异。但双链表在插入和删除操作的实现上与单链表相比有着较大的不同，因为在对“链”进行修改时不仅仅需要修改next指针域，此时还需要照顾到prior指针域，此时在操作时就必需保证在修改过程中不会断链。此外双链表可以很方便的找到其前驱结点，因此插入，删除结点时的时间复杂度仅为O(1)。

二.双链表基本操作的实现

2.1建立双链表

2.1.1头插法建立双链表

该方法中，首先建立一个具有头结点的空双链表，然后每生成一个读取到数据的新节点，就将其放置到头结点之后。如下图所示：

算法描述如下：

DLinkList CreatList(DNode *head)
{
    DNode *s;
    ElemType x;
    scanf("%d",&x);
    while(x!=999){
        s=(DNode*)malloc(sizeof(DNode));
        s->data=x;

        s->next=head->next;
        if(head->next){
            head->next->prior=s;
        }
        s->prior=head;
        head->next=s;

        scanf("%d",&x);
    }
    return head;
}

2.1.2尾插法建立双链表

该方法中同样首先建立一个具有头结点的空双链表，然后每生成一个读取到数据的新节点，就将它插入到表尾；为了达到这样的目的，必须增加一个尾指针r，使其始终指向当前链表的尾结点。如下图所示：

算法描述如下：

DLinkList CreatList(DNode *head)
{
    DNode *s;
    DNode *r=head;

    ElemType x;
    scanf("%d",&x);
    while(x!=999){
        s=(DNode*)malloc(sizeof(DNode));
        s->next=NULL;
        s->data=x;

        r->next=s;
        s->prior=r;
        r=s;

        scanf("%d",&x);
    }

    r->next=NULL;
    return head;
}

2.2双链表的插入操作

2.2.1插入后继结点

在双链表p所指的结点之后插入结点*s，其指针的变化过程一定不能乱，否则会断链，具体过程如下图所示：

void InsertDNode(DNode* p, ElemType x)
{
    DNode *s;
    s=(DNode*)malloc(sizeof(DNode));
    s->data=x;

    s->next=p->next;
    p->next->prior=s;
    s->prior=p;
    p->next=s;
}

2.2.2插入前驱结点

在双链表p所指的结点之前插入结点*s，其指针的变化过程一定不能乱，否则会断链，具体过程如下图所示：

算法描述如下所示：

void InsertDNode(DNode* p, ElemType x)
{
    DNode *s;
    s=(DNode*)malloc(sizeof(DNode));
    s->data=x;

    s->next=p;
    p->prior->next=s;
    s->prior=p->prior;
    p->prior=s;
}

2.3双链表的删除操作

删除双链表中结点p的后继结点q，其指针的变化过程如下图所示：

算法描述如下：

void DelList(DNode *p)
{
    DNode *q=p->next;
    p->next=q->next;
    q->next->prior=p;
    free(q);
}