🔥引言

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

🌈个人主页：是店小二呀
🌈C语言笔记专栏：C语言笔记
🌈C++笔记专栏： C++笔记
🌈初阶数据结构笔记专栏： 初阶数据结构笔记

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

一、链表的概念

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

二、链表的分类

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

1.无头单向非循环链表

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

2.带头双向循环链表

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

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

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

【注意】:

1. 从图上可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续

2. 现实中的节点一般都是从堆上申请出来的

3. 从堆上申请的空间。是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

四、实现无头单向非循环链表的相关接口(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)	只需修改指针指向
插入	动态顺序表，空间不够时需要 扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低

不管是哪一种数据结构都有他的优点和缺点，对此在使用数据结构中应该知道它的优缺点是什么，加以合理地利用解决实际中的问题。

---

以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二初阶数据结构笔记，希望对你在学习初阶数据结构中有所帮助！