【数据结构篇】探索底层容器本身的实现，链表篇

这里可以看链表的结构来进行链表的构建链表的结构跟⽕⻋⻋厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。⻋厢是独⽴存在的，且每节⻋厢都有⻋⻔。想象⼀下这样的场景，假设每节⻋厢的⻋⻔都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾？最简单的做法：每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙

在链表中的体现

与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/节点” 节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。图中指针变量plist保存的是第⼀个节点的地址，我们称plist此时“指向”第一个节点，如果我们希望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA0。为什么还需要指针变量来保存下⼀个节点的位置？链表中每个节点都是独⽴申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。

在链表中我们定义的结构体为（typedef是为了后期的好使用）

typedef int SListtype;

typedef struct SListNode
{
	SListtype date;
	struct SListNode* next;
}SLN;

开始存入的数据不确定我们采用重命名后期好修改

date--->是储存的数据

next--->指向下一个结构体的指针

我们要在链表实现的操作

//链表的打印
void SLNprint(SLN* phead);

//链表的尾插
void SLNpushBack(SLN **phead,SListtype x);

//链表的头插
void SLNpushFront(SLN** phead, SListtype x);

//链表的尾删
void SLNpopBack(SLN** phead);

//链表的头删
void SLNpopFront(SLN** phead);

//链表的查找
SLN* SLNfind(SLN* phead, SListtype x);

//指定位置之前插入数据
void SLNpushsrand(SLN** phead,SLN* pos, SListtype x);//pos表示在这个节点之前

//在指定位置之后插⼊数据
void SLTInsertAfter(SLN* pos, SListtype x);

//删除pos节点
void SLTErase(SLN** pphead, SLN* pos);

//删除pos之后的节点
void SLTEraseAfter(SLN* pos);

//销毁链表
void SListDesTroy(SLN** pphead);

1->链表的打印

这里主要是链表不为NULL就继续打印，phead=phead->next就是让phead等于他所指向的下一个节点，最后的打印主要是让我们更能清楚的看到链表是否为空

void SLNprint(SLN* phead)
{
	while (phead)
	{
		printf("%d->", phead->date);
		phead = phead->next;
	}
	printf("NULL\n");
}

2->链表的尾插

（在插入的时候一定要进行空间的申请了链接一个申请一个）

这个空间的盛情要注意要将申请到的节点的地址返回去，要在链表的指定地方将值进行插入进去

//链表的空间申请
SLN* Applist(SListtype x)
{
	SLN* newSLiN = (SLN*)malloc(sizeof(SLN));
	if (newSLiN == NULL)
	{
		perror("maolloc fail!");
		exit(1);
	}
	else
	{
		newSLiN->date = x;
	}
	return newSLiN;
}

尾插的时候要接受那个你申请出的节点的地址（并且将原尾节点的next指针来接到你所申请的指针上面并且将新指针的next指针置为空）
文中的while循环时因为你传的是头节点要进去寻找原的尾节点进行操作

为什么传二级指针：

因为我要对原链表进行更改

void SLNpushBack(SLN **phead,SListtype x)
{
	assert(phead);
	SLN*newSLiN=Applist(x);
	newSLiN->next = NULL;
	if (*phead == NULL)
	{
		*phead = newSLiN;
	}
	else
	{
		SLN * ptr = *phead;
		while (ptr->next)
		{
			ptr = ptr->next;
		}
		ptr->next = newSLiN;
	}
}

3->头插

了解了尾插之后头插更简单了（只要将申请的节点的next指针指向原来的头节点即可）

别忘了将phead进行更新就行

void SLNpushFront(SLN ** phead, SListtype x)
{
	assert(phead);
	SLN* newSLiN=(SLN*)Applist(x);
	newSLiN->next = *phead;
	*phead = newSLiN;//覆盖了只是因为出的是指针这样受位置的地址就发生了改变
}

4->尾删

同样进行遍历找到尾节点将尾节点的前一个结点的next指针进行指向NULL就可以（同时free掉尾巴节点就行）

//链表的尾删
void SLNpopBack(SLN ** phead)
{
	assert(phead && *phead);
	SLN* ptail = *phead;
	SLN* ptr = *phead;
	ptail = ptail->next;
	while (ptail->next)
	{
		ptail = ptail->next;
		ptr = ptr->next;
	}
	free(ptail);
	ptail = NULL;
	ptr->next = NULL;
}

5->头删

头删更简单一些直接让头节点指向下一个节点就行别忘了将此空间销毁

//链表的头删
void SLNpopFront(SLN ** phead)
{
	assert(phead && *phead);
	SLN* ptr = *phead;
	*phead = ptr->next;
	free(ptr);
	ptr = NULL;
}

6->链表的查找

在链表中实现查找有利于一些后续的操作

我们从头结点开始一直向下取寻找直到找到了直接返回该节点的指针

等到你用遍历的参数走到NULL也就查询结束了直接返回NULL就可以

//链表的查找
SLN* SLNfind(SLN* phead, SListtype x)
{
	assert(phead);
	SLN* as = phead;
	while (as)
	{
		if (as->date == x)
		{
			printf("找到了!!!!!!!!!\n");
			return as;
		}
		as = as->next;
	}
	//没找到
	printf("没找到\n");
	return NULL;
}

7>在指定位置之前插入数据

这里就要找到我们第一个所写的查找函数了（这些就是在test文件中进行查找相关的操作）

这里要注意判断一下是不是要头如果是就执行一下头插类似的操作不要调用

在相关位置进行插入将钱一个指针的指向要插入的节点，将要插入的那个节点指针指向查找的数据

void SLNpushsrand(SLN** phead, SLN* pos, SListtype x)
{
	assert(pos && phead);
	SLN* newSLiN = Applist(x);
	if (pos == *phead)
	{
		newSLiN->next = *phead;
		*phead = newSLiN;
	}
	else
	{
		SLN* bl = *phead;
		while (bl->next != pos)
		{
			bl = bl->next;
		}
		bl->next = newSLiN;
		newSLiN->next = pos;
	}
}

8->在相关位置之后插入数据

这相对前一个就比较简单了

直接将查找的数据进行操作

//在指定位置之后插⼊数据
void SLTInsertAfter(SLN* pos, SListtype x)
{
	assert(pos);
	SLN* newSLiN = Applist(x);
	newSLiN->next = pos->next;
	pos->next = newSLiN;
}

9->删除对应的pos节点

这里要注意的是：这里传入二级指针相当于传入属于传值但当那面的二级指针*后会访问这个一级指针的值

//删除pos节点
void SLTErase(SLN** pphead, SLN* pos)
{
	assert(pphead && pos && *pphead);
	if (pos = *pphead)
	{
		SLNpopFront(pphead);//这里传入二级指针相当于传入属于传值但当那面的二级指针*后会访问这个一级指针的值
	}
	else
	{
		SLN* ptr= *pphead;
		while (ptr->next  !=  pos)
		{
			ptr = ptr->next;
		}
		ptr->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

10->删除pos之后的节点

void SLTEraseAfter(SLN* pos)
{
	assert(pos);
	SLN* ptr = pos->next;
	pos->next = ptr->next;

	free(ptr);
	ptr = NULL;
}

11--->销毁链表

就将头节点进行保存然后依次取free节点（销毁前要进行保存到下个值避免找不到）

别忘了free掉头节点并叫他置为NULL

void SListDesTroy(SLN** pphead)
{
	assert(pphead && *pphead);
	SLN* ptr = *pphead;
	while (ptr)
	{
		SLN* next1 = ptr->next;
		free(ptr);
		ptr = next1;
	}
	*pphead = NULL;
}

展示所有函数的实现

#include"SListNode.h"
//链表的打印
void SLNprint(SLN* phead)
{
	while (phead)
	{
		printf("%d->", phead->date);
		phead = phead->next;
	}
	printf("NULL\n");
}

//链表的空间申请
SLN* Applist(SListtype x)
{
	SLN* newSLiN = (SLN*)malloc(sizeof(SLN));
	if (newSLiN == NULL)
	{
		perror("maolloc fail!");
		exit(1);
	}
	else
	{
		newSLiN->date = x;
	}
	return newSLiN;
}

//链表的尾插
void SLNpushBack(SLN **phead,SListtype x)
{
	assert(phead);
	SLN*newSLiN=Applist(x);
	newSLiN->next = NULL;
	if (*phead == NULL)
	{
		*phead = newSLiN;
	}
	else
	{
		SLN * ptr = *phead;
		while (ptr->next)
		{
			ptr = ptr->next;
		}
		ptr->next = newSLiN;
	}
}

//链表的头插
void SLNpushFront(SLN ** phead, SListtype x)
{
	assert(phead);
	SLN* newSLiN=(SLN*)Applist(x);
	newSLiN->next = *phead;
	*phead = newSLiN;//覆盖了只是因为出的是指针这样受位置的地址就发生了改变
}

//链表的尾删
void SLNpopBack(SLN ** phead)
{
	assert(phead && *phead);
	SLN* ptail = *phead;
	SLN* ptr = *phead;
	ptail = ptail->next;
	while (ptail->next)
	{
		ptail = ptail->next;
		ptr = ptr->next;
	}
	free(ptail);
	ptail = NULL;
	ptr->next = NULL;
}

//链表的头删
void SLNpopFront(SLN ** phead)
{
	assert(phead && *phead);
	SLN* ptr = *phead;
	*phead = ptr->next;
	free(ptr);
	ptr = NULL;
}

//链表的查找
SLN* SLNfind(SLN* phead, SListtype x)
{
	assert(phead);
	SLN* as = phead;
	while (as)
	{
		if (as->date == x)
		{
			printf("找到了!!!!!!!!!\n");
			return as;
		}
		as = as->next;
	}
	//没找到
	printf("没找到\n");
	return NULL;
}

//指定位置之前插入数据
void SLNpushsrand(SLN** phead, SLN* pos, SListtype x)
{
	assert(pos && phead);
	SLN* newSLiN = Applist(x);
	if (pos == *phead)
	{
		newSLiN->next = *phead;
		*phead = newSLiN;
	}
	else
	{
		SLN* bl = *phead;
		while (bl->next != pos)
		{
			bl = bl->next;
		}
		bl->next = newSLiN;
		newSLiN->next = pos;
	}
}

//在指定位置之后插⼊数据
void SLTInsertAfter(SLN* pos, SListtype x)
{
	assert(pos);
	SLN* newSLiN = Applist(x);
	newSLiN->next = pos->next;
	pos->next = newSLiN;
}


//删除pos节点
void SLTErase(SLN** pphead, SLN* pos)
{
	assert(pphead && pos && *pphead);
	if (pos = *pphead)
	{
		SLNpopFront(pphead);//这里传入二级指针相当于传入属于传值但当那面的二级指针*后会访问这个一级指针的值
	}
	else
	{
		SLN* ptr= *pphead;
		while (ptr->next  !=  pos)
		{
			ptr = ptr->next;
		}
		ptr->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

//删除pos之后的节点
void SLTEraseAfter(SLN* pos)
{
	assert(pos);
	SLN* ptr = pos->next;
	pos->next = ptr->next;

	free(ptr);
	ptr = NULL;
}

//销毁链表
void SListDesTroy(SLN** pphead)
{
	assert(pphead && *pphead);
	SLN* ptr = *pphead;
	while (ptr)
	{
		SLN* next1 = ptr->next;
		free(ptr);
		ptr = next1;
	}
	*pphead = NULL;
}

展示测试文件的信息

#include"SListNode.h"

//测试1
//void test01()
//{
//	//向链表中添加数据
//	SLN* node1 = (SLN*)malloc(sizeof(SListtype));
//	node1->date = 1;
//	SLN* node2 = (SLN*)malloc(sizeof(SListtype));
//	node2->date = 2;
//	SLN* node3 = (SLN*)malloc(sizeof(SListtype));
//	node3->date = 3;
//	SLN* node4 = (SLN*)malloc(sizeof(SListtype));
//	node4->date = 4;
//
//	node1->next = node2;
//	node2->next = node3;
//	node3->next = node4;
//	node4->next = NULL;
//	int* phead = node1;
//	SLNprint(phead);
//}

//测试二
void test02()
{
	SLN* node1 = NULL;//给第一个元素初始化
	SLNpushBack(&node1,1);//形参不会影响实参所以传地址进去
	SLNprint(node1);
	SLNpushBack(&node1, 2);
	SLNprint(node1);
	SLNpushBack(&node1, 3);
	SLNprint(node1);
	SLNpushBack(&node1, 4);
	SLNprint(node1);
	SLNpushBack(&node1, 5);
	SLNprint(node1);
	SLNpushFront(&node1, 0);
	SLNprint(node1);
	SLNpopBack(&node1);
	SLNprint(node1);
	SLNpopFront(&node1);
	SLNprint(node1);
	int *p=SLNfind(node1, 3);//*(***************************
	//SLNpushsrand(&node1, p, 110);
	//SLNprint(node1);
	//SLTInsertAfter(p, 190);
	//SLNprint(node1);
	//SLNpopFront(&node1);
	//SLNprint(node1);
	// 
	//SLTErase(&node1, p);
	//SLNprint(node1);
	//SLNpopBack(&node1);
	//SLNprint(node1);
	SLTEraseAfter(p);
	SLNprint(node1);
	//销毁空间
	SListDesTroy(&node1);
}
int main()
{
	//test01();
	test02();
	return 0;
}

还有双向链表的实现（双向，循环，有头）

.h文件

#pragma once

//包含能用到的头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//类型不确定
typedef int SLNtype;

//定义双向链表的结构体类型
typedef struct SListNode
{
	SLNtype date;
	struct SListNode* next;//后节点
	struct SListNode* patil;//前节点
	
}SLN;

//双向链表的初始化
void SLNIint(SLN**pphead);

//双向链表的尾插
void SLNpushback(SLN*phead,SLNtype x);

//双向链表的头插
void SLNpushFront(SLN* phead, SLNtype x);

//双向链表的打印
void SLNprint(SLN* phead);

//双向链表的尾删
void SLNpopback(SLN*phead);

//双向链表的头删
void SLNpopFront(SLN* phead);

//这里要先找到pop位置进行插入
//所以要先先写一个查找函数
//双向链表的查找
SLN* Find(SLN* phead, SLNtype x);

//双向链表在指定位置之后插入数据
void SLNpushsrandb(SLN* phead,SLN *pop,SLNtype x);

//双向链表指定位置之前插入数据
void SLNpushsrandf(SLN* phead, SLN* pop, SLNtype x);

//双线链表指定位置删除
void SLNpopsrand(SLN* pop);

//双向链表的销毁
void SLNdestory(SLN**phead);

.c文件

#include "SListNode.h"

//空间的申请
SLN* Space(SLNtype x)
{
	SLN* ptr = (SLN*)malloc(sizeof(SLN));
	if (ptr == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	//成功
	ptr->date = x;
	return ptr;
}

//双向链表的初始化
void SLNIint(SLN** pphead)
{
	*pphead = Space(-1);
	SLN* str = *pphead;
	str->next = str->patil = str;//先让双项链表指向自己
	printf("初始化成功\n");
}

//双向链表的尾插
void SLNpushback(SLN* phead, SLNtype x)
{
	assert(phead);
	//要进行空间的申请在初始化的时候，尾插，头插都需要要直接分装成函数
	SLN* newptr = Space(x);
	phead->next = newptr;
	newptr->patil = phead;
	phead->patil = newptr;
	newptr->next = phead;
}

//双向链表的头插
void SLNpushFront(SLN* phead, SLNtype x)
{
	assert(phead);
	SLN* ptr = Space(x);
	ptr->next = phead->next;
	ptr->patil = phead;
	ptr->next->patil = ptr;
	phead->next = ptr;
}

//双向链表的打印
void SLNprint(SLN* phead)
{
	assert(phead);
	SLN* ptr = phead->next;
	while (ptr!=phead)
	{
		printf("%d->", ptr->date);
		ptr = ptr->next;
	}
	printf("NULL\n");
}

//双向链表的尾删
void SLNpopback(SLN* phead)
{
	assert(phead && phead->next);
	phead->patil->patil->next = phead;
	phead->patil = phead->patil->patil;
}

//双向链表的头删
void SLNpopFront(SLN* phead)
{
	assert(phead && phead->next);
	phead->next->next->patil = phead;
	phead->next = phead->next->next;
}

//双向链表的查找
SLN* Find(SLN* phead, SLNtype x)
{
	assert(phead);
	SLN* ptr = phead->next;
	while (ptr!=phead)
	{
		if (ptr->date == x)
		{
			printf("找到了\n");
			return ptr;
		}
		ptr = ptr->next;
	}
	//没找到
	printf("无该信息,没找到\n");
	return NULL;
}

//双向链表在指定位置之后插入数据
void SLNpushsrandb(SLN* phead, SLN* pop, SLNtype x)
{
	assert(phead && pop);
	SLN* ptr = Space(x);
	ptr->next = pop->next;
	pop->next->patil=ptr;
	pop->next = ptr;
	ptr->patil = pop;
}

//双向链表指定位置之前插入数据
void SLNpushsrandf(SLN* phead, SLN* pop, SLNtype x)
{
	assert(phead && pop);
	SLN* str = Space(x);
	str->patil = pop->patil;
	pop->patil->next = str;
	str->next = pop;
	pop->patil = str;
}

//双线链表指定位置删除
void SLNpopsrand(SLN* pop)
{
	assert(pop);
	pop->patil->next = pop->next;
	pop->next->patil = pop->patil;
}

//双向链表的销毁
void SLNdestory(SLN ** pphead)
{
	assert(pphead && *pphead);
	SLN* ptr = *pphead;
	ptr = ptr->next;
	while (ptr !=*pphead)
	{
		SLN* ptrv = ptr->next;
		free(ptr);
		ptr = ptrv;
	}
	free(*pphead);
	*pphead = NULL;
}

text文件

#include "SListNode.h"


void test01()
{
	SLN * head;
	//初始化
	SLNIint(&head);
	//尾插的测试
	SLNpushback(head,6);
	SLNprint(head);
	//头插的测试
	SLNpushFront(head, 5);
	SLNprint(head);
	SLNpushFront(head, 4);
	SLNprint(head);
	SLNpushFront(head, 3);
	SLNprint(head);
	SLNpushFront(head, 2);
	SLNprint(head);
	SLNpushFront(head, 1);
	SLNprint(head);
	//尾删的测试
	//SLNpopback(head);
	//SLNprint(head);
	//SLNpopback(head);
	//SLNprint(head);
	//SLNpopback(head);
	//SLNprint(head);
	//SLNpopback(head);
	//SLNprint(head);
	//SLNpopback(head);
	//SLNprint(head);
	//头删的测试
	//SLNpopFront(head);
	//SLNprint(head);
	//SLNpopFront(head);
	//SLNprint(head);
	//SLNpopFront(head);
	//SLNprint(head);
	//查找测试
	SLN*find=Find(head, 6);
	//指定位置pop之后
	//SLNpushsrandb(head, find, 111);
	//SLNpushsrandb(head, find, 112);
	//SLNprint(head);
	//指定位置pop之前
	//SLNpushsrandf(head, find, 112);
	//SLNprint(head);
	//SLNpushsrandf(head, find, 113);
	//SLNprint(head);
	//SLNpopsrand(find);
	//SLNprint(head);
	SLNdestory(&head);
}

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

亚马逊云科技技术品牌专区

更多推荐

open-code-review Codex 插件教程：对话式调用评审技能指南

本文是一份面向新手的 **open-code-review Codex 插件教程**，教你在 Codex 中通过对话式方式调用 open-code-review 的 AI 代码评审技能。open-code-review 是阿里巴巴开源的 AI 代码评审工具，采用"确定性流水线 + LLM Agent"混合架构，内置多语言评审规则（NPE、线程安全、XSS、SQL 注入等），可在 Codex 里用一

亚马逊云科技技术品牌专区

OBS Studio 完整指南：免费开源录屏与直播软件从零上手

想做一场像模像样的直播，或者把屏幕内容录成教程视频，但一想到商用软件的订阅费就有些犹豫？其实你不需要花一分钱。OBS Studio 是一款免费开源的直播与录屏软件，支持 Windows、macOS 和 Linux，采集、混音、编码、推流、录制，一条流水线全包了。## 先搞清楚 OBS Studio 是什么OBS Studio 是一个"场景化"的采集合成工具：你把摄像头、窗口、浏览器、图片、

亚马逊云科技技术品牌专区

如何用MediaCrawler爬取小红书抖音数据？7大平台爬虫从安装到实战完整指南

MediaCrawler 是一个支持小红书、抖音、快手、B站、微博、百度贴吧、知乎的开源自媒体数据采集工具。它能按关键词、按帖子、按创作者主页三种方式抓取笔记/视频内容、评论甚至二级评论，并把结果存成 JSON、CSV、Excel 或数据库。适合做市场调研、竞品监控、内容选题的运营人员，以及想要现成爬虫框架而不想从零写 JS 逆向的开发者。## 从一次"手动抄数据"说起想象这个场景：你负责