【数据结构】– 单链表 vs 双向链表

🌈 个人主页：白子寰
🔥 分类专栏：python从入门到精通，魔法指针，进阶C++，C语言，C语言题集，C语言实现游戏👈 希望得到您的订阅和支持~
💡 坚持创作博文(平均质量分82+)，分享更多关于深度学习、C/C++，python领域的优质内容！（希望得到您的关注~） 

目录

 单链表和双向链表的比较

链表的打印

单链表

//链表的打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

双向链表 

//打印
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->dada);
		pcur = pcur->next;
	}
	printf("\n");
}

初始化

双向链表

//双向链表初始化
LTNode* LTInit()
{
	//哨兵位设置为-1
	LTNode* phead = SLTBuyNode(-1);
	return phead;
}

开辟空间，写入新数据

单链表

//开辟空间，写入新数据
SLTNode* SLTbuyNode(SLTDatatype x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}

	//先插入，后数据为空（后为空）
	newnode->data = x;
	newnode->next = NULL;

	return newnode;//返回数据
}

双向链表

//扩容，申请新节点
LTNode* SLTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//扩容
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//数据赋值
	newnode->dada = x;
	//指向自己
	newnode->next = newnode->prev = newnode;

	return newnode;
}

尾部插入数据

单链表

//尾插
void SLTPushBack(SLTNode** pphead, SLTDatatype x)
{
	//传的参数不为空
	assert(pphead);

	SLTNode*newnode = SLTbuyNode(x);
	//链表为空，新节点作为phead
	//*pphead是指向第一个节点的指针
	if (*pphead == NULL)//头节点为空
	{
		*pphead = newnode;
		return;
	}

	//链表不为空，找尾节点
	//ptail作为尾节点
	SLTNode* ptail = *pphead;
	//先方向，后数据
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	ptail->next = newnode;
}

双向链表

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = SLTBuyNode(x);
	
	newnode->next = phead;
	newnode->prev = phead->prev;

	phead->prev->next = newnode;
	phead->prev = newnode;
}

头部插入数据

单链表 

//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype x)
{
	//传参有效
	assert(pphead);
	//开辟空间，新数据进入
	SLTNode* newnode = SLTbuyNode(x);

	//先方向，后数据
	newnode->next = *pphead;
	*pphead = newnode;
}

双向链表

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = SLTBuyNode(x);

	newnode->next = phead->next;
	newnode->prev = phead;

	phead->next = newnode;
	phead->prev = newnode->prev->prev;
}

尾部删除数据

单链表

//尾删
void SLTPopBack(SLTNode** pphead)
{
	//保证传参数据有效
	assert(pphead);
	//链表不能为空
	assert(*pphead);

	//链表不为空
	//链表只有一个节点
	if ((*pphead)->next==NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}

	//有多个节点
	SLTNode* prev = NULL;
	SLTNode* ptail = *pphead;
	while (prev->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	prev = NULL;

	//销毁尾节点
	free(ptail);
	ptail = NULL;
}

双向链表

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);

	LTNode* del = phead->prev;

	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
}

头部删除数据

单链表

//头删
void SLTPopFront(SLTNode** pphead)
{
	//保证传参有效
	assert(pphead);
	//保证链表有效
	assert(*pphead);

	//让第二个节点成为新的头
	SLTNode* next = (*pphead)->next;
	//把旧的头节点释放掉
	free(*pphead);

	*pphead = next;//第一个节点 = 原来第二个节点
}

双向链表

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);

	LTNode* del = phead->next;

	phead->next = del->next;
	del->next->prev = phead;

	free(del);
	del = NULL;
}

查找

单链表 

SLTNode* SLTFind(SLTNode** pphead, SLTDatatype x)
{
	//保证传参有效
	assert(pphead);

	//遍历链表
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}

双向链表 

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* pcur = phead->next;

	while (pcur != phead)
	{
		if (pcur->dada == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

在指定位置之前插入数据 

单链表

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDatatype x)
{
	//保证传参有效
	assert(pphead);
	//保证指定位置数据有效
	assert(pos);
	//链表也不能为空
	assert(*pphead);

	//新节点，开辟新空间
	SLTNode* newnode = SLTbuyNode(x);
	//pos刚好是头节点
	if (newnode->next = *pphead)
	{
		//头插
		SLTPushFront(pphead, x);
		return;
	}

	//pos不是头节点的情况
	SLTNode* prev = *pphead;
	if (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = newnode;
	newnode->next = pos;
}

在指定位置之后插入数据

单链表

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDatatype x)
{
	//保证目标数据有效
	assert(pos);

	//创建新节点
	SLTNode* newnode = SLTbuyNode(x);

	//先方向，后数据
	newnode->next = pos->next;
	pos->next = newnode;
}

双向链表 

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = SLTBuyNode(x);
	newnode->prev = pos;
	newnode->next = pos->next;

	pos->next = newnode;
	pos->next->prev = newnode;
}

 删除指定位置数据

单链表

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	//保证传的参数有效
	assert(pphead);
	//保证单链表有效
	assert(*pphead);
	//保证目标数据有效
	assert(pos);

	//pos刚好是头节点，没有前驱节点
	if (*pphead == pos)
	{
		//头删
		SLTPopFront(pphead);
		return;
	}

	//pos不是头节点
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}

	//释放
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

双向链表

//删除pos位置的数据
void LTErase(LTNode* pos)
{
	assert(pos);

	LTNode* del = pos;
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(del);
	del = NULL;
}

删除指定位置后的数据

单链表

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	//保证目标数据有效
	assert(pos);
	//pos->next数据有效
	assert(pos->next);

	SLTNode* del = pos->next;
	pos->next = pos->next->next;

	//释放
	free(del);
	del = NULL;
}

销毁链表

单链表

//销毁链表
void SListDesTroy(SLTNode** pphead)
{
	//保证传的参数有效
	assert(pphead);
	//保证链表有效
	assert(*pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

双向链表

//销毁
void LTDesTroy(LTNode* phead)
{
	//哨兵位不能为空
	assert(phead);

	LTNode* pcur = phead->next;
	while(pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

***********************************************************分割线*****************************************************************************
完结！！！
感谢浏览和阅读。
等等等等一下，分享最近喜欢的一句话:

“成为正确答案的第一步，相信自己会是正确答案”。

我是白子寰，如果你喜欢我的作品，不妨你留个点赞+关注让我知道你曾来过。
你的点赞和关注是我持续写作的动力！！！ 
好了划走吧。