本文共 1666 字，大约阅读时间需要 5 分钟。

一、双链表初始化、插入、删除、遍历等操作的分析

1. 单链表 VS 双链表

2. 双链表的初始化（带头结点）

• DLinklist：强调是一个链表。
• DNode *：强调是一个结点。
  

typedef struct DNode{
   	ElemType data;	struct DNode *prior,*next;}DNode, *DLinklist;//初始化双链表bool InitDLinkList(DLinklist &L){
   	L = (DNode *)malloc(sizeof(DNode));//分配一个头结点	if(L == NULL)		//内存不足，分配失败		return false;	L -> prior = NULL;	//头结点的prior永远指向NULL	L -> next = NULL;	//头结点之后暂时还没有结点	return true;}//判断双链表是否为空（带头结点）bool Empty(DLinklist L){
   	if(L -> next == NULL)		return true;	else		return false;}void testDLinkList(){
   	//初始化双链表	DLinklist L;	InitDLinkList(L);	//后续代码....}

3. 双链表的插入

//在p结点之后插入s结点bool InsertNextDNode(DNode *p, DNode *s){
   	if(p==NULL || s==NULL)		//非法参数		return false;	s -> next = p -> next;	if(p->next != NULL)			//如果p结点有后继节点		p -> next -> prior = s;	s -> prior = p;	p -> next = s;	return true;}![在这里插入图片描述](https://img-blog.csdnimg.cn/20210426210730958.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDk2Njcw,size_16,color_FFFFFF,t_70)

4. 双链表的删除

//删除p结点的后继节点bool DeleteNextDNode(DNode *p){
   	if(p == NULL)	return false;	DNode *q = p -> next;	//找到p的后继节点q	if(q == NULL) 	return false;	//p没有后继	p -> next = q -> next;	if(q -> next != NULL)	//q结点不是最后一个结点		q -> next -> prior = p;	free(q);				//释放结点空间	return true;}

void DestoryList(DLinklist &L){
   	//循环释放各个数据结点	while(L -> next != NULL)		DeleteNextDNode(L);	free(L);	//释放头结点	L = NULL;	//头指针指向NULL}

5. 双链表的遍历

• 后向遍历

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

• 前向遍历

while (p!=NULL){
   	//对结点p做相应处理	p = p->prior;}

• 前向遍历（跳过头结点）

while (p-> prior != NULL){
   	//对结点p做相应处理	p = p->prior;}

• 双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。
• 时间复杂度 O(n)