单链表中只有一个指向其后继结点的指针，使得单链表只能从前向后依次遍历，若要访问某个结点的前驱结点（或插入，删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为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); } ~~~