数据结构——链表（最全的一集）

1、动态大小：链表的大小可以在运行时动态变化，初始化定不出链表的最终大小
2、节点：每个节点存储数据，并包含一个或多个指针指向列表中的其他节点。
3、无需连续内存：由于节点通过指针连接，它们不需要在内存中连续存放，这使得内存使用更加灵活。
4、增删操作：在链表中插入或删除节点通常比数组更快，因为这些操作只需要作用在插入位置的前驱和后继，而不是整体移动。

二、单向链表

1、单向链表的构成

链表由一个个节点构成，每个节点一般采用结构体的形式定义：

typedef int element_t;
typedef struct link_node
{
	element_t data;
	struct link_node* next;
} Lnode;

如上文，单向链表的节点一般有两个域构成：

1、数据域：存储该节点的信息

2、指针域：存放下一个节点的地址

2、链表与数组的区别

在上一次顺序表的讲解当中，我们谈及了顺序表和数组的区别，那么我们现在谈谈链表和数组的区别：

链表是通过节点的指针把离散的数据链接成一个表，并通过对节点的插入和删除操作从而实现数据的存取，而数组是通过开辟一段连续的内存空间来存储数据，这是数组和链表最大的区别。

3、两种单向链表的创建

我们在创建一个链表时，我们有两种链表操作可选

1、带头指针的链表

2、带头结点的链表

在对比其上两种操作，我想先插入一个小知识点，即我们在添加链表时，我们通常进行这样的操作：

1、创建新节点

2、先处理新结点的next再处理老结点的next

node->next = p->next
p->next = node;

这时候我们再想，如果我们用第一种带头指针的节点的话，那么我们对链表进行头插法是不是就需要进行if特判，因为对于头插且链表还没有元素时，我们进行node->next = p->next时（p此时就是头指针）p为空，我们对一个空指针访问就会发生段错误，那么此时就会出现不一致的情况，即需要用if判断，这的确比带头结点的链表处理起来要麻烦。

那么我们开始定义链表节点的结构体

/* 链式表 数据结构定义 先定义节点 */
typedef int element_t;
typedef struct link_node
{
	element_t data;
	struct link_node* next;
} Lnode;

/* 带头结点的链表 */
typedef struct
{
	Lnode head;
	int num;
} LinkTable;

/* 带头指针的链表 */
typedef struct
{
	Lnode* ptr_head;
	int num;
} LinkList;

由易到难，我们首先会讲带头结点的链表的一系列实现

4、带头结点的单向链表的接口

注意，注意，注意，在此处我想提醒各位链表操作的核心永远是node->next，此处的动用一定要慎重，因为单向链表中node = node->next的操作是不可逆的，且我们通常查找还是插入动用的都是node->next。

/* 带头节点的单向链表 接口 */
void insertHeadTable(LinkTable *table, element_t v);				// 头插
void insertRearTable(LinkTable* table, element_t v);				// 尾插
void insertPosTable(LinkTable* table, int pos, element_t v);		// 在指定pos位置插入

void deleteValueTable(LinkTable* table, element_t v);				//删除指定值
void deleteAllLinkTable(LinkTable* table);							//删除所有数据节点
void showLinkTable(const LinkTable* table);							//显示

4.1链式表的通用接口

考虑到不同的值的插入、删除、显示都是同一套操作，我们此处继续采用static定义三个专用接口

/* 链式表的通用接口 */
static int insertLnode(Lnode* p, element_t v)
{
	Lnode* node = malloc(sizeof(Lnode));
	if (node == NULL)
	{
		return 0;
	}
	node->data = v;
	node->next = p->next;
	p->next = node;
	return 1;
}

static void showLnode(const Lnode *start)
{
	while (start)
	{
		printf("%d ", start->data);
		start = start->next;
	}
	printf("\n");
}

static void deleteLnode(Lnode* p)
{
	Lnode* tmp = p->next;
	p->next = tmp->next;
	free(tmp);
}

4.2头插

void insertHeadTable(LinkTable* table, element_t v)
{
	Lnode* p = &table->head;
	if (insertLnode(p, v))
	{
		++table->num;
	}
}

4.3任意位置插入

void insertPosTable(LinkTable* table, int pos, element_t v)
{
	if (pos < 0||pos > table->num)
	{
		return;
	}
	Lnode* p = &table->head;
	int i = 0;				//找到pos-1的位置
	while (i < pos && p != NULL)
	{
		p = p->next;
		++i;
	}
	if (p && insertLnode(p, v))
	{
		++table->num;
	}
}

4.4尾插

void insertRearTable(LinkTable* table, element_t v)
{
	Lnode* p = &table->head;
	while (p->next)
	{
		p = p->next;
	}
	if (insertLnode(p, v))
	{
		++table->num;
	}
}

4.5删除指定节点

void deleteValueTable(LinkTable* table, element_t v)
{
	Lnode* p = &table->head;		//把头结点的地址，假设作为前置节点p
	// 站在p，往后看他下一个节点的data是否=v
	while (p && p->next)
	{
		if (p->next->data == v)
		{
			break;
		}
		p = p->next;
	}

	//找到v值前面的的节点首地址
	if (p && p->next)
	{
		deleteLnode(p);
		--table->num;
	} 
}

4.6删除所有节点

void deleteAllLinkTable(LinkTable* table)
{
	//以头结点为固定点，相当于删除节点的前置节点，一直删除后面的节点，直到头结点后面为空
	Lnode* p = &table->head;
	while (p->next)
	{
		deleteLnode(p);
		--table->num;
	}
	printf("table->num = %d", table->num);
}

4.7展现节点内数据

void showLinkTable(const LinkTable* table)
{
	printf("table[%d] : ", table->num);
	Lnode* start = table->head.next;
	showLnode(start);
}

5、带头指针的单向链表的接口

那么带头结点的单向链表就到这里，接下来我们进入带头指针的链表操作

老样子，先上接口

/* 带头指针的链表 接口 */
void insertHeadList(LinkList *List, element_t v);					// 头插
void insertRearList(LinkList *List, element_t v);					// 尾插
void insertPosList(LinkList* List, int pos, element_t v);			// 在指定pos位置插入

void deleteValueList(LinkList* List, element_t v);					// 删除指定值
void deleteAllLinkList(LinkList* List);
void showLinkList(const LinkList* List);							// 显示

4.1头插

此处我们有两种操作，第一种也就是在代码块被注释掉的这种就是上文所讲的if判断来操作，但是我在此处更提倡第二种，也就是先转换为带头结点的链表，再对链表进行操作，我们接下来的剩余操作也将围绕第二种进行

void insertHeadList(LinkList* List, element_t v)
{
	//Lnode* node = malloc(10);
	//if (List->ptr_head == NULL)
	//{
	//	List->ptr_head = node;
	//}
	//else
	//{
	//	node->next = List->ptr_head;
	//	List->ptr_head = node;
	//}
	Lnode head;
	head.next = List->ptr_head;

	Lnode* p = &head;
	if (insertLnode(p, v))
	{
		List->ptr_head = head.next;	//更新指针
		++List->num;
	}
}

4.2任意位置插入

void insertPosList(LinkList* List, int pos, element_t v)
{
	if (pos < 0 || pos > List->num)
	{
		return;
	}
	Lnode head;
	head.next = List->ptr_head;

	Lnode* p = &head;
	int i = 0;				//找到pos-1的位置
	while (i < pos && p != NULL)
	{
		p = p->next;
		++i;
	}

	if (p && insertLnode(p, v))
	{
		++List->num;
	}
}

4.3尾插

void insertRearList(LinkList* List, element_t v)
{
	Lnode head;
	head.next = List->ptr_head;

	Lnode* p = &head;
	while (p->next)					//遍历到最后一个节点
	{
		p = p->next;
	}
	if (insertLnode(p, v))
	{
		List->ptr_head = head.next;
		++List->num;
	}
}

4.4删除指定节点

void deleteValueList(LinkList* List, element_t v)
{
	Lnode head;
	head.next = List->ptr_head;

	Lnode* p = &head;		//把头结点的地址，假设作为前置节点p
	// 站在p，往后看他下一个节点的data是否=v
	while (p && p->next)
	{
		if (p->next->data == v)
		{
			break;
		}
		p = p->next;
	}

	//找到v值前面的的节点首地址
	if (p && p->next)
	{
		deleteLnode(p);
		List->ptr_head = head.next;
		--List->num;
	}
}

4.5删除所有节点

void deleteAllLinkList(LinkList* List)
{
	Lnode head;
	head.next = List->ptr_head;

	Lnode* p = &head;
	while (p->next)
	{
		deleteLnode(p);
		--List->num;
	}
	printf("List->num = %d", List->num);
	List->ptr_head = NULL;
}

4.6展示节点内数据

void showLinkList(const LinkList* List)
{
	printf("List[%d] : ", List->num);
	Lnode* start = List->ptr_head;
	showLnode(start);
}

那么我们的头指针的链表也在此完结。

6.66、单向链表的小彩蛋

那么这一时刻又有人要问了，说y哥y哥，你的两种链表形式怎么都与leetcode里面的不一样，那么好，我告诉你：

我们都知道leetcode中，他只是给了首元节点，而没有头节点和头指针这种类型的链表。那么我们这个时候又该如何操作呢，此处只给出了插入的操作，其他操作因篇幅有限且lc也有，暂不提及。

Lnode* insertLink(Lnode *head, element_t v)
{
	Lnode dummy;
	dummy.next = head;

	Lnode* p = &dummy;
	if (insertLnode(p, v))
	{
		return dummy.next;
	}
	return NULL;
}

可以看到我们依旧为了方便将其转化为带头结点的链表。

7、总结

故遇到链表时，我们就往带头结点的链表上靠，当头结点出来以后，之后的所有操作都会好想很多。

三、单向循环链表

1、循环链表的图示

那么问题来了，下方的链表是循环链表吗，聪明的小伙伴已经发现了我的图中根本没标循环链表，

那就对了，因为这确实不是循环链表，这只是能提高尾插效率的一种双指针链表。

那么这种才是真正的循环链表，不过这也是其中的一种

为了方便，我们的代码实现将会采用下面这一种循环链表

2、循环链表的节点创建

typedef int element_t;

typedef struct Linknode
{
	element_t data;
	struct Linknode* next;
}Lnode;

typedef struct
{
	Lnode head;
	int num;
	Lnode* rear;
}LinkLoop;

3、循环链表的接口

// 静态初始化表头
void initLinkLoop(LinkLoop* link_loop);
// 插入，头插尾插
void insertLinkLoopHeader(LinkLoop* link_loop, element_t v);
void insertLinkLoopRear(LinkLoop* link_loop, element_t v);

// 删除
int deleteLinkLoop(LinkLoop *link_loop, element_t v);
void deleteAllLinkLoop(LinkLoop* link_loop);

// 遍历
void showLinkLoop(const LinkLoop *link_loop);

3.1循环链表的通用接口

同样，考虑到插入和删除的统一性，我们创建通用接口来提高效率

static void insertLinkLoop(LinkLoop* link_loop, Lnode* p, element_t v)
{
	Lnode* node = (Lnode*)malloc(sizeof(Lnode));
	if (node == NULL)
	{
		return;
	}
	node->data = v;
	
	node->next = p->next;
	p->next = node;
	if (link_loop->rear == p)//判断是否是第一个元素插入
	{
		link_loop->rear = node;
	}
	++link_loop->num;
}

static void delLinkLoop(LinkLoop* link_loop, Lnode* p)
{
	if (!p || p->next == &link_loop->head)
	{
		return;
	}
	Lnode* tmp = p->next;
	p->next = tmp->next;
	if (tmp == link_loop->rear)//若p下一个节点是尾指针则将尾指针交给p
	{
		link_loop->rear = p;
	}
	free(tmp);
	--link_loop->num;
}

3.2初始化链表

void initLinkLoop(LinkLoop* link_loop)
{
	link_loop->head.next = &link_loop->head;
	link_loop->rear = &link_loop->head;
	link_loop->num = 0;
}

3.3头插

void insertLinkLoopHeader(LinkLoop* link_loop, element_t v)
{
	Lnode* p = link_loop->rear->next;//&link_loop->head也可
	insertLinkLoop(link_loop, p, v);
}

3.4尾插

void insertLinkLoopRear(LinkLoop* link_loop, element_t v)
{
	Lnode* p = link_loop->rear;
	insertLinkLoop(link_loop, p, v);
}

3.5删除指定节点

int deleteLinkLoop(LinkLoop* link_loop, element_t v)
{
	Lnode* p = &link_loop->head;
	while (p->next != &link_loop->head)
	{
		if (p->next->data == v)
		{
			delLinkLoop(link_loop, p);
			return 1;		//找到
		}
		p = p->next;
	}
	return 0;		//没找到
}

3.6删除所有节点

void deleteAllLinkLoop(LinkLoop* link_loop)
{
	Lnode* p = &link_loop->head;
	while (p->next != &link_loop->head)
	{
		delLinkLoop(link_loop, p);
	}
	link_loop->rear = &link_loop->head;
	printf("list num = %d\n", link_loop->num);
}

3.7展现节点中元素

void showLinkLoop(const LinkLoop* link_loop)
{
	Lnode* p = link_loop->head.next;
	printf("loop_table[%d] : ", link_loop->num);
	while (p != &link_loop->head) //开头已经不是head了
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

4.循环链表的应用：约瑟夫环问题

void init_JoseGame(JosephHead* game, int n)
{
	Node* node = NULL;
	for (int i = 1; i <= n; i++)
	{
		node = (Node*)malloc(sizeof(Node));
		node->data = i;
		if (game->head == NULL)//第一次插入
		{
			game->head = game->tail = node;
		}
		else
		{
			game->tail->next = node;//连接
			game->tail = node;
		}
		game->tail->next = game->head;//回头
	}
}

void showData(const JosephHead* game)
{
	Node* p = game->head;
	do {
		printf("%d\t", p->data);
		p = p->next;
	} while (p != game->head);
	printf("\n");
}

void start_JosephGame(JosephHead* game, int k)
{
//	Node* p = game->head;
//	while (1)
//	{
//		int i = 0;
//		for (i = 1; i < k - 1; i++)
//		{
//			p = p->next;
//		}
//		if (p->next->next == p)
//		{
//			printf("end : %d", p->data);
//			break;
//		}
//		Node* tmp = p->next;
//		p->next = tmp->next;
//		p = p->next;
//	}
	Node* fap = game->head; // 指向正在报数的人
	Node* slp = NULL;		// 
	while (fap->next != fap)
	{
		slp = fap;
		// 按照k值报数
		for (int i = 1; i < k; i++)
		{
			slp = fap;
			fap = fap->next;
		}
		// 使用slp删除后一个节点fap
		slp->next = fap->next;
		printf("%d ", fap->data);
		free(fap);
		fap = slp->next;
	}
	printf("\n the last Person : %d\n", fap->data);
	free(fap);
	game->head = game->head = NULL;
}

四、双向循环链表

此处我们的操作都将借用Linus Benedict Torvalds神也就是linux和git创作者及其团队写出来的代码来讲解，注意此处并非原创，早在linux内核里就有了，因为太NB，我将会借用大神的部分代码来讲。

废话不多说，我们首先先来看双向链表的初始化图

那么接下来大的就要来了

双向链表后面所有操作最核心的操作图就这么来了，即双向链表的插入逻辑

我们操作的顺序逆正都可，此处画和表达的是逆时针

接下来我们看看代码实现，领略大神的逻辑思想

1、双向链表的节点创建

typedef int element_t;
typedef struct dnode
{
	struct dnode* prev;
	element_t data;
	struct dnode* next;
} DNode;

// 带头结点的双向循环链表表头
typedef struct
{
	DNode head;
	int num;
} DLoopList;

2、双向链表的各个接口

void initDLoopList(DLoopList *loop_link);
void insertDLoopLinkHead(DLoopList* loop_link, element_t v);
void insertDLoopLinkRear(DLoopList* loop_link, element_t v);
void showDLoopLink(const DLoopList* loop_link);

void deleteValueDLoopList(DLoopList* loop_link, element_t v);
void deleteAllDLoopList(DLoopList* loop_link);

3、双向循环列表的接口

3.1双向循环链表的通用接口

依依旧旧考虑到插入和删除的统一性，依依旧旧考虑到效率，我们用static限制在此文件里

/* 定义通用的辅助函数接口 插入，删除 */
static void addDNode(DNode* new_node, DNode *prev, DNode *next)
{
	next->prev = new_node;
	new_node->next = next;
	new_node->prev = prev;
	prev->next = new_node;
}

static void delDNode(DNode* prev, DNode* next)
{
	next->prev = prev;
	prev->next = next;
}

3.2初始化链表

void initDLoopList(DLoopList* loop_link, element_t v)
{
	loop_link->head.next = &loop_link->head;
	loop_link->head.prev = &loop_link->head;
	loop_link->num = 0;
}

3.3头插

void insertDLoopLinkHead(DLoopList* loop_link, element_t v)
{
	DNode* new_node = malloc(sizeof(DNode));
	new_node->data = v;
	addDNode(new_node, &loop_link->head, loop_link->head.next);
	++loop_link->num;
}

3.4尾插

void insertDLoopLinkRear(DLoopList* loop_link, element_t v)
{
	DNode* new_node = malloc(sizeof(DNode));
	new_node->data = v;
	addDNode(new_node, loop_link->head.prev, &loop_link->head);
	++loop_link->num;
}

3.5删除指定节点

void deleteValueDLoopList(DLoopList* loop_link, element_t v)
{
	DNode* p = loop_link->head.next;
	while (p != &loop_link->head)
	{
		if (p->data == v)
		{
			delDNode(p->prev,p->next);
			free(p);
			--loop_link->num;
			return;
		}
		p = p->next;
	}
	printf("Not found\n");
}

3.6删除所有节点

void deleteAllDLoopList(DLoopList* loop_link)
{
	DNode* p = loop_link->head.next;
	while (p != &loop_link->head)
	{
		DNode* tmp = p->next;
		free(p);
		p = tmp;
		--loop_link->num;
	}
	loop_link->head.next = &loop_link->head;
	loop_link->head.prev = &loop_link->head;
	printf("table num : %d", loop_link->num);
}

3.7展现节点数据

void showDLoopLink(const DLoopList* loop_link)
{
	DNode* p = loop_link->head.next;
	printf("table[%d] : ", loop_link->num);
	while (p != &loop_link->head)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

五、结语

至此，链表集大成之作结束。

所有测试运行代码

接下来公布各接口测试代码

单向链表

#include"LinkList.h"
#include<stdio.h>
#include<stdlib.h>

//测试带头结点的链表
void test01()
{
	LinkTable table;
	table.num = 0;
	table.head.next = 0;

	for (int i = 0; i < 5; i++)
	{
		//insertHeadTable(&table, i + 100);
		insertRearTable(&table , i + 100);
	}
	showLinkTable(&table);
	insertPosTable(&table, 2, 500);
	showLinkTable(&table);
	deleteValueTable(&table, 500);
	showLinkTable(&table);
	deleteAllLinkTable(&table);
}

void test02()
{
	LinkList List;
	List.num = 0;
	List.ptr_head = NULL;

	for (int i = 0; i < 5; i++)
	{
		insertHeadList(&List, i + 200);
	}
	insertPosList(&List, 2, 500);
	showLinkList(&List);
	deleteValueList(&List, 204);
	showLinkList(&List);
	deleteAllLinkList(&List);
}

void test03()
{
	Lnode* head = NULL;
	for (int i = 0; i < 5; i++)
	{
		head = insertLink(head, 10 + i);
	}

	Lnode* p = head;
	while (p)
	{
		printf("%d\t", p->data);
		p = p->next;
	}
	printf("\n");
}

int main()
{
	test01();
	//test02();
	//test02();

	return 0;
}

循环链表

#include"LinkLoopList.h"
#include<stdio.h>

void test01()
{
	LinkLoop link_loop;
	initLinkLoop(&link_loop);

	for (int i = 0; i < 10; i++)
	{
		//insertLinkLoopHeader(&link_loop, i + 100);
		insertLinkLoopRear(&link_loop, i + 100);
	}
	showLinkLoop(&link_loop);
	deleteLinkLoop(&link_loop, 104);
	showLinkLoop(&link_loop);
	deleteAllLinkLoop(&link_loop);
}

void JosephGameTest()
{
	JosephHead game1 = { NULL,NULL };
	init_JoseGame(&game1, 10);
	showData(&game1);
	printf("start game : \n");
	start_JosephGame(&game1, 3);
}

int main()
{
	//test01();
	JosephGameTest();
	return 0;
}

双向循环链表

#include"DoubleLoopList.h"

DLoopList stu_table;
void test01()
{
	initDLoopList(&stu_table);
	for (int i = 0; i < 5; i++)
	{
		insertDLoopLinkHead(&stu_table, i+100);
	}
	showDLoopLink(&stu_table);
	deleteValueDLoopList(&stu_table, 103);
	showDLoopLink(&stu_table);
	deleteAllDLoopList(&stu_table); 
}

int main()
{
	test01();
	return 0;
}

我是YYYing，后面还有更精彩的内容，希望各位能多多关注支持一下主包。

无限进步，我们下次再见。

上期内容：顺序表

下期内容：顺序栈和链式栈

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

全家桶集齐！Qwen3.5四款小模型上线魔乐社区，附昇腾全套实践教程

魔乐社区

Pont - 搭建前后端之桥：高效、灵活的接口管理工具

Pont 是一款强大的数据服务层解决方案，它能够帮助开发者快速搭建前后端之间的桥梁，实现接口的高效管理和代码自动生成。无论是新手还是有经验的开发者，都能通过 Pont 轻松处理接口文档、生成类型安全的 API 代码，从而显著提升开发效率。[![Pont 工具标志](https://raw.gitcode.com/gh_mirrors/po/pont/raw/3f1b7d4bbba3fd2dda

魔乐社区

如何快速上手 hvac：HashiCorp Vault Python 客户端零基础入门指南

**hvac** 是 HashiCorp Vault 的 Python 3.X 客户端库，专为开发者提供简单高效的 Vault 交互方式。无论你是需要管理密钥、配置身份验证，还是实现安全的秘密数据存储，hvac 都能帮助你轻松搞定 Vault 的各项操作。本文将带你零基础快速入门，从安装到基础操作，让你在几分钟内即可上手使用这个强大的工具。[![hvac 客户端 Logo](https://r