脚踏实地《数据结构第二章》第四节:双链表

一: 双链表的初始化(带头结点)

1.1 初始化实现代码

typedef struct DNode{
	ElemType data;
	struct DNode *prior,*next;//prior:前驱结点
}DNode,*DLinkList;
//初始化双链表
bool InitDLinkList(DLinkList){
	L = (DNode *)malloc(sizeof(DNode));//分配一个头结点
	if(L==NULL)//内存不足,分配失败
		return false;
	L->prior = NULL;//头结点的prior永远指向NULL
	L->next = NULL;//头结点之后暂时还没有节点
	return true;
}
void testDLinkList(){
	//初始化双链表
	DLinklist L;
	InitDLinkList(L);
	//后续代码。。。
}

1.2 判断双链表是否为空

//判断双链表是否为空(带头结点)
bool Empty(DLinklist L){
	if(L->next == NULL)
		return true;
	else
		return false;
}

二:双链表的插入

2.1 实现代码

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
	if(p==NULL || s==NULL)//非法参数
		return false;
	s->next = p->next;//将结点*s插入到结点*p之后
	if(p->next != NULL) //如果p结点有后继结点
		p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

2.2 插入的不是最后一个结点的执行流程

执行过程:如果插入的结点不是双链表的最后一个结点的话

  1. 插入的链表如下:
    脚踏实地《数据结构第二章》第四节:双链表

  2. s->next = p->next;
    脚踏实地《数据结构第二章》第四节:双链表

  3. p->next->prior = s;
    脚踏实地《数据结构第二章》第四节:双链表

  4. s->prior = p;
    脚踏实地《数据结构第二章》第四节:双链表

  5. p->next = s;
    脚踏实地《数据结构第二章》第四节:双链表

2.3 插入的是最后一个结点的执行流程

执行过程2:如果插入的结点是双链表的最后一个结点的话

  1. s->next = p->next;
    脚踏实地《数据结构第二章》第四节:双链表

  2. 进行判断,得出没有后继结点,所有执行s->prior = p;
    脚踏实地《数据结构第二章》第四节:双链表

  3. p->next = s;
    脚踏实地《数据结构第二章》第四节:双链表

三:双链表的删除

3.1 删除结点的后继结点实现代码

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

3.2 删除的不是最后一个结点的执行流程

执行流程:
脚踏实地《数据结构第二章》第四节:双链表

  1. p->next = q->next;
    脚踏实地《数据结构第二章》第四节:双链表

  2. q->next->prior = p;
    脚踏实地《数据结构第二章》第四节:双链表

  3. free(q);
    脚踏实地《数据结构第二章》第四节:双链表

3.3 删除的是最后一个结点的执行流程

执行流程:
脚踏实地《数据结构第二章》第四节:双链表

  1. p->next = q->next;
    脚踏实地《数据结构第二章》第四节:双链表

  2. 结果判断,为null所以不执行q->next->prior = p;

  3. free(q);
    脚踏实地《数据结构第二章》第四节:双链表

3.4 销毁一个双链表实现代码

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

四:双链表的遍历

4.1 后向遍历

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

4.2 前向遍历

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

4.3 前向遍历(跳过头结点)

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

4.4 时间复杂度

双链表不可随机存取,按位查找、按值查找操作都只能用遍历的方式实现。

时间复杂度O(n)

五:知识回顾与重要考点

脚踏实地《数据结构第二章》第四节:双链表

上一篇:数据结构双链表C语言


下一篇:python数据结构之双向链表