双链表的定义

背景：由于单链表的结点中只有一个指向其后继的指针，使得单链表只能一次从头结点依次顺序向后遍历。其访问前驱结点的时间复杂度为$O(n)$，访问后继结点的时间复杂度$O($)。

为了克服单链表的问题，我们引入了双链表——一个双链表结点中含有两个指针：prior指针：前驱指针，next：后继指针，二者分别指向前驱结点和后继结点。

双链表的结点类型

//双链表的结点类型
typedf struct DNode{     //定义双链表结构类型
	ElemType data;        //每个节点存放一个数据元素
	struct DNode *prior, *next;    //前驱和后继指针
}DNode,*DLinkList;

双链表的初始化

(带头结点)

typedf struct DNode{     //定义双链表结构类型
	ElemType data;        //每个节点存放一个数据元素
	struct DNode *prior, *next;    //前驱和后继指针
}DNode,*DLinkList;

//DLinkList 等价于 DNode *

// 初始化双链表
bool InitDLinklist(DLinkList &L){
	L =  (DNode *) malloc (sizeof(DNode));  //申请一个头结点
	if(L==NULL)//空表，暂时还没有任何节点,可以防止脏数据；内存不足，分配失败
		return false；
	L->prior=NULL;//头结点的前驱指针永远指向NULL
	L->next =NULL;//初始化时，头结点之后还没有结点
	return ture;
}

void testDLinkList (){
	//初始化一个双链表
	DLinkList L; 
	InitDLinkList(L);
	//....后续代码。。。。。
}

双链表在插入和删除操作的实现上，与单链表的插入，删除操作有着很大的不同。
原因："链"变化时不仅是对$\ast next$指针的修改，也要注意对$\ast prior$指针进行修改。关键在于修改的过程中不断链。
Note:由于双链表很容易找到其前驱结点，因此双链表的插入和删除操作的时间复杂度都是$O(1)$。

双链表的插入

思路代码

//函数功能：在p结点之后插入s结点
Bool InsertNextDnode(DNode *p,DNode *s){
	s->next =p->next;  //1——p结点的后继指针指向赋予s结点的后继指针
	p->next->prior=s;  //2-p结点的后继指针的前驱指针指向s
	s->prior=p;   //3-s结点的前向指针指向p 
	p->next=s;    //4-p结点的后继指针指向s
//1和2两步必须在4之前

效果过程图

思考：如果p结点是最后一个结点，那么p结点的后继指针就为NULL，导致上述代码存在问题，不符合健壮性。

为了更严谨一些，来看下面这段代码

严谨代码

//函数功能：在p结点之后插入s结点
Bool InsertNextDnode(DNode *p,DNode *s){
	if(p==NULL || s==NULL)//非法参数，没有插入的必要
		return false;
	s->next =p->next;  //p结点的后继指针指向赋予s结点的后继指针
	if(p->next !=NULL){   //如果p结点有后继结点，就考虑把p结点的后继指针指向s，否则不读下面的代码，本身s的后继指针同样也是指向NULL。
		p->next->prior=s;  //p结点的后继指针的前驱指针指向s
	}
	s->prior=p;   //s结点的前向指针指向p 
	p->next=s;    //p结点的后继指针指向s
}

双链表的删除

逻辑代码

//函数功能：删除p结点的后继结点q
Bool DeleteNextDnode(DNode *p,DNode *s){
	p->next =q->next;  //后继结点——q结点的后继指针指向赋予p结点的后继指针
	q->next->prior=p;  //q结点的后继结点的前驱指针指向p
	free(q);//释放结点空间
}

效果过程




思考：如果被删结点是尾结点怎么办？为了提高代码的健壮性，大家来看一下代码：

严谨代码

//函数功能：删除p结点的后继结点q
Bool DeleteNextDnode(DNode *p,DNode *s){
	if(p==NUll){  //若p是尾结点，那么它的后继指针指向为为NULL，没有删除的必要
		return false
	}
	DNode *q=p->next;  //先找到p的后继结点
	if(q==NULL){
		return false;   //q是尾结点， 说明p没有后继结点
	p->next =q->next;  //后继结点——q结点的后继指针指向赋予p结点的后继指针
	if(q->next!=NULL){   //q结点不是尾结点
		q->next->prior=p;  //q结点的后继结点的前驱指针指向p
	}
	free(q);//释放结点空间
}

双链表的销毁

利用双链表的删除函数

void DestoryList(DLinkList &L){
	//循环释放结点，删除结点
	while (L-next !=NULL){
		DeleteNextDnode(L);
	}
	free(L);  //释放头结点
	L=NULL； //头指针指向NULL

双链表的遍历

后向遍历

while（p!=NULL){
	p=p->next;
}
//例如：对结点p作相应处理，打印

前向遍历

while（p!=NULL){
	p=p->prior;
}
//例如：对结点p作相应处理

注意到：双链表不可以随机存取，所以按位查找和按值查找都只能用遍历的方式实现。
时间复杂度为：$O(n)$

总结