文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >从零开始学链表:数据结构的基础与应用

从零开始学链表:数据结构的基础与应用

作者头像
夜雨声烦1413
发布于 2026-01-12 15:19:09
发布于 2026-01-12 15:19:09
1090
举报

嘿嘿,家人们,今天咱们来详细剖析数据结构中的链表,好啦,废话不多讲,开干!

1:链表

1.1:链表的概念以及结构

链表是一种 物理存储结构上非连续 、 非顺序的存储结构，数据元素的 逻辑顺序 是通过链表 中的 指针链接 次序实现的.

  • 链表的结构跟火车车厢相似, 淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉或者加上,不会影响其他⻋厢，每节⻋厢都是独立存在的.
  • ⻋厢是独立存在的,且每节⻋厢都有车门.可以想象⼀下介样滴的场景，假设每节⻋厢的车门都是锁上的状态,需要不同的钥匙才能解锁,每次只能携带⼀把钥匙的情况下如何从⻋头走到车尾？

最简单的做法：每节车厢里都放一把下⼀节车厢的钥匙.

  1. 从上图我们可以看到,链式结构在逻辑上是连续的,但是在物理上不一定连续.
  2. 现实中的节点一般都是从堆上申请出来的.
  3. 从堆上申请的空间,是按照一定的策略来进行分配的,两次申请的空间可能连续,也可能不连续.
  4. 与顺序表不同的是,链表里的每节"车厢"都是独立申请下来的空间,我们称之为"结点/结点",结点有以下两个组成部分:
  • 图中指针变量 plist保存的是第⼀个节点的地址,我们称plist此时"指向"第⼀个节点,如果我们想要plist“指向”第二个节点时，只需要修改plist保存的内容为0x0012FFB0.

那么为什么还要指针变量来保存下一个节点的位置呢?

  • 链表中每个节点都是 独立申请 的( 即需要插⼊数据时才去申请⼀块节点的空间 ),我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点.

结合前⾯学到的结构体知识,我们可以给出每个节点对应的结构体代码: 假设当前保存的节点为整型.

代码语言：javascript
复制
#include <stdio.h>

struct ListNode
{
	int Value;
	struct ListNode* Next;
};

当我们想要保存⼀个整型数据时,实际是向操作系统申请了⼀块内存,这个内存不仅要保存整型数据,也需要保存下⼀个节点的地址(当下⼀个节点为空时保存的地址为空). 当我们想要从第⼀个节点⾛到最后⼀个节点时,只需要在前⼀个节点拿上下⼀个节点的地址下⼀个节点的钥匙)就可以了.

假设在32位系统上,结点中值域为int类型, 则一个节点的大小为8个字节,则也有可能下面的链表.

1.2:链表的分类

实际中的链表的结构十分多样,组合起来有8种链表结构: 1.单向或双向 2.带头或不带头 3.循环或非循环

虽然链表的结构有如此之多,但实践中最常用的还是两种结构:无头单向非循环链表与带头双向循环链表.

  1. 无头单向非循环链表:结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等.
  2. 带头双向循环链表:结构最复杂,一般用在单独存储数据.实际中使用的链表数据结构,都是带头双向循环链表.

2:无头单向非循环链表的实现

2.1:Single_Linked_List.h

代码语言：javascript
复制
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

//结构声明与函数声明

typedef int LKDataType;

typedef struct SingleList
{
	//存值
	LKDataType data;
	//指向下一个节点的地址
	struct SingleList* next;

}Slist;

//打印链表
void SlistPrint(Slist* phead);

//创建节点
Slist* SlistCreateNode(LKDataType value);

//尾插数据
void SlistPushback(Slist** pphead, LKDataType value);

//头插数据
void SlistPushfront(Slist** pphead, LKDataType value);

//尾删数据
void SlistPopback(Slist** pphead);

//头删数据
void SlistPopfront(Slist** pphead);

//查找节点
Slist* SlistFindNode(Slist* position, LKDataType value);

//在position位置的前面添加数据
void SlistInsert(Slist** pphead, Slist* position, LKDataType value);

//删除
// position位置的删除数据
void SlistDelete(Slist** pphead, Slist* position);

//postion后面位置的添加数据
void SlistInsertAfter(Slist* position, LKDataType value);

//position后面位置的删除数据
void SlistDeleteAfter(Slist* position);

//销毁链表
void SlistDestory(Slist** pphead);

2.2:Single_Linked_List.c

2.2.1:打印链表与创建链表节点
代码语言：javascript
复制
#include "Single_Linked_List.h"
//打印链表
void SlistPrint(Slist* phead)
{
	assert(phead);
	Slist* Current = phead;
	while(Current)
	{
		printf("%d->", Current->data);
		Current = Current->next;
	}
	printf("\n");
}


//创建节点
Slist* SlistCreateNode(LKDataType value)
{
	Slist* NewNode = (Slist *)malloc(sizeof(Slist));
	if(NewNode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	NewNode->data = value;
	NewNode->next = NULL;
	return NewNode;
}
2.2.2:头插与尾插节点
代码语言：javascript
复制
//头插数据
void SlistPushfront(Slist** pphead, LKDataType value)
{
	//确保plist的地址为有效地址
	assert(pphead);
	Slist* NewNode = SlistCreateNode(value);
	//让创建的节点存储最初的头结点的地址;
	NewNode->next = *pphead;
	//让头节点存储新头结点的地址
	*pphead = NewNode;
}

//尾插数据
void SlistPushback(Slist** pphead, LKDataType value)
{
	assert(pphead);
	Slist* NewNode = SlistCreateNode(value);
	//链表为空即phead的地址为NULL
	//这里改变的是结构体的指针,一开始plist指向的地址是NULL
	if (*pphead == NULL)
	{
		*pphead = NewNode;
	}
	else
	{
		//先找到最后一个节点
		Slist* Current = *pphead;
		while(Current->next != NULL)
		{
			//这里改变的是结构体的成员
			Current = Current->next;
		}
		//然后在最后一个节点里存放新节点的地址
		Current->next = NewNode;
	}
}

2.2.3:头删节点与尾删节点

代码语言：javascript
复制
//头删数据
void SlistPopfront(Slist** pphead)
{
	assert(pphead);
	//空节点不能删
	assert(*pphead);
	//记录头节点
	Slist* temp = *pphead;
	//plist指向head的next
	*pphead = (*pphead)->next;
	//释放最初的头结点
	free(temp);
}

//尾删数据
void SlistPopback(Slist** pphead)
{
	assert(pphead);
	//空节点不能删
	assert(*pphead);
	//单独处理一个节点的情况
	if((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//找尾节点的前一个节点
	else
	{
		//记录头节点
		Slist* tail = *pphead;
		Slist* previous = NULL;
		while (tail->next)
		{
			//记录尾节点的前一个节点
			previous = tail;
			//这里改变的是结构体的成员
			tail = tail->next;
		}
		free(tail);
		//找尾之后直接释放(tail可置可不置)
		tail = NULL;
		//将上一个节点的所存储的地址置为空
		previous->next = NULL;
	}

}

2.2.4:查找节点与在position位置的前面插入节点
代码语言：javascript
复制
//查找节点
Slist* SlistFindNode(Slist* phead, LKDataType value)
{
	Slist* current = phead;
	while (current != NULL)
	{
		//根据值来进行查找
		if (current->data == value)
		{
			return current;
		}
		else
		{
			current = current->next;
		}
	}
	return NULL;
}

//在position位置的前面添加数据
void SlistInsert(Slist** pphead, Slist * position, LKDataType value)
{
	assert(pphead);
	//防止一个为空与一个不为空的情况(链表是空的,但是position这一节点不存在)
	assert((!position && !(*pphead)) || (position && *pphead));
	Slist* NewNode = SlistCreateNode(value);
	if (NewNode == NULL)
	{
		perror("CreateNode Fail");
		exit(-1);
	}
	//等于头结点,则是头插
	if (position == *pphead)
	{
		SlistPushfront(pphead, value);
	}
	else
	{
		Slist* Previous = *pphead;
		//找到position位置的前一个节点
		while(Previous->next != position)
		{
			Previous = Previous->next;
		}
		//新节点的next指针指向position位置
		NewNode->next = position;
		//position位置的前一个节点的next指针指向NewNode
		Previous->next = NewNode;
	}
}

有的uu会比较好奇,为什么链表的查找不是像顺序表那样子返回下标呢, 本质原因在于:链表是一种物理存储结构上非连续、非顺序的存储结构,而顺序表是物理存储结构上连续的存储结构.

2.2.5:删除position位置的节点与删除position位置后面的节点以及在position位置后面添加节点
代码语言：javascript
复制
// position位置的删除数据
void SlistDelete(Slist** pphead, Slist* position)
{
	//防止一个为空与一个不为空的情况(链表是空的,但是position这一节点不存在)
	assert((!position && !(*pphead)) || (position && *pphead));
	if (*pphead == position)
	{
		*pphead = position->next;
		free(position);
		position = NULL;
	}
	else
	{
		Slist* Previous = *pphead;
		//找到position位置的前一个节点
		while(Previous->next  != position)
		{
			Previous = Previous->next;
		}
		Previous->next = position->next;
		free(position);
	}
}

//postion后面位置的添加数据
void SlistInsertAfter(Slist* position, LKDataType value)
{
	assert(position);
	Slist* NewNode = SlistCreateNode(value);
	if(NULL == NewNode)
	{
		perror("malloc fail");
		exit(-1);
	}
	NewNode->next = position->next;
	position->next = NewNode;
}

//position后面位置的删除数据
void SlistDeleteAfter(Slist* position)
{
	assert(position);
	Slist* temp = position->next;
	position->next = temp->next;
	free(temp);
}
2.2.6:链表的销毁
代码语言：javascript
复制
//销毁链表
void SlistDestory(Slist** pphead)
{
	assert(pphead);
	Slist* Current = *pphead;
	while(Current)
	{
		Slist* temp = Current->next;
		free(Current);
		Current = temp;
	}
	*pphead = NULL;
}

2.3:Test.c

2.3.1:测试打印链表与创建链表节点
代码语言：javascript
复制
#include "Single_Linked_List.h"

void TestCreateAndPrint(Slist ** pphead)
{
	*pphead = SlistCreateNode(1);
	(*pphead)->next = SlistCreateNode(2);
	(*pphead)->next->next = SlistCreateNode(3);
	(*pphead)->next->next->next = SlistCreateNode(4);
	(*pphead)->next->next->next->next = SlistCreateNode(5);
	SlistPrint(*pphead);
}

int main()
{
	Slist* phead = NULL;
	TestCreateAndPrint(&phead);
	return 0;
}
2.3.2:测试头插与尾插
代码语言：javascript
复制
#include "Single_Linked_List.h"

void TestPushFrontAndPushBack(Slist** pphead) 
{
	SlistPushfront(pphead, 6);
	SlistPushfront(pphead, 5);
	SlistPushfront(pphead, 4);
	SlistPushfront(pphead, 3);
	SlistPrint(*pphead);
	SlistPushback(pphead, 7);
	SlistPushback(pphead, 8);
	SlistPushback(pphead, 9);
	SlistPrint(*pphead);
}
int main()
{
	Slist* phead = NULL;
	TestPushFrontAndPushBack(&phead);
	return 0;
}
2.3.3:测试头删与尾删
代码语言：javascript
复制
#include "Single_Linked_List.h"

void TestPopFrontAndPopBack(Slist** pphead)
{
	SlistPushfront(pphead, 6);
	SlistPushfront(pphead, 5);
	SlistPushfront(pphead, 4);
	SlistPushfront(pphead, 3);
	SlistPushback(pphead, 7);
	SlistPushback(pphead, 8);
	SlistPushback(pphead, 9);
	SlistPrint(*pphead);
	//头删
	SlistPopfront(pphead);
	SlistPopfront(pphead);
	SlistPopfront(pphead);
	SlistPopfront(pphead);
	SlistPrint(*pphead);
	SlistPopback(pphead);
	SlistPopback(pphead);
	SlistPrint(*pphead);
}
int main()
{
	Slist* phead = NULL;
	TestPopFrontAndPopBack(&phead);
	return 0;
}
2.3.4:测试查找与在position位置的前面添加节点
代码语言：javascript
复制
#include "Single_Linked_List.h"

void TestFindAndInsert(Slist** pphead)
{
	SlistPushfront(pphead, 6);
	SlistPushfront(pphead, 5);
	SlistPushfront(pphead, 4);
	SlistPushfront(pphead, 3);
	SlistPushback(pphead, 7);
	SlistPushback(pphead, 8);
	SlistPushback(pphead, 9);
	SlistPrint(*pphead);
	Slist* postion = SlistFindNode(*pphead, 5);
	SlistInsert(pphead,postion,1);
	postion = SlistFindNode(*pphead, 3);
	SlistInsert(pphead, postion, 0);
	SlistPrint(*pphead);
}

int main()
{
	Slist* phead = NULL;
	TestInsertAndDelete(&phead);
	return 0;
}
2.3.6:测试删除position位置的节点与删除position位置后面的节点以及在position位置后面添加节点
代码语言：javascript
复制
#include "single_linked_list.h"
void TestDeleteAndInsertAfter(Slist ** pphead)
{
	SlistPushfront(pphead, 6);
	SlistPushfront(pphead, 5);
	SlistPushfront(pphead, 4);
	SlistPushfront(pphead, 3);
	SlistPushback(pphead, 7);
	SlistPushback(pphead, 8);
	SlistPushback(pphead, 9);
	SlistPrint(*pphead);
	Slist* position = SlistFindNode(*pphead, 5);
	//删除5这个节点
	SlistDelete(pphead, position);
	position = SlistFindNode(*pphead, 3);
	//删除头节点
	SlistDelete(pphead, position);
	SlistPrint(*pphead);
	printf("-------------------------\n");
	position = SlistFindNode(*pphead, 4);
	SlistInsertAfter(position, 10);
	SlistPrint(*pphead);
	printf("-------------------------\n");
	SlistDeleteAfter(position);
	SlistDeleteAfter(position);
	SlistDeleteAfter(position);
	SlistDeleteAfter(position);
	SlistDeleteAfter(position);
	SlistPrint(*pphead);
}

int main()
{
	Slist* phead = NULL;
	TestDeleteAndInsertAfter(&phead);
	return 0;
}
2.3.7:测试链表的销毁
代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS
#include "single_linked_list.h"

//测试头插和尾插
void test1(Slist** list)
{
	printf("头插与尾插:>");
	SlistPushfront(&(*list), 0);
	SlistPushfront(&(*list), 1);
	SlistPushfront(&(*list), 2);
	SlistPushfront(&(*list), 3);
	SlistPushfront(&(*list), 4);
	SlistPushback(&(*list), 5);
	SlistPushback(&(*list), 6);
	SlistPushback(&(*list), 7);
	SlistPrint(*list);
}


int main()
{
	Slist* list = NULL;
	test1(&list);
	SlistDestory(&list);
	return 0;
}

3:无头单向非循环链表的总代码

3.1:Single_Linked_List.h

代码语言：javascript
复制
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//结构声明与函数声明

typedef int LKDataType;

typedef struct SingleList
{
	//存值
	LKDataType data;
	//指向下一个节点的地址
	struct SingleList* next;

}Slist;

//打印链表
void SlistPrint(Slist* phead);

//创建节点
Slist* SlistCreateNode(LKDataType value);

//尾插数据
void SlistPushback(Slist** pphead, LKDataType value);

//头插数据
void SlistPushfront(Slist** pphead, LKDataType value);

//尾删数据
void SlistPopback(Slist** pphead);

//头删数据
void SlistPopfront(Slist** pphead);

//查找节点
Slist* SlistFindNode(Slist* phead, LKDataType value);

//在position位置的前面添加数据
void SlistInsert(Slist** pphead, Slist* position, LKDataType value);

//删除
// position位置的删除数据
void SlistDelete(Slist** pphead, Slist* position);

//postion后面位置的添加数据
void SlistInsertAfter(Slist* position, LKDataType value);

//position后面位置的删除数据
void SlistDeleteAfter(Slist* position);

//销毁链表
void SlistDestory(Slist** pphead);

3.2:Single_Linked_List.c

代码语言：javascript
复制
#include "Single_Linked_List.h"

//打印链表
void SlistPrint(Slist* phead)
{
	assert(phead);
	Slist* Current = phead;
	while(Current)
	{
		printf("%d->", Current->data);
		Current = Current->next;
	}
	printf("\n");
}

//创建节点
Slist* SlistCreateNode(LKDataType value)
{
	Slist* NewNode = (Slist *)malloc(sizeof(Slist));
	if(NewNode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	NewNode->data = value;
	NewNode->next = NULL;
	return NewNode;
}

//头插数据
void SlistPushfront(Slist** pphead, LKDataType value)
{
	//确保plist的地址为有效地址
	assert(pphead);
	Slist* NewNode = SlistCreateNode(value);
	//让创建的节点存储最初的头结点的地址;
	NewNode->next = *pphead;
	//让头节点存储新头结点的地址
	*pphead = NewNode;
}

//尾插数据
void SlistPushback(Slist** pphead, LKDataType value)
{
	assert(pphead);
	Slist* NewNode = SlistCreateNode(value);
	//链表为空即phead的地址为NULL
	//这里改变的是结构体的指针,一开始plist指向的地址是NULL
	if (*pphead == NULL)
	{
		*pphead = NewNode;
	}
	else
	{
		//先找到最后一个节点
		Slist* Current = *pphead;
		while(Current->next != NULL)
		{
			//这里改变的是结构体的成员
			Current = Current->next;
		}
		//然后在最后一个节点里存放新节点的地址
		Current->next = NewNode;
	}
}


//头删数据
void SlistPopfront(Slist** pphead)
{
	assert(pphead);
	//空节点不能删
	assert(*pphead);
	//记录头节点
	Slist* temp = *pphead;
	//plist指向head的next
	*pphead = (*pphead)->next;
	//释放最初的头结点
	free(temp);
}

//尾删数据
void SlistPopback(Slist** pphead)
{
	assert(pphead);
	//空节点不能删
	assert(*pphead);
	//单独处理一个节点的情况
	if((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//找尾节点的前一个节点
	else
	{
		//记录头节点
		Slist* tail = *pphead;
		Slist* previous = NULL;
		while (tail->next)
		{
			//记录尾节点的前一个节点
			previous = tail;
			//这里改变的是结构体的成员
			tail = tail->next;
		}
		free(tail);
		//找尾之后直接释放(tail可置可不置)
		tail = NULL;
		//将上一个节点的所存储的地址置为空
		previous->next = NULL;
	}

}

//查找节点
Slist* SlistFindNode(Slist* phead, LKDataType value)
{
	Slist* current = phead;
	while (current != NULL)
	{
		//根据值来进行查找
		if (current->data == value)
		{
			return current;
		}
		else
		{
			current = current->next;
		}
	}
	return NULL;
}

//在position位置的前面添加数据
void SlistInsert(Slist** pphead, Slist * position, LKDataType value)
{
	assert(pphead);
	//防止一个为空与一个不为空的情况(链表是空的,但是position这一节点不存在)
	assert((!position && !(*pphead)) || (position && *pphead));
	Slist* NewNode = SlistCreateNode(value);
	if (NewNode == NULL)
	{
		perror("CreateNode Fail");
		exit(-1);
	}
	//等于头结点,则是头插
	if (position == *pphead)
	{
		SlistPushfront(pphead, value);
	}
	else
	{
		Slist* Previous = *pphead;
		//找到position位置的前一个节点
		while(Previous->next != position)
		{
			Previous = Previous->next;
		}
		//新节点的next指针指向position位置
		NewNode->next = position;
		//position位置的前一个节点的next指针指向NewNode
		Previous->next = NewNode;
	}
}

//删除
// position位置的删除数据
void SlistDelete(Slist** pphead, Slist* position)
{
	//防止一个为空与一个不为空的情况(链表是空的,但是position这一节点不存在)
	assert((!position && !(*pphead)) || (position && *pphead));
	if (*pphead == position)
	{
		*pphead = position->next;
		free(position);
		position = NULL;
	}
	else
	{
		Slist* Previous = *pphead;
		//找到position位置的前一个节点
		while(Previous->next  != position)
		{
			Previous = Previous->next;
		}
		Previous->next = position->next;
		free(position);
	}
}

//postion后面位置的添加数据
void SlistInsertAfter(Slist* position, LKDataType value)
{
	assert(position);
	Slist* NewNode = SlistCreateNode(value);
	if(NULL == NewNode)
	{
		perror("malloc fail");
		exit(-1);
	}
	NewNode->next = position->next;
	position->next = NewNode;
}

//position后面位置的删除数据
void SlistDeleteAfter(Slist* position)
{
	assert(position);
	Slist* temp = position->next;
	position->next = temp->next;
	free(temp);
}


//销毁链表
void SlistDestory(Slist** pphead)
{
	assert(pphead);
	Slist* Current = *pphead;
	while(Current)
	{
		Slist* temp = Current->next;
		free(Current);
		Current = temp;
	}
	*pphead = NULL;
}

3.3:Test.c

代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS
#include "single_linked_list.h"

//测试头插和尾插
void test1(Slist** list)
{
	printf("头插与尾插:>");
	SlistPushfront(&(*list), 0);
	SlistPushfront(&(*list), 1);
	SlistPushfront(&(*list), 2);
	SlistPushfront(&(*list), 3);
	SlistPushfront(&(*list), 4);
	SlistPushback(&(*list), 5);
	SlistPushback(&(*list), 6);
	SlistPushback(&(*list), 7);
	SlistPrint(*list);
}

//测试头删和尾删
void test2(Slist** list)
{
	printf("头删与尾删:>");
	SlistPopback(&(*list));
	SlistPopback(&(*list));
	SlistPopback(&(*list));
	SlistPopfront(list);
	SlistPopfront(list);
	SlistPrint(*list);
}

//测试查找与任意位置的增加
void test3(Slist** list)
{
	//链表与要插入的位置都为空的情况
	Slist* position = SlistFindNode(*list, 2);
	SlistInsert(&(*list), position, 5);
	SlistPrint(*list);
	position = SlistFindNode(*list, 5);
	SlistInsert(&(*list), position, 8);
	SlistInsert(&(*list), position, 9);
	SlistInsert(&(*list), position, 10);
	SlistPrint(*list);
}

//测试查找与任意位置的删除
void test4(Slist** list)
{

	SlistPushfront(list, 3);
	Slist* position = SlistFindNode(*list, 10);
	SlistPrint(*list);
	SlistDelete(list, position);
	SlistPrint(*list);

	SlistPushback(list, 5);
	SlistPushback(list, 6);
	SlistPushback(list, 7);
	SlistPushfront(list, 4);
	SlistPushfront(list, 3);
	position = SlistFindNode(*list, 5);
	SlistDelete(list, position);
	SlistPrint(*list);
}
//测试在position位置之后的数据添加与删除与链表销毁
void test5(Slist** list)
{
	SlistPushback(list, 5);
	SlistPushback(list, 6);
	SlistPushback(list, 7);
	SlistPushfront(list, 4);
	SlistPushfront(list, 3);
	SlistPrint(*list);

	Slist* position = SlistFindNode(*list, 5);
	SlistInsertAfter(position, 20);
	SlistInsertAfter(position, 30);
	SlistPrint(*list);

	SlistDeleteAfter(position);
	SlistDeleteAfter(position);
	SlistDeleteAfter(position);
	SlistDeleteAfter(position);
	SlistPrint(*list);
	SlistDestory(list);
}

int main()
{
	Slist* list = NULL;
	test1(&list);
	test2(&list);
	test3(&list);
	test4(&list);
	test5(&list);
	return 0;
}

4:带头双向循环链表的实现

4.1:Doubly_Circular_Linked_List.h

代码语言：javascript
复制
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int CircularDatatype;

typedef struct CircularList
{
	struct CircularList* next;
	struct CircularList* previos;
	CircularDatatype value; 
}CircularList;

//创建节点
CircularList* CreateNewnode(CircularDatatype value);

//初始化带头双向循环链表
void CircularListInit(CircularList** phead);

//尾插数据
void CircularListPushback(CircularList* phead, CircularDatatype value);

//尾删数据
void CircularListPopback(CircularList* phead);

//头插数据
void CircularListPushfront(CircularList* phead, CircularDatatype value);

//头删数据
void CircularListPopfront(CircularList* phead);

//查找节点
CircularList* CircularListFind(CircularList* phead, CircularDatatype value);

//在position位置的前面添加数据
void CircularListInsert(CircularList* postion,CircularDatatype value);


//删除postion位置的节点
void  CircularListErase(CircularList* phead,CircularList* position);

//销毁链表
void CircularListDestory(CircularList* phead);

//打印带头双向循环链表
void CircularListPrint(CircularList* phead);

4.2:Doubly_Circular_Linked_List.c

4.2.1:初始化与创建节点与尾插
代码语言：javascript
复制
#include "Doubly_Circular_Linked_List.h"

//创建节点
CircularList* CreateNewnode(CircularDatatype value)
{
	CircularList* NewNode = (CircularList *)malloc(sizeof(CircularList));
	if (NewNode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	NewNode->value = value;
	NewNode->previos = NULL;
	NewNode->next = NULL;
	return NewNode;
}

//打印带头双向循环链表
void CircularListPrint(CircularList* phead)
{
	assert(phead);
	CircularList* Current = phead->next;
	while(Current != phead)
	{
		printf("%d->", Current->value);
		Current = Current->next;
	}
}
//初始化带头双向循环链表
void CircularListInit(CircularList** pphead)
{
	//确保传过来的地址是有效地址
	assert(pphead);
	//创建哨兵位的头结点
	*pphead = CreateNewnode(-1);
	//指向自己
	(*pphead)->previos = *pphead;
	(*pphead)->next = *pphead;
}

//尾插数据
void CircularListPushback(CircularList* phead, CircularDatatype value)
{
	assert(phead);
	//创建节点
	CircularList* NewNode = CreateNewnode(value);
	if(NewNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	CircularList* tail = phead->previos;
	//新节点的前驱链接旧链表的尾节点
	NewNode->previos = tail;
	//旧尾节点存储新尾节点的地址
	tail->next = NewNode;
	//哨兵位的前驱节点链接新节点
	phead->previos = NewNode;
	//新节点的next指针指向头结点
	NewNode->next = phead;
}

4.2.2:尾删与头插与头删数据
代码语言：javascript
复制
//尾删数据
void CircularListPopback(CircularList* phead)
{
	assert(phead);
	CircularList* tail = phead->previos;
	//哨兵位的前驱节点指向尾节点的前驱
	phead->previos = tail->previos;
	//尾节点的前驱节点的next指向哨兵位
	tail->previos->next = phead;
	free(tail);
	tail = NULL;
}

//头插数据
void CircularListPushfront(CircularList* phead, CircularDatatype value)
{
	assert(phead);
	CircularList* NewNode = CreateNewnode(value);
	if (NewNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//记录旧的头结点
	CircularList* OldHead = phead->next;
	//哨兵位的next指针指向NewNode
	phead->next = NewNode;
	//新节点的前驱指向哨兵位
	NewNode->previos = phead;
	//新节点的后驱指向旧的头节点
	NewNode->next = OldHead;
	//旧的头结点的前驱指向NewNode
	OldHead->previos = NewNode;
}

//头删数据
void CircularListPopfront(CircularList* phead)
{
	assert(phead);
	//保存旧的头节点
	CircularList* OldHead = phead->next;
	//哨兵位头节点的next指针指向旧的头节点的next
	phead->next = OldHead->next;
	//旧的头节点的下一个节点的前驱节点指向哨兵位
	OldHead->next->previos = phead;
	free(OldHead);
}

4.2.3:查找节点与在position位置的前面插入节点
代码语言：javascript
复制
//查找节点
CircularList* CircularListFind(CircularList* phead, CircularDatatype value)
{
	assert(phead);
	CircularList* Current = phead;
	while(Current->next != phead)
	{
		if (Current->value == value)
			return Current;
		Current = Current->next;
	}
	return NULL;
}

//在position位置的前面添加数据
void CircularListInsert(CircularList* postion, CircularDatatype value)
{
	assert(postion);
	CircularList* NewNode = CreateNewnode(value);
	//新节点的前驱指向posituon位置的前一个节点
	NewNode->previos = postion->previos;
	//新节点的next指向position节点
	NewNode->next = postion;
	//position位置的前一个节点next指向新节点
	postion->previos->next = NewNode;
	//position位置的节点的前驱指向NewNode
	postion->previos = NewNode;
}

4.2.4:删除position位置的节点与销毁链表
代码语言：javascript
复制
//删除postion位置的节点
void  CircularListErase(CircularList* phead, CircularList* position)
{
	assert(phead);
	CircularList* temp = position->previos;
	//temp的next指针指向position的下一个节点
	temp->next = position->next;
	//position的下一个节点的前驱指向temp
	position->next->previos = temp;
}

//销毁链表
void CircularListDestory(CircularList* phead)
{
	assert(phead);
	CircularList* Current = phead->next;
	while(Current != phead)
	{
		CircularList* temp = Current->next;
		free(Current);
		Current = temp;
	}
}

4.3:Test.c

4.3.1:测试初始化与创建节点与尾插
代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"

void TestInitAndPushBack(CircularList ** List)
{
	CircularListInit(List);
	CircularListPushback(*List,1);
	CircularListPushback(*List,2);
	CircularListPushback(*List,3);
	CircularListPrint(*List);
}

int main()
{
	CircularList* List;
	TestInitAndPushBack(&List);
	return 0;
}
4.3.2:测试尾删与头插与头删数据
代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"

void TestPushFrontAndPopFrontAndPopBack(CircularList** List)
{
	CircularListInit(List);
	CircularListPushback(*List, 1);
	CircularListPushback(*List, 2);
	CircularListPushback(*List, 3);
	CircularListPrint(*List);
	CircularListPopback(*List);
	CircularListPopback(*List);
	CircularListPrint(*List);
	CircularListPushfront(*List, 5);
	CircularListPushfront(*List, 4);
	CircularListPushfront(*List, 6);
	CircularListPrint(*List);
	CircularListPopfront(*List);
	CircularListPopfront(*List);
	CircularListPrint(*List);

}

int main()
{
	CircularList* List;
	//TestInitAndPushBack(&List);
	TestPushFrontAndPopFrontAndPopBack(&List);
	return 0;
}
4.3.3:测试查找节点与在position位置的前面插入节点
代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"

void TestFindAndInsert(CircularList** List)
{
	CircularListInit(List);
	CircularListPushback(*List, 1);
	CircularListPushback(*List, 2);
	CircularListPushback(*List, 3);

	CircularListPrint(*List);
	CircularList* position = CircularListFind(*List, 2);
	CircularListInsert(position, 4);
	position = CircularListFind(*List, 1);
	CircularListInsert(position, 25);
	CircularListPrint(*List);
}

int main()
{
	CircularList* List;
	TestFindAndInsert(&List);
	return 0;
}
4.3.4:测试删除position位置的节点与销毁链表
代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"


void TestEraseAndDestory(CircularList** List)
{
	CircularListInit(List);
	CircularListPushback(*List, 1);
	CircularListPushback(*List, 2);
	CircularListPushback(*List, 3);

	CircularListPrint(*List);
	CircularList* position = CircularListFind(*List, 2);
	CircularListInsert(position, 4);
	position = CircularListFind(*List, 1);
	CircularListPrint(*List);
	printf("\n");

	CircularListErase(*List, position);
	position = CircularListFind(*List, 2);
	CircularListErase(*List, position);
	CircularListPrint(*List);
	CircularListDestory(*List);
	//释放哨兵位的头结点
	free(*List);
	*List = NULL;
	CircularListPrint(*List);
}

int main()
{
	CircularList* List;
	TestEraseAndDestory(&List);
	return 0;
}

5:带头双向循环链表的总代码

5.1:Doubly_Circular_Linked_List.h

代码语言：javascript
复制
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int CircularDatatype;

typedef struct CircularList
{
	struct CircularList* next;
	struct CircularList* previos;
	CircularDatatype value;
}CircularList;

//创建节点
CircularList* CreateNewnode(CircularDatatype value);

//初始化带头双向循环链表
void CircularListInit(CircularList** phead);

//尾插数据
void CircularListPushback(CircularList* phead, CircularDatatype value);

//尾删数据
void CircularListPopback(CircularList* phead);

//头插数据
void CircularListPushfront(CircularList* phead, CircularDatatype value);

//头删数据
void CircularListPopfront(CircularList* phead);

//查找节点
CircularList* CircularListFind(CircularList* phead, CircularDatatype value);

//在position位置的前面添加数据
void CircularListInsert(CircularList* postion, CircularDatatype value);


//删除postion位置的节点
void  CircularListErase(CircularList* phead, CircularList* position);

//销毁链表
void CircularListDestory(CircularList* phead);

//打印带头双向循环链表
void CircularListPrint(CircularList* phead);

5.2:Doubly_Circular_Linked_List.c

代码语言：javascript
复制
#include "Doubly_Circular_Linked_List.h"

//创建节点
CircularList* CreateNewnode(CircularDatatype value)
{
	CircularList* NewNode = (CircularList *)malloc(sizeof(CircularList));
	if (NewNode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	NewNode->value = value;
	NewNode->previos = NULL;
	NewNode->next = NULL;
	return NewNode;
}

//打印带头双向循环链表
void CircularListPrint(CircularList* phead)
{
	assert(phead);
	CircularList* Current = phead->next;
	while(Current != phead)
	{
		printf("%d->", Current->value);
		Current = Current->next;
	}
	printf("\n");
}
//初始化带头双向循环链表
void CircularListInit(CircularList** pphead)
{
	//确保传过来的地址是有效地址
	assert(pphead);
	//创建哨兵位的头结点
	*pphead = CreateNewnode(-1);
	//指向自己
	(*pphead)->previos = *pphead;
	(*pphead)->next = *pphead;
}

//尾插数据
void CircularListPushback(CircularList* phead, CircularDatatype value)
{
	assert(phead);
	//创建节点
	CircularList* NewNode = CreateNewnode(value);
	if(NewNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	CircularList* tail = phead->previos;
	//新节点的前驱链接旧链表的尾节点
	NewNode->previos = tail;
	//旧尾节点存储新尾节点的地址
	tail->next = NewNode;
	//哨兵位的前驱节点链接新节点
	phead->previos = NewNode;
	//新节点的next指针指向头结点
	NewNode->next = phead;
}

//尾删数据
void CircularListPopback(CircularList* phead)
{
	assert(phead);
	CircularList* tail = phead->previos;
	//哨兵位的前驱节点指向尾节点的前驱
	phead->previos = tail->previos;
	//尾节点的前驱节点的next指向哨兵位
	tail->previos->next = phead;
	free(tail);
	tail = NULL;
}

//头插数据
void CircularListPushfront(CircularList* phead, CircularDatatype value)
{
	assert(phead);
	CircularList* NewNode = CreateNewnode(value);
	if (NewNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//记录旧的头结点
	CircularList* OldHead = phead->next;
	//哨兵位的next指针指向NewNode
	phead->next = NewNode;
	//新节点的前驱指向哨兵位
	NewNode->previos = phead;
	//新节点的后驱指向旧的头节点
	NewNode->next = OldHead;
	//旧的头结点的前驱指向NewNode
	OldHead->previos = NewNode;
}

//头删数据
void CircularListPopfront(CircularList* phead)
{
	assert(phead);
	//保存旧的头节点
	CircularList* OldHead = phead->next;
	//哨兵位头节点的next指针指向旧的头节点的next
	phead->next = OldHead->next;
	//旧的头节点的下一个节点的前驱节点指向哨兵位
	OldHead->next->previos = phead;
	free(OldHead);
}

//查找节点
CircularList* CircularListFind(CircularList* phead, CircularDatatype value)
{
	assert(phead);
	CircularList* Current = phead;
	while(Current->next != phead)
	{
		if (Current->value == value)
			return Current;
		Current = Current->next;
	}
	return NULL;
}

//在position位置的前面添加数据
void CircularListInsert(CircularList* postion, CircularDatatype value)
{
	assert(postion);
	CircularList* NewNode = CreateNewnode(value);
	//新节点的前驱指向posituon位置的前一个节点
	NewNode->previos = postion->previos;
	//新节点的next指向position节点
	NewNode->next = postion;
	//position位置的前一个节点next指向新节点
	postion->previos->next = NewNode;
	//position位置的节点的前驱指向NewNode
	postion->previos = NewNode;
}

//删除postion位置的节点
void  CircularListErase(CircularList* phead, CircularList* position)
{
	assert(phead);
	CircularList* temp = position->previos;
	//temp的next指针指向position的下一个节点
	temp->next = position->next;
	//position的下一个节点的前驱指向temp
	position->next->previos = temp;
}

//销毁链表
void CircularListDestory(CircularList* phead)
{
	assert(phead);
	CircularList* Current = phead->next;
	while(Current != phead)
	{
		CircularList* temp = Current->next;
		free(Current);
		Current = temp;
	}
}

5.3:Test.c

代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"

//测试初始化,尾删与尾插
void test1(CircularList* phead)
{
	printf("尾插与尾删:>");
	CircularListInit(&phead);
	CircularListPushback(phead, 1);
	CircularListPushback(phead, 2);
	CircularListPushback(phead, 3);
	CircularListPushback(phead, 4);
	CircularListPushback(phead, 5);
	CircularListPushback(phead, 6);
	CircularListPopback(phead);
	CircularListPopback(phead);
	CircularListPopback(phead);
	CircularListPrint(phead);

}
//测试头插与头删
void test2(CircularList* phead)
{
	printf("头插与头删:>");
	CircularListInit(&phead);
	CircularListPushfront(phead, 0);
	CircularListPushfront(phead, 1);
	CircularListPushfront(phead, 2);
	CircularListPushfront(phead, 3);
	CircularListPushfront(phead, 4);
	CircularListPushfront(phead, 5);
	CircularListPushfront(phead, 6);

	CircularListPopfront(phead);
	CircularListPopfront(phead);
	CircularListPopfront(phead);
	CircularListPopfront(phead);
	CircularListPrint(phead);
}

//测试查找与在position位置的前面添加数据与删除position位置的数据
void test3(CircularList* phead)
{
	CircularListInit(&phead);
	CircularListPushfront(phead, 3);
	CircularListPushfront(phead, 4);
	CircularListPushfront(phead, 5);
	CircularListPushfront(phead, 6);
	CircularListPushfront(phead, 7);
	CircularList* position = CircularListFind(phead, 5);
	if (position != NULL)
	{
		position->value = position->value * 15;
	}
	CircularListInsert(position, 72);
	CircularListInsert(position, 73);
	CircularListInsert(position, 74);
	CircularListPrint(phead);
	if (position != NULL)
	{
		CircularListErase(phead, position);
		position = NULL;
	}
	CircularListPrint(phead);
}
//测试销毁链表
void test4(CircularList* phead)
{
	CircularListInit(&phead);
	CircularListPushfront(phead, 3);
	CircularListPushfront(phead, 4);
	CircularListPushfront(phead, 5);
	CircularListPushfront(phead, 6);
	CircularListPushfront(phead, 7);
	CircularListPrint(phead);
	CircularListDestory(phead);
	phead = NULL;
}

int main()
{
	CircularList* phead = NULL;
	test1(phead);
	test2(phead);
	test3(phead);
	test4(phead);
}

6:顺序表与链表的区别

不同点

顺序表

链表

存储空间上

物理和逻辑上一定连续

逻辑上连续,但是物理上不一定连续.

访问方式

随机访问,O(1)

不支持随机访问,O(N)

任意位置插入与删除

可能需要迁移元素,O(N);

只需要修改指针指向

插入

动态顺序表,空间不够时需要扩容.

没有容量的概念

应用场景

元素高效存储 + 频繁访问

元素高效存储 + 频繁访问

缓存利用率

高

低

好啦,uu们,数据结构链表这部分滴详细内容博主就讲到这里啦,如果uu们觉得博主讲的不错的话,请动动你们滴小手给博主点点赞,你们滴鼓励将成为博主源源不断滴动力,同时也欢迎大家来指正博主滴错误~

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2026-01-12，如有侵权请联系 cloudcommunity@tencent.com 删除
链表
数据
数据结构
position
基础

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

链表
数据
数据结构
position
基础
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 1:链表
    • 1.1:链表的概念以及结构
    • 1.2:链表的分类
  • 2:无头单向非循环链表的实现
    • 2.1:Single_Linked_List.h
    • 2.2:Single_Linked_List.c
      • 2.2.1:打印链表与创建链表节点
      • 2.2.2:头插与尾插节点
      • 2.2.4:查找节点与在position位置的前面插入节点
      • 2.2.5:删除position位置的节点与删除position位置后面的节点以及在position位置后面添加节点
      • 2.2.6:链表的销毁
    • 2.3:Test.c
      • 2.3.1:测试打印链表与创建链表节点
      • 2.3.2:测试头插与尾插
      • 2.3.3:测试头删与尾删
      • 2.3.4:测试查找与在position位置的前面添加节点
      • 2.3.6:测试删除position位置的节点与删除position位置后面的节点以及在position位置后面添加节点
      • 2.3.7:测试链表的销毁
  • 3:无头单向非循环链表的总代码
    • 3.1:Single_Linked_List.h
    • 3.2:Single_Linked_List.c
    • 3.3:Test.c
  • 4:带头双向循环链表的实现
    • 4.1:Doubly_Circular_Linked_List.h
    • 4.2:Doubly_Circular_Linked_List.c
      • 4.2.1:初始化与创建节点与尾插
      • 4.2.2:尾删与头插与头删数据
      • 4.2.3:查找节点与在position位置的前面插入节点
      • 4.2.4:删除position位置的节点与销毁链表
    • 4.3:Test.c
      • 4.3.1:测试初始化与创建节点与尾插
      • 4.3.2:测试尾删与头插与头删数据
      • 4.3.3:测试查找节点与在position位置的前面插入节点
      • 4.3.4:测试删除position位置的节点与销毁链表
  • 5:带头双向循环链表的总代码
    • 5.1:Doubly_Circular_Linked_List.h
    • 5.2:Doubly_Circular_Linked_List.c
    • 5.3:Test.c
  • 6:顺序表与链表的区别
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论