手撕数据结构01--单链表（附源码）

目录

1.链表的概念和结构

1.1 链表的概念

1.2 单链表结构

2.实现单链表

2.1 节点定义

2.2 链表功能

2.3 创建节点

2.4 尾插

2.5 头插

2.6 打印

2.7 尾删

2.8 头删

2.9 查找

2.10 指定位置插入

2.11 指定位置之后插入

2.12 删除pos节点

2.13 删除pos之后的节点

2.14 销毁链表

3.单链表和顺序表的对比

3.1 存储方式

3.2 插入和删除操作

3.3 空间复杂度

3.4 内存占用

1.链表的概念和结构

1.1 链表的概念

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

这里我们先引进一个小问题？如果火车的每一节车厢的钥匙形状都是不一样的，我们要到达指定车厢（每次只能携带一把钥匙），最简单的方法是每节车厢放下一把车厢的钥匙，这也是我们链表的核心思想。链表如下：

我们这里一个一个与”火车车厢“相似的我们称为节点。

1.2 单链表结构

结构：首先是一个结构体，结构体里面要有指针和被储存的数据类型。

typedef struct Node {
	int data;
	struct Node* next;
}Node;

2.实现单链表

2.1 节点定义

这里对int 和 struct SListNode 重新定义了一下方便后面使用。这里SL是单链表的缩写。

typedefint SLTDataType;//节点元素类型定义，方便修改
 
typedefstruct SListNode//单链表
{
	int data;//该节点的存储元素
	struct SListNode* next;//下一节点的地址，为了找到下一节点
}SLTNode;

2.2 链表功能

功能：尾插、头插、查找、删除等等功能。这里会一一介绍和带你画图理解。

//单链表尾插
void SLTPushBlack(SLTNode** pphead,SLTDataType x);
//单链表头插
void SLTPushFront(SLTNode** pphead,SLTDataType x);
//创建一个新的节点
SLTNode* SLTBuyNode(SLTDataType x);
//单链表的打印
void SLTPrint(SLTNode* phead);
//尾删
void SLTPopBlack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* pphead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead,SLTNode* pos,SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter( SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//为什么没有pos之前的元素删除嘞，因为pos为第一个元素时，就矛盾了
//销毁链表
void SListDesTroy(SLTNode** pphead);

2.3 创建节点

因为我们前面就提到了这个单链表是逻辑上的连续，但是物理结构上不一定连续 。所以我们就只需要开辟动态内存就可以了。我们就可以用最简洁的malloc函数。

malloc是可能会开启失败的，所以要判断一下。接着就是对节点里面的值进行赋值，其中指向下一个指针next指向NULL，防止出现野指针。

注意：为什么单链表里面没有初始化这个功能呢？因为我们只有在测试文件里面定义一个指针指向第一个有效节点就可以完成剩下的操作了。

SLTNode* SLTBuyNode(SLTDataType x)//创建一个新的节点
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);//正常情况下是exit(1)
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

2.4 尾插

思路我们要尾插：也就是在最后一个节点插入一个节点，首先要****遍历****找到最后一个节点，所以就要用到循环，循环的结束条件是什么呢！，我们观察到最后一个节点的指针指向NULL（作为循环结束条件），我们就只需要把最后一个节点的指针指向新的节点，这是大致思路。

我们来处理一下细节上的东西，我们要传一个怎么样的参数？？，一级指针？还是二级指针？

这是我们要思考的一个问题，我们要通过形参来影响实参，所以就要传地址。一级指针的地址我们要用二级指针来接收。我们还要判断一下传过来的是否为空指针，如果为空指针就不可以进行解引用操作，还有判断是不是空链表。空链表和非空链表会影响尾插的代码。

空链表：直接让空链表的指针指向新节点。

对非空链表：定义一个尾指针遍历到最后一个节点，然后进行插入。

void SLTPushBlack(SLTNode** pphead, SLTDataType x)//尾插
{
	assert(pphead);//判断这个二级指针是不是空指针
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)//为空链表
	{
		*pphead = newnode;
	}
	else//尾插链表不是空链表
	{
		SLTNode* pur = *pphead;
		while (pur->next)//pur->next!=NULL
		{
			pur = pur->next;
		}
		pur->next = newnode;
	}
}

2.5 头插

头插相比尾插简单很多，在单链表第一个有效节点前插入新节点就可以了。让节点的指针指向第一个有效节点，还要注意一下空指针，最后就是让新节点成为新的第一个有效节点！！！

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//判断这个二级指针是不是空指针
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;//让pphead指向新的起点
}

2.6 打印

通过循环来打印节点内容，注意一下循环结束条件和遍历指针的移动，这个打印还是很简单的。

void SLTPrint(SLTNode* pphead)//打印单链表
{
	SLTNode* pur = pphead;//防止原指针被修改
	while (pur)//pur!=NULL
	{
		printf("%d->", pur->data);
		pur = pur->next;
	}
	printf("NULL\n");
}

2.7 尾删

凡是遇到要进行数据修改的都要传地址，所以我们这里需要很多二级指针。

思路：我们是进行尾删操作，首先我们要找到最后一个节点，就需要进行遍历。因为我们是通过malloc函数开辟空间，所以我们需要释放空间就要用到free函数。再把倒数第二个节点的指针指向空指针。我们再来检查一下会不会传一个空指针或者空链表呢！！不可以对空指针进行解引用，需要断言assert（pphead && *pphead），这里很多人会理解不了，看看下面的图会有助于理解。

我们还要考虑有几个节点来进行分类，如果只要一个节点的话执行到     

free(prev);
prev = NULL;
ptail->next = NULL;

这时就是非法访问了，因为我们前面就已经释放了空间。所以一个节点要单独处理。

//尾删
void SLTPopBlack(SLTNode** pphead)
{
	assert(pphead && *pphead);//判断这个二级指针是不是空指针和是否传了一个空链表
	//只有一个节点
	if ((*pphead)->next == NULL)// -> 的优先级高于 *
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//有多个节点
	{
		SLTNode* prev = *pphead;//用来找到最后一个节点
		SLTNode* ptail = *pphead;//用来修改最后一个节点
		while (prev->next)
		{
			ptail = prev;
			prev = prev->next;
		}
		free(prev);
		prev = NULL;
		ptail->next = NULL;
	}
}

2.8 头删

头删相比尾删简单很多，把第二个节点储存起来然后释放了第一个节点就可以了。

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* ptail = (*pphead)->next;
	free(*pphead);
	*pphead = NULL;
	*pphead = ptail;
}

2.9 查找

通过遍历链表来找到被查询的值。

//查找
SLTNode* SLTFind(SLTNode* pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* prev = pphead;
	while (prev)
	{
		if (prev->data == x)
		{
			return prev;
		}
		prev = prev->next;
	}
	//没找到
	returnNULL;
}

2.10 指定位置插入

分两种情况，在第一个节点之前插入是头插，其他地方插入作为另外一种。

先通过遍历链表找到pos的上一个节点，然后把上一个节点的指针指向新创建的节点，新创建的节点指针指向pos节点。接下来还是老样子判断空指针和空链表。

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	SLTNode* prev = *pphead;
	if (prev == pos)//在第一个节点之前插入
	{
		//头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = SLTBuyNode(x);
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}

2.11 指定位置之后插入

把新创建的节点指针指向pos的下一个节点，这里不需要遍历，因为pos储存了下一个节点的地址，最后再把pos的指针指向新创建的指针。

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

2.12 删除pos节点

通过遍历链表找到pos的上一个节点，因为删除pos节点会影响pos前的节点和pos后面的节点，所以要先让pos之前一个的指针指向pos后一个指针，再来释放掉pos节点。

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

2.13 删除pos之后的节点

这里我们影响到了pos，pos->next，pos->next->next这三个指针，我们通过pos指向pos->next->next。这样我们就找不到了pos->next，所以需要找中间一个指针来存储pos->next，来进行以上操作，这样就不会丢失了。

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

2.14 销毁链表

因为会形参会影响到实参所以还是二级指针，遍历链表一个一个节点释放空间。

//单链表的销毁
void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* prev = *pphead;
	while (prev)
	{
		SLTNode* ptail = prev->next;
		free(prev);
		prev = ptail;
	}
	*pphead = NULL;
}

3.单链表和顺序表的对比

单链表和顺序表是两种常见的数据结构，它们在内部组织数据的方式上有很大的不同。

3.1 存储方式

顺序表: 使用一段连续的存储空间来存储数据，可以通过数组来实现。因此可以直接通过下标来访问元素，查找速度快。

单链表: 使用节点来存储数据，每个节点包含数据和指向下一个节点的指针。由于节点之间的关联通过指针来实现，因此在插入和删除操作上更加灵活。

3.2 插入和删除操作

顺序表: 在中间插入或删除元素时，需要移动后续元素，时间复杂度为 O(n)。而在末尾进行插入和删除操作时，时间复杂度为 O(1)。

单链表: 在中间插入或删除元素时，只需要改变节点的指针，时间复杂度为O(1)。而在末尾进行插入和删除操作时，如果没有指向尾节点的指针，则需要遍历整个链表找到尾节点，时间复杂度为 O(n)。

3.3 空间复杂度

顺序表: 静态分配时需要预先确定大小，可能会造成空间浪费；动态扩展时需要重新分配内存，可能会导致数据复制。

单链表: 动态分配内存，可以根据需要灵活调整大小，不会出现空间浪费。

3.4 内存占用

顺序表: 由于需要一段连续的内存空间，可能会受到内存碎片的影响。

单链表: 由于节点可以分散存储在内存中，对内存碎片不敏感。

选择使用哪种数据结构取决于具体的应用场景和对数据操作的需求。如果需要频繁的插入和删除操作，单链表可能更适合；如果对随机访问的效率要求较高，顺序表可能更适合。