正经夜光杯

这个屌丝很懒，什么也没留下！

热门标签

【数据结构和算法】5.超详解析，带你手撕单向链表（图文解析，附带源码）

作者：正经夜光杯 | 2024-07-29 09:47:14

踩

欢迎来sobercq的博客喔，本期系列为【数据结构和算法】5.超详解析，带你手撕单向链表（图文解析，附带源码），带大家理解单向链表在内存中的分布，以及链表的实现，最后还会有源码分享，感谢观看，支持的可以给个赞哇。

前言

在上一篇我们知道了线性表中顺序表的问题，本期我们将讨论线性表的另一种结构，链表，由于它不要求像顺序表一样开辟连续的物理空间，并且要求逻辑上相邻的元素在物理位置上也顺序存储，也因此链表不需要移动大量的数据，但同时也失去了随机下标访问的优势。

一、链表的概念及结构

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

结构：

对链表中的数据元素来说，除了存储其本身的信息外，还需存储一个指示其后继的信息（地址），这两部分信息组成数据元素的存储映像，称为节点或者结点。它在内存中有两个域，其中存储数据元素本身的信息的域叫做数据域，存储后继位置地址的域称为指针域。指针域中存储的信息就叫做指针或链。n个结点链结成链表，因为链表中的每个结点只包含一个指针域，故又称为线性链表或者单链表。

二、单向链表的结构

定义链表结构，我们使用一个头指针phead指向链表的起始位置，在一个结点中的指针域，也就是next，让其指向下一个结点的起始位置，在单向链表的末端，也就是最后一个结点，让它的next指向NULL，这样一个单向链表的结构定义就完成了。

链表的结构如下图所示：


typedef int SLNDataType;
 
typedef struct SListNode
{
	SLNDataType val;
	struct SListNode* next;
}SLNode;

单向链表的存取必须从头指针开始进行（头指针指示链表中的第一个结点的存储位置）同时，最后一个结点的指针为“空”（NULL）（因为最后一个数据元素没有直接后继）。

三、单向链表功能实现

(1).单向链表的打印

在打印单向链表，我们通过指针next来找到下一个结点，然后打印这一个结点的值。但是注意一点，我们是不碰原先链表中的next的，所以在寻找链表的时候，需要定义一个指针cur来遍历链表，当cur指向到链表末尾的时候，这时候cur为NULL，也就意味着指针遍历结束。

单向链表逻辑结构上的打印：（逻辑结构和物理结构看第五大点）


//打印单向链表
void SLTPrint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
}

(2).单向链表的尾插

为了插入数据元素x，我们首先要找到单向链表的“尾巴”，其次要开辟一个结点，其数据为x，然后插入单向链表中。并且要修改原先单向链表上一个结点的指针，使其指向新开辟出来的val为x的结点，让val为x的结点的指针next为"空"（NULL），这样就完成了尾插的操作。

找单向链表的尾巴：

我们定义一个tail来存储头部指针phead，接着去遍历单向链表。

找尾中可能出现的问题

请看下列两个代码，并思考有何区别？


	SLNode* tail = phead;
	//找尾
	while (tail->next != NULL)
	{
		tail = tail->next;
	}


	SLNode* tail = phead;
	//找尾
	while (tail != NULL)
	{
		tail = tail->next;
	}

在找尾部的时候，我们需要判断的是tail->next后的指针是否为空指针，在第二个代码中，其找尾部的最后结果通常是把NULL赋值给tail，而不是我们想要的把新创建的结点地址给到tail。因此需要提前判断tail的下一个结点是否为空指针。

逻辑结构如下图所示：

创建新的结点：

我们用newnode来表示新结点，注意newnode不能在尾插当中直接创建（因为是局部变量的关系，局部变量出了作用域就销毁了），在函数外，我们创建一个新函数，并且通过创建内存空间来创建一个新结点。


//创建一个新结点
SLNode* CreateNode(SLNDataType x)
{
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
 
	newNode->val = x;
	newNode->next = NULL;
	return newNode;
}

插入结点：


//尾插
void SLTPushBack(SLNode* phead, SLNDataType x)
{
	//找尾
	SLNode* tail = phead;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
	//创建新结点
	SLNode* newnode = CreateNode(x);
	//插入结点
	tail->next = newnode;
}

如果链表开始为空怎么办？

我们需要先判断链表的状态，那么单向链表为空的时候，其实就是phead为空。


//判断链表是否为空
	if (phead == NULL)
	{
		phead = newnode;
	}

最后梳理后，我们在代码中要先创建结点，然后判断链表状态，最后是插入。


//尾插
void SLTPushBack(SLNode* phead, SLNDataType x)
{
	//创建新结点
	SLNode* newnode = CreateNode(x);
	//判断链表是否为空
	if (phead == NULL)
	{
		phead = newnode;
	}
	else
	{
		//找尾
		SLNode* tail = phead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//插入结点
		tail->next = newnode;
	}
}

尾插测试


int main()
{
	SLNode* plist = NULL;
 
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
 
	SLTPrint(plist);
 
	return 0;
}

我们在测试的时候发现问题，屏幕居然什么也没打印，回顾后发现，其实也就是当我传plist的时候，本意是想通过phead操作plist，但我们只拷贝了plist而并没有对plist进行操作，所以对原先一级指针phead要进行部分调整（尾插和头插的SLNode* phead就要改成SLNode** pphead）

改完后的代码如下：


int main()
{
	SLNode* plist = NULL;
 
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
 
	SLTPrint(plist);
 
	return 0;
}
 
//尾插
void SLTPushBack(SLNode** pphead, SLNDataType x)
{
	//创建新结点
	SLNode* newnode = CreateNode(x);
	//判断链表是否为空
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//插入结点
		tail->next = newnode;
	}
}
 
//头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{
	;
}
 
void SLTPushBack(SLNode** pphead, SLNDataType x);
//尾插
void SLTPushFront(SLNode** pphead, SLNDataType x);
//头插

测试效果如下图所示：

至此，尾插的功能就完成了。

(3) .单向链表的头插

为了插入数据元素x，我们首先要创建一个结点，其数据为x，然后将phead指向新结点。并且要修改结点，使其指向原先单向链表的第一个val的结点。这样就完成了头插的操作。


//头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{
	SLNode* newnode = CreateNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

头插测试


int main()
{
	SLNode* plist = NULL;
	//尾插测试
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	//头插测试
	SLTPushFront(&plist, 5);
	SLTPushFront(&plist, 6);
	SLTPushFront(&plist, 7);
	SLTPushFront(&plist, 8);
 
	SLTPrint(plist);
 
	return 0;
}

可以看到如下结果：

(4).单向链表的尾删

为在单向链表中删除结点的时候，我们仅仅只需要修改上一个结点的指针域即可，而不需要对数据进行操作。尾删仍然需要找到尾巴，并且要判断链表是否只有一个结点。

我们要对一个结点和多个结点的情况分类讨论。当我们只有一个结点的时候。在采取同样对多节点的时候会导致prev的指向。在删除的时候，我们还是需要对指针进行检查。

这里就不展开详细讲解了，代码如下所示：


void SLTPopBack(SLNode** pphead)
{
	assert(*pphead);
	
	//找尾
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* prev = NULL;
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
 
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

尾删的另外一种写法，我们知道tail用来表示一结点的起始位置，其中的next是下一个结点，而我们在这个前面的代码中，要找到tail的上一个结点，也就是要间隔一个结点判断是否为链表末端所以可以用如下代码：


void SLTPopBack(SLNode** pphead)
{
	assert(*pphead);
 
	SLNode* tail = *pphead;
	while (tail->next->next != NULL)
	{
		tail = tail->next;
	}
 
	free(tail->next);
	tail->next = NULL;
}

结果如下所示：

(5).单向链表的头删

在单向链表中删除结点的时候，从头部开始，我们需要修改下一个结点的指针域，让其赋值给pphead，这样就完成了头删的操作。

plist是我们传入的指针，*pphead是plist的二级指针。

操作过程逻辑结构如下图所示：

对第一个结点free了，然后让*pphead指向下一个结点。


void SLTPopFront(SLNode** pphead)
{
	assert(*pphead);
 
	SLNode* tmp = (*pphead)->next;
	free(*pphead);
	*pphead = tmp;
}

删除测试


//删除测试
void Test2()
{
	SLNode* plist = NULL;
	//尾部插入四个数据
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	//尾删测试
	SLTPopBack(&plist);
	SLTPrint(plist);
	//尾删测试
	SLTPopBack(&plist);
	SLTPrint(plist);
	//头删测试
	SLTPopFront(&plist);
	SLTPrint(plist);
}

结果如下图所示：

(6).单向链表的查找

用cur指针遍历链表，比对每个结点的值，如果值相等，则返回cur，如果cur遍历到NULL，也就是链表末尾，则返回NULL


//链表查找
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{
	SLNode* cur = phead;
	while (cur)
	{
		if (cur->val == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	
	return NULL;
}

查找测试


//查找测试
void Test3()
{
	SLNode* plist = NULL;
	//尾部插入一个数据
	SLTPushBack(&plist, 1);
	
	if (SLTFind(plist, 3))
		printf("找到了");
	else
		printf("找不到");
 
	if (SLTFind(plist, 1))
		printf("找到了");
	else
		printf("找不到");
 
}

结果如下图所示：

(7). 在pos位置之前插入一个结点

对pos的位置进行讨论，我们发现pos位置有三种情况，一中是头结点，一种是中间结点，还有一种是尾结点。

在插入前需要对指针进行检查，assert也有几种情况

一种是对三个都检查一遍

   assert(pphead);//有必要断言，防止乱传
   assert(*pphead);//可以不断言
   assert(pos);

另外一种是

    //宽松的条件
   //pos 和 *pphead 要么都是空要么都不是
   assert((!pos && !(*pphead))||(pos && *pphead));

第一种断言主要是针对pos，严格限制pos一定是链表里的一个有效节点，第二种就会稍微宽松点。

为pos的位置进行讨论后发现中间结点和尾结点都一样，所以将头结点和后面的两种情况进行探讨。

假设pos指向头结点

针对头结点或者是开始链表为空的情况，发现pos和pphead指向的都是第一个结点，所以条件为二者相等的情况。即pphead == pos 这种情况同样也能解决二者都为空的情况，这样使用头插就能解决

假设pos指向中间结点或者尾结点

我们需要找到pos的上一个结点（这是单向链表的缺陷）然后让上一个prev结点指向下一个新结点，下一个结点指向pos结点。


//在pos之前插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
	//限制pos一定是链表里的一个有效节点
	assert(pphead);//有必要断言，防止乱传
	//assert(*pphead);//可以不断言
	//assert(pos);
 
	//宽松的条件
	//pos 和 *pphead 要么都是空要么都不是
	assert((!pos && !(*pphead))||(pos && *pphead));
	
	//头插
	if (*pphead == pos)//也能解决两个都为空的情况
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		//找前一个结点位置
		SLNode* prev = *pphead;
		SLNode* newnode = CreateNode(x);
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//插入
		prev->next = newnode;
		newnode->next = pos;
	}
}

插入测试


//插入测试
void Test4()
{
	SLNode* plist = NULL;
	//第一种情况，plist和pos都为空
	SLTInsert(&plist,NULL,3);
	//尾部插入四个数据
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
 
	SLNode* pos = SLTFind(plist, 4);
	SLTInsert(&plist, pos, 40);
 
	//报错测试
	//pos = SLTFind(plist, 400);
	//SLTInsert(&plist, pos, 40);
 
	//打印
	SLTPrint(plist);
}

结果如下图所示

(8).删除pos结点

删除pos结点还是得分情况，一种是只有一个结点，一种是多个结点，因为当只有一个结点的时候，prev其实会走到空。


//删除pos结点
void SLTErase(SLNode** pphead, SLNode* pos)
{
	//针对pphead是每个都要检查的
	assert(pphead);
	assert(*pphead);
	assert(pos);
 
	//删除pos结点仍然需要找到pos的前一个位置
	if (*pphead == pos)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
 
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

(9). 在pos位置后插入

在pos位置后插入删除，修改pos位置的指针即可，跟plist没什么关系，不需要修改plist

在这里需要先让newnode指向下一个结点，然后再让pos指向新节点。


//在pos位置后插入
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{
	assert(pos);
	SLNode* newnode = CreateNode(x);
 
	newnode->next = pos->next;
	pos->next = newnode;
}

(10).在pos位置后删除

删除pos后的位置，用一个游标cur保存一下也可以

但是这里存在空指针的情况，有可能pos->next为空指针，也有可能pos->next->next为空。所以还是需要对pos->next进行相对应的检查。


//删除在pos位置后
void SLTEraseAfter(SLNode* pos)
{
	assert(pos);
 
	SLNode* cur = pos->next;
	pos->next = pos->next->next;
 
	free(cur);
	cur = NULL;
}

在pos位置后的插入和删除测试


void Test6()
{
	SLNode* plist = NULL;
	//尾部插入四个数据
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
 
	//在pos后插入
	SLNode* pos = SLTFind(plist, 2);
	SLTInsertAfter(pos,5);
 
	SLTPrint(plist);
 
	//在pos后插入
	pos = SLTFind(plist, 5);
	SLTInsertAfter(pos, 6);
 
	SLTPrint(plist);
 
	//在pos后删除
	pos = SLTFind(plist, 2);
	SLTEraseAfter(pos);
 
	pos = SLTFind(plist, 3);
	SLTEraseAfter(pos);
 
	//报错测试
	/*pos = SLTFind(plist, 3);
	SLTEraseAfter(pos);*/
 
	SLTPrint(plist);
}

结果如下图所示：

(11).链表的销毁

链表的销毁，用游标遍历链表，然后不断释放空间，最后将这个头指针置空。

那在这里要注意保存地址。


//销毁
void SLTDestroy(SLNode** pphead)
{
	assert(pphead);
 
	SLNode* cur = *pphead;
	while (cur)
	{
		SLNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
 
	*pphead = NULL;
}

(12).完善代码，进行补全断言的操作

不详细展开了，把pphead的断言补上，包括一些其他的断言检查补全就好了。

四、物理结构和逻辑结构

在涉及到单向链表的打印的时候，我们看到链表打印的逻辑结构如下图所示：

那什么是逻辑结构？

就是我们把链表画成用箭头相链接的结点的序列，结点之间用箭头表示链域中的指针。

为什么用逻辑结构表示链表？

这是因为我们在使用链表的时候，关心的只是它所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置。

那链表的物理结构是什么样子的呢？

链表的物理结构如下图所示：

实际上是每个指针都有一个地址，然后内存空间也有一个结点地址，指针先去找结点地址，通过结点中的指针而找到下一个结点。

五、总结以及单向链表的源码分享

断言：这个值不能为空就断言

单向链表的优劣性

优势：

不需要移动大量的数据

劣势：

失去了随机下标访问的优势。

单向链表的尾插尾删效率不好

单向链表在某些功能上如果要找到上一个结点的画，需要用到另外一个指针，降低效率。

那代码的话仍然是分为三个文件，SList.h，SList.c，test.c

SList.h的代码如下：


#pragma once
 
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int SLNDataType;
 
typedef struct SListNode
{
	SLNDataType val;
	struct SListNode* next;
}SLNode;
 
void SLTPrint(SLNode* phead);
void SLTPushBack(SLNode** pphead, SLNDataType x);
void SLTPushFront(SLNode** pphead, SLNDataType x);
void SLTPopBack(SLNode** pphead);
void SLTPopFront(SLNode** pphead);
SLNode* SLTFind(SLNode* phead, SLNDataType x);
void SLTInsert(SLNode**pphead,SLNode* pos, SLNDataType x);
void SLTInsertAfter(SLNode* pos, SLNDataType x);
void SLTErase(SLNode** pphead, SLNode* pos);
void SLTEraseAfter(SLNode* pos);
void SLTDestroy(SLNode** pphead);

SList.c的代码如下：


#include"SList.h"
 
void SLTPrint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("\n");
}
 
SLNode* CreateNode(SLNDataType x)
{
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
 
	newNode->val = x;
	newNode->next = NULL;
 
	return newNode;
}
 
void SLTPushBack(SLNode** pphead, SLNDataType x)
{
	assert(pphead);
 
	SLNode* newnode = CreateNode(x);
 
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
 
void SLTPushFront(SLNode** pphead, SLNDataType x)
{
	assert(pphead);
 
	SLNode* newnode = CreateNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
 
void SLTPopBack(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
 
	SLNode* tail = *pphead;
	while (tail->next->next != NULL)
	{
		tail = tail->next;
	}
	free(tail->next);
	tail->next = NULL;
}
 
void SLTPopFront(SLNode** pphead)
{
	assert(*pphead);
 
	SLNode* tmp = (*pphead)->next;
	free(*pphead);
	*pphead = tmp;
}
 
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{
	SLNode* cur = phead;
	while (cur)
	{
		if (cur->val == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	
	return NULL;
}
 
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
 
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLNode* prev = *pphead;
		SLNode* newnode = CreateNode(x);
		while (prev->next != pos)
		{
			prev = prev->next;
		}
 
		prev->next = newnode;
		newnode->next = pos;
	}
}
 
void SLTErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
 
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
 
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
 
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{
	assert(pos);
	SLNode* newnode = CreateNode(x);
 
	newnode->next = pos->next;
	pos->next = newnode;
}
 
void SLTEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);
 
	SLNode* cur = pos->next;
	pos->next = pos->next->next;
 
	free(cur);
	cur = NULL;
}
 
void SLTDestroy(SLNode** pphead)
{
	assert(pphead);
 
	SLNode* cur = *pphead;
	while (cur)
	{
		SLNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
 
	*pphead = NULL;
}

test.c的代码如下：


#include"SList.h"
 
//插入测试
void Test1()
{
	SLNode* plist = NULL;
	//尾插测试
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	//头插测试
	SLTPushFront(&plist, 5);
	SLTPushFront(&plist, 6);
	SLTPushFront(&plist, 7);
	SLTPushFront(&plist, 8);
	//打印
	SLTPrint(plist);
}
 
//删除测试
void Test2()
{
	SLNode* plist = NULL;
	//尾部插入四个数据
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	//尾删测试
	SLTPopBack(&plist);
	SLTPrint(plist);
	//尾删测试
	SLTPopBack(&plist);
	SLTPrint(plist);
	//头删测试
	SLTPopFront(&plist);
	SLTPrint(plist);
}
 
//查找测试
void Test3()
{
	SLNode* plist = NULL;
	//尾部插入一个数据
	SLTPushBack(&plist, 1);
	
	if (SLTFind(plist, 3))
		printf("找到了");
	else
		printf("找不到");
 
	if (SLTFind(plist, 1))
		printf("找到了");
	else
		printf("找不到");
}
 
//插入测试
void Test4()
{
	SLNode* plist = NULL;
	//第一种情况，plist和pos都为空
	SLTInsert(&plist,NULL,3);
	//尾部插入四个数据
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
 
	SLNode* pos = SLTFind(plist, 4);
	SLTInsert(&plist, pos, 40);
 
	//报错测试
	//pos = SLTFind(plist, 400);
	//SLTInsert(&plist, pos, 40);
 
	//打印
	SLTPrint(plist);
}
 
//删除测试
void Test5()
{
	SLNode* plist = NULL;
	//尾部插入四个数据
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	
	SLNode* pos = SLTFind(plist, 3);
	SLTErase(&plist, pos);
 
	pos = SLTFind(plist, 1);
	SLTErase(&plist, pos);
 
	pos = SLTFind(plist, 4);
	SLTErase(&plist, pos);
	//打印
	SLTPrint(plist);
}
 
void Test6()
{
	SLNode* plist = NULL;
	//尾部插入四个数据
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
 
	//在pos后插入
	SLNode* pos = SLTFind(plist, 2);
	SLTInsertAfter(pos,5);
 
	SLTPrint(plist);
 
	//在pos后插入
	pos = SLTFind(plist, 5);
	SLTInsertAfter(pos, 6);
 
	SLTPrint(plist);
 
	//在pos后删除
	pos = SLTFind(plist, 2);
	SLTEraseAfter(pos);
 
	pos = SLTFind(plist, 3);
	SLTEraseAfter(pos);
 
	//报错测试
	/*pos = SLTFind(plist, 3);
	SLTEraseAfter(pos);*/
 
    //销毁测试
	SLTDestroy(&plist);
 
	SLTPrint(plist);
}
 
int main()
{
	//Test1();
	//Test2();
	//Test3();
	//Test4();
	//Test5();
	Test6();
 
	return 0;
}

感谢各位同伴的支持，本期单链表讲解就结束啦，在文章的末尾有源代码分享，有需要的小伙伴可自取哈。

下期预告：【数据结构与算法】第六篇双向链表

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/正经夜光杯/article/detail/898225

【数据结构和算法】5.超详解析，带你手撕单向链表（图文解析，附带源码）

一、链表的概念及结构

二、单向链表的结构

三、单向链表功能实现

(1).单向链表的打印

(2).单向链表的尾插

找单向链表的尾巴：

创建新的结点 ：

插入结点：

如果链表开始为空怎么办？

尾插测试

(3) .单向链表的头插

头插测试

(4).单向链表的尾删

(5).单向链表的头删

删除测试

(6).单向链表的查找

查找测试

(7). 在pos位置之前插入一个结点

插入测试

(8).删除pos结点

(9). 在pos位置后插入

(10).在pos位置后删除

在pos位置后的插入和删除测试

(11).链表的销毁

(12).完善代码，进行补全断言的操作

四、物理结构和逻辑结构

五、总结以及单向链表的源码分享

创建新的结点：