【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）

07-14 1333阅读

初阶数据结构	相关知识点	可以通过点击	以下链接进行学习	一起加油！
时间与空间复杂度的深度剖析	深入解析顺序表:探索底层逻辑	深入解析单链表:探索底层逻辑	深入解析带头双向循环链表:探索底层逻辑	深入解析栈:探索底层逻辑
深入解析队列:探索底层逻辑	深入解析循环队列:探索底层逻辑

🔥引言

本篇将深入解析单链表:探索底层逻辑，理解底层是如何实现并了解该接口实现的优缺点，以便于我们在编写程序灵活地使用该数据结构。

🌈个人主页：是店小二呀

🌈C语言笔记专栏：C语言笔记

🌈C++笔记专栏： C++笔记

🌈初阶数据结构笔记专栏：初阶数据结构笔记

🌈喜欢的诗句:无人扶我青云志我自踏雪至山巅

文章目录

一、链表的概念
二、链表的分类
四、实现无头单向非循环链表的相关接口(SLTlist.h)
五、知识铺垫
六、正式开始模拟实现单链表

6.1 创建链表中的节点
6.2 单链表的插入节点

6.2.1 单链表的尾插
6.2.2 单链表的头插
6.3 单链表的删除

6.3.1 单链表的尾删
6.3.2 单链表的头删
6.4 查找单链表中数据
6.5 关于单链表的任意位置插入和删除

6.5.1 单链表的pos指定前插入
6.5.2 单链表的删除pos当前结点
6.5.3 单链表的pos之后插入
6.5.4 单链表的pos之后删除
6.6 单链表的打印

七、顺序表和链表的区别

一、链表的概念

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

二、链表的分类

我们重点需要关注以下两个链表:

1.无头单向非循环链表

结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2.带头双向循环链表

结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。虽然结构复杂，但是使用代码实现，以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了

链表是通过一个个结点链接起来的数据结构，多个结点链接形成下列结构(箭头是不存在，是为了方便理解)

下列图片会简化结点间的链接过程：

【注意】:

从图上可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
现实中的节点一般都是从堆上申请出来的
从堆上申请的空间。是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

四、实现无头单向非循环链表的相关接口(SLTlist.h)

五、知识铺垫

1.实现部分接口需要通过二级指针接受实参

原因在于我们需要可以修改实参，而是实参为一级指针时(同样是传递地址)，需要使用二级指针进行接受，否则获得临时拷贝，不会影响到实参。修改实参的情况，比如一开始为空，在插入时需将头指针存储在有效结点的的地址上，需要改变实参的值

2.单链表的初始化

这里实现链表，没有必要进行初始化，初始化对于一开始就要开辟的空间有初始化的需求，表是多个节点通过地址链接在一起，那么只需要开辟新节点的时候，初始化下就行了(有哨兵位需要初始化)

3.二级指针断言

二级指针存放的是头节点的地址，头节点的地址为空，那么还有什么意义呢?

当我们有所了解链表的结构，接下来是实现链表的相关接口，比如增删查改

六、正式开始模拟实现单链表

6.1 创建链表中的节点

在插入中需要先创建一块结点空间，再通过上一个结点通过当前结点的地址指向当前结点的位置。这是因为结点是通过地址访问的，结点里面存储着下一个节点的地址，理解为当前结点(通过下一个结点地址)指向下一个结点

SLNode* CreateNode(SLNDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode==NULL)
	{
		perror("malloc fail!!!");
		 return (-1);
	}
	newnode->next = NULL;
	newnode->val = x;
	return newnode;
}

这里需要注意的是:申请到的空间交给什么类型去维护，为结点(结构体)申请空间，就需要交给结构体指针维护，同时需要注意开辟空间可能会失败，比如开辟空间多大，无法提供空间。对新结点设置了指向下一个结点为空

6.2 单链表的插入节点

插入分为三类:头插\尾插\任意位置插入(其中任意位置插入，在实现查找功能先放着)

6.2.1 单链表的尾插

void SLTPushBack(SLNode** phead,SLNDataType x)
{
	assert(phead);
	SLNode* newnode = CreateNode(x);//值已经有了,创建一个新节点
	if (*phead == NULL)//这里需要二级指针去改变了，外的头了
	{
		*phead = newnode;
	}
	else
	{
		//找尾
		SLNode* cur =*phead;//拷贝一份
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;//newnode已经搞下一次是空了	
	}	
}

这里需要注意的是:while语句cur需要到达尾，再进行尾插的操作。同时需要考虑到特殊情况，这里我们通过if判断语句对于* pphead为空的情况，将*pphead存储在第一个结点地址。

6.2.2 单链表的头插

void SLTPushFront(SLNode** pphead, SLNDataType x)
{
	assert(pphead);
	SLNode* newnode = CreateNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLNode* cur = *pphead;
		*pphead = newnode;
		newnode->next = cur;
	}
}

这里需要注意的是:将*pphead移动到新节点的位置，再 * pphead指向cur(在原来的头节点位置)。同样的需要考虑到特殊情况，这里使用if判断语句对于* pphead为空的情况，将*pphead设为存储第一个结点地址。

6.3 单链表的删除

删除分为三类：头删\尾删\任意位置删除(其中任意位置删除，在实现查找功能先放着)

提前说明:空链表无法进行删除数据，需要在删除操作之前进行断言检查assert(*pphead)

6.3.1 单链表的尾删

void SLTPopBack(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);//空的时候
	//一个节点和多个节点
	//这里不创建一个cur变量，当只有一个节点的时候，直接pphead
	SLNode* cur = *pphead;
	if (cur->next == NULL)
	{
		*pphead = NULL;
		free(cur);
		cur = NULL;
	}
	else
	{
		while (cur->next->next!= NULL)
		{
			cur = cur->next;//上一个节点
		}
		free(cur->next);
		cur->next = NULL;
	}
}

这里需要注意的是:删除需要分为两种情况存在一个节点和多个节点的处理。需要利用while循环找到删除节点的上一个节点，将上一个节点指向空，最后不要忘记free(cur->next)，释放当前节点空间。

6.3.2 单链表的头删

void SLTPopFront(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLNode* cur = *pphead;
	if (cur->next == NULL)
	{
		*pphead = NULL;
		free(cur);
		cur = NULL;
	}
	else
	{
		*pphead = cur->next;
		free(cur);
		cur = NULL;
	}
}

这里需要注意的是:删除需要分为两种情况存在一个节点和多个节点的处理。cur保存当头节点位置，*pphead移动到下一个节点的位置，再free(cur)

6.4 查找单链表中数据

SLNode* SLTFind(SLNode* pphead, SLNDataType x)
{
	SLNode* cur = pphead;
	while (cur!=NULL)
	{
		if (cur->val == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;
}

这里需要注意的是:遍历链表，找到返回当前节点，没有找到继续向下遍历

6.5 关于单链表的任意位置插入和删除

6.5.1 单链表的pos指定前插入

void SLTInsert(SLNode** pphead,SLNode *pos,SLNDataType x)//pos指定之前插入
{
	assert(pphead);
	assert(*pphead);
	if (pos == NULL)//没有节点
	{
		SLTPushFront(pphead, x);
	}
	if (*pphead == pos)//一个节点
	{
		SLTPushFront(pphead, x);
	}
	else//多个节点
	{
		SLNode* newnode = CreateNode(x);
		SLNode* cur = *pphead;
		while (cur->next != pos)//上面避免了pos等于cur
		{
			cur = cur->next;
		}
		cur->next = newnode;
		newnode->next = pos;
	}
}

这里需要注意的是:需要分为三种情况，空节点，一个节点，多个节点就行处理。空节点调用尾插或者头插都可以，一个节点(在pos前插入)那么可以调用头插

6.5.2 单链表的删除pos当前结点

void SLTEeara(SLNode** pphead, SLNode* pos)
{
	assert(pphead);//防止用户传个空指针
	assert(*pphead);
	assert(pos);
	SLNode* next = pos->next;
	SLNode* cur = *pphead;
	if (cur==pos)
	*pphead = NULL;
        free(cur);
		cur = NULL;
	else
	{
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = next;
		free(pos);
		pos = NULL;
	}
}

这里需要注意的是：分为两种情况，存在一个节点和多个节点的处理。如果使用三个变量，需要使用到的地址不会丢失，就不需要担心先后顺序问题。结点是一块块的独立空间，其链接方式也是较灵活的，这里跟上面方法是类似的。

如果不想在pos之前插入\删除，可以改动逻辑在pos之后进行插入、删除。

6.5.3 单链表的pos之后插入

void SLTInsertAfter(SLNode **pphead,SLNode* pos, SLNDataType x)
{
	assert(pphead);
	assert(*pphead);
	if (pos == NULL)//没有节点
	{
		SLTPushFront(pphead, x);
	}
	if (*pphead == pos)//一个节点
	{
		SLTPushBack(pphead, x);
	}
	else//多个节点
	{
		SLNode* newnode = CreateNode(x);
		SLNode* back = pos->next;
		newnode->next = back;
		pos->next = newnode;
	}
}

6.5.4 单链表的pos之后删除

void SLTEearaAfter(SLNode **pphead,SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	SLNode* cur = *pphead;
	SLNode* back = pos->next;
	if (cur == pos)//只有一个结点
		SLTPopBack(pphead);
	if(back->next==NULL)
	{
		free(back);
		back = NULL;
		pos->next = NULL;
	}
	else
	{
		pos->next = back->next;
		free(back);
		back = NULL;
	}
}

上面的两个接口实现过程跟SLTInsert、SLTEeara实现类似的，看看代码就能理解

在完成了单链表的核心接口，我们需要继续完善剩下的接口，使实现的单链表功能更加丰富起来。

6.6 单链表的打印

void SLTPrint(SLNode** pphead)//二级指针改变外的结构体指针类型
{
	assert(pphead);
	SLNode* cur = *pphead;
	while (cur!= NULL)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}

这里需要注意的是：当cur==NULL时，没有进去循环，需要额外打印NULL，最后不要忘记单链表的销毁

void SLTDestroy(SLNode** pphead)
{
	assert(pphead);
	SLNode* cur = *pphead;
	while (cur)
	{
		SLNode* next = cur->next;
		free(cur);
		//这里cur不要赋空，还需要使用的
		cur = next;
}
	*pphead = NULL;
}

这里需要注意的是：链表是通过多个节点链接而成的，同时也是一块块独立空间，通过cur去访问每一个空间和释放每一块空间。其中free指针跟指针变身是没有关系的，释放的是指针所指向的那一块动态空间

七、顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低 O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低