从前慢现在也慢

这个屌丝很懒，什么也没留下！

热门标签

【C语言数据结构】双链表详解（带头双向循环链表）_c语言双链表

作者：从前慢现在也慢 | 2024-06-01 02:01:10

踩

c语言双链表

作者：热爱编程的小y
专栏：C语言数据结构
座右铭：能击败你的只能是明天的你

一、导言

根据链表的结构的不同，我们可以按三种方法对链表进行分类。

1.单向与双向

单向链表每个节点包含两个参数，一个是存放的数据，一个是指向下一个节点的指针。

双向链表每个节点包含三个参数，比单向链表多了一个指向上一个节点的指针。

相比于单向链表，双向链表可以更容易地实现中间节点的插入与删除，知道一个节点就可以之间找到它的前后节点，而单向链表则不容易找到前一个节点。

2.有头节点与无头节点

有的链表会带上一个哨兵位的头节点。

有的则没有。

那么带哨兵位头节点有什么好处呢？

哨兵节点,也是头结点,是一个 dummy node. 可以用来简化边界条件.

是一个附加的链表节点.该节点作为第一个节点,它的值域不存储任何东西.

只是为了操作的方便而引入的.

如果一个链表有哨兵节点的话,那么线性表的第一个元素应该是链表的第二个节点.

3.循环与非循环

循环链表的特点是，最后一个节点里的指针指向的是头节点，而不是NULL，因此整个链表形成了一个闭环。

非循环链表的最后一个节点里的指针指向NULL。

根据以上三种分类方式，可以把链表细分成八种形式。而我们今天要介绍的就是其中的带头双向循环链表。

二、结构

带头双向循环链表是所有链表当中结构最复杂的一种，一般用于单独存储数据。实际中使用的链表形式，都是带头双向循环链表。它虽然结构复杂，但得利于其结构带来的便利性，用代码实现起来反倒简单。

三、接口实现

（一）准备工作

1.创立文件

我们需要创立三个文件，分别是List.c，List.h，Test.c 。

List.h 内包含引用的头文件，函数的声明，结构体的声明。

List.c 内包含函数的定义，功能具体这里实现。

Test.c 负责各项功能的测试与具体运用。

2.函数与结构体的定义

我们把要存放的数据类型重命名，接着定义一个含有三个参数的结构体，分别用于存放数据，指向下一节点与指向上一节点。


typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

我们在进行插入操作以及建立头节点的时候都需要进行申请节点的操作，因此我们可以把它分装成一个函数。不管是进行插入还是删除操作，我们都需要传入哨兵位头节点，我们可以把哨兵位头节点的创立也分装成一个函数。然后剩下的的就是链表的通用功能：增删查改，pos位置的插入与删除以及链表的销毁。


//双链表申请一个新节点
ListNode* BuyListNode(LTDataType x);
 
// 创建返回链表的头结点
ListNode* ListCreate();
 
// 双向链表打印
void ListPrint(ListNode* pHead);
 
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
 
// 双向链表尾删
void ListPopBack(ListNode* pHead);
 
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
 
// 双向链表头删
void ListPopFront(ListNode* pHead);
 
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
 
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
 
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
 
// 双向链表销毁
void ListDestory(ListNode* pHead);

（二）具体实现

1.节点的申请

我们用malloc函数申请一块空间用于存放节点，并将节点内参数初始化为0。申请空间要考虑申请失败的情况。

建立哨兵位头节点时需要将申请来的节点与自己首尾相接，以满足双向循环的结构。

代码如下：


//双链表申请一个新节点
ListNode* BuyListNode(LTDataType x)
{
	ListNode* node = malloc(sizeof(ListNode));
	if (node == NULL)
	{
		perror("BuyListNode::malloc");
		return NULL;
	}
	node->data = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}
 
// 创建返回链表的头结点
ListNode* ListCreate()
{
	ListNode* head = BuyListNode(-1);
	head->next = head;
	head->prev = head;
}

2.头插与尾插

我们在进行尾插操作时，只需要将原尾节点的next指针指向新尾节点，新尾节点的prev指针指向原尾节点，next指向头节点，头节点的prev指向新尾节点。注意，必须是先改变原尾节点的next指针指向，再改变头节点的next指针指向，否则就不能直接找到原尾节点了。

在进行头插操作时，我们并不是将新节点插入到head前面，而是head后面，因为head是一个不含数据的哨兵位头节点，插入时同理先改变原头节点的prev指向，再改变head的next指向。

代码如下：


// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = BuyListNode(x);
	ListNode* tail = pHead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = pHead;
	pHead->prev = newnode;
	return;
}
 
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = BuyListNode(x);
	newnode->next = pHead->next;
	pHead->next->prev = newnode;
	pHead->next = newnode;
	newnode->prev = pHead;
	return;
}

3.头删与尾删

我们在进行尾删操作时，通过head的prev指针直接找到原尾节点，再通过原尾节点的prev指针直接找到新尾节点，将新尾节点的next指针指向head，再将head的prev指针指向新尾节点，注意，顺序不可倒换，与上述同理。完成新尾节点的链接之后，要记得将原尾节点进行内存释放。

在进行头删操作的时候，通过head哨兵位的next指针找到原头节点，通过原头节点的next指针找到新头节点，将新头节点的prev指针指向head，再将head的next指针指向新头节点，与上述同理，顺序不可调换。

代码如下：


// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	ListNode* tail = pHead->prev;
	if (tail == pHead)
		return;
	tail->prev->next = pHead;
	pHead->prev = tail->prev;
	free(tail);
	tail = NULL;
	return;
}
 
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	ListNode* tmp = pHead->next;
	if (tmp == pHead)
		return;
	tmp->next->prev = pHead;
	pHead->next = tmp->next;
	free(tmp);
	tmp = NULL;
}

4.指定位置的插入与删除

给定一个指定节点pos，在pos位置后面或者前面插入节点，删除pos位置的节点时，方法与头插尾插，头删尾删相同，这里就不赘述，直接上代码。


// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	pos->prev = newnode;
	newnode->next = pos;
	return;
}
 
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
	return;
}

5.查找与打印

我们在进行节点的查找时，只需要从哨兵位头节点开始向后遍历链表，直到回到哨兵位时结束遍历，将找到的节点返回，找不到就返回NULL。

打印链表时也是从哨兵位头节点开始向后遍历，遍历一个打印一个，直到回到哨兵位时结束

代码如下：


// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* cur = pHead;
	while (cur->data != x)
	{
		cur = cur->next;
		if (cur == pHead)
			return NULL;
	}
	return cur;
}
 
// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	printf("head<=>");
	while (cur != pHead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
	return;
}

6.链表的销毁

我们在进行链表销毁时，同样从哨兵位头节点开始向后遍历，遍历一个销毁一个，直至回到哨兵位头为之，但是要记得申请一个新节点来保存销毁节点的信息，以保证销毁之后可以继续遍历。

代码如下：


// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	free(pHead);
	return;
}

四、完整代码

在这里献上带头双向循环链表的完整代码：


List.h部分
#pragma once
// 带头+双向+循环链表增删查改实现
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
 
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
 
//双链表申请一个新节点
ListNode* BuyListNode(LTDataType x);
 
// 创建返回链表的头结点
ListNode* ListCreate();
 
// 双向链表打印
void ListPrint(ListNode* pHead);
 
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
 
// 双向链表尾删
void ListPopBack(ListNode* pHead);
 
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
 
// 双向链表头删
void ListPopFront(ListNode* pHead);
 
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
 
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
 
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
 
// 双向链表销毁
void ListDestory(ListNode* pHead);


List.c部分
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
 
//双链表申请一个新节点
ListNode* BuyListNode(LTDataType x)
{
	ListNode* node = malloc(sizeof(ListNode));
	if (node == NULL)
	{
		perror("BuyListNode::malloc");
		return NULL;
	}
	node->data = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}
 
// 创建返回链表的头结点
ListNode* ListCreate()
{
	ListNode* head = BuyListNode(-1);
	head->next = head;
	head->prev = head;
}
 
// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	printf("head<=>");
	while (cur != pHead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
	return;
}
 
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = BuyListNode(x);
	ListNode* tail = pHead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = pHead;
	pHead->prev = newnode;
	return;
}
 
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	ListNode* tail = pHead->prev;
	if (tail == pHead)
		return;
	tail->prev->next = pHead;
	pHead->prev = tail->prev;
	free(tail);
	tail = NULL;
	return;
}
 
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = BuyListNode(x);
	newnode->next = pHead->next;
	pHead->next->prev = newnode;
	pHead->next = newnode;
	newnode->prev = pHead;
	return;
}
 
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	ListNode* tmp = pHead->next;
	if (tmp == pHead)
		return;
	tmp->next->prev = pHead;
	pHead->next = tmp->next;
	free(tmp);
	tmp = NULL;
}
 
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* cur = pHead;
	while (cur->data != x)
	{
		cur = cur->next;
		if (cur == pHead)
			return NULL;
	}
	return cur;
}
 
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	pos->prev = newnode;
	newnode->next = pos;
	return;
}
 
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
	return;
}
 
// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	free(pHead);
	return;
}

如果觉得这篇文章有帮助的，欢迎点赞评论收藏，还可以关注一波博主，俺会坚持创作，持续生产好文滴！！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/655420