第1章第2节 线性表的链式表示（2）
最后更新于：2022-04-01 19:50:33
单链表中只有一个指向其后继结点的指针，使得单链表只能从前向后依次遍历，若要访问某个结点的前驱结点（或插入，删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为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);
}
~~~
';