单链表的增删改查（数据结构）

之前我们学习了动态顺序表，今天我们来讲一讲单链表是如何进行增删改查的

一、单链表

1.1、单链表概念

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

1.2、链表与顺序表的区别：

链表不像顺序一样，空间给少了不够，给多了浪费，链表是你需要多少空间，就申请多少空间。

链表中一个结点就是一个数据，结点中必须包含两个数据，一个是我们需要存放的数据，另外一个就是下一个数据的地址。

每存放一个数据，我们就需要申请一个结点，直到最后一个结点指向的地址为NULL

淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。

在链表⾥，每节“⻋厢”是什么样的呢？

1.3、链表的打印

为什么提前讲链表是如何打印的，而不是先讲插入删除，初始化，这是因为比较好理解，这个理解的，接下来在看增删查改理解就会快了。

当pcur为头结点时，需要打印第一个结点的数据，第一个结点的数据为pcur这个结构体中的data数据，所有我们需要获取data数据进行打印。当需要打印第二个结点里data数据时候，pcur需要往前走一个结点，走到的结点是pcur结构体中存放的下一个结点的地址进行解引用，然将解引用得到的数据赋值给pcur，此时pcur就往前前进了一位。直到pcur等于NULL才停止循环。

二、增删改查

在这一部分，只写node.c中增删改查实现的函数代码，总代码可在最后进行查看。

2.1、结点的创建（结构体）

node.h

typedef int SLTDataType;     //将int类型定义为SLTDataType，方便修改数据类型

typedef struct SListNode {
	SLTDataType data;       
	struct SListNode* next;    //指向的下一个结点
}SLTNode;

struct SListNode* next;这段代码是创建一个为类型大小为struct SListNode指针的next，next指向下一个结点，为什么不是这样写struct SListNode next;  如果这样的话，每个结点都包含一个完整的 SListNode ,那么造成了巨大的空间浪费，在进行移动的时候，占用非常大的计算。

这样写struct SListNode* next; 那么在进行两个结点连接时，next可以存储另外一个结点的地址，可以快速找到下一个数据

2.2、创建头结点

test.c

int main()
{
	SLTNode* plist = NULL;   //创建头结点
    return 0;
}

为什么需要使用SLTNode* plist = NULL; 那是因为plist是一个指向SLTNode的一个指针，我们可以用这个来指向链表的头结点，并且在链表的动态中进行改变他的值。

SLTNode plist = NULL;这样写的意思是plist的类型是SLTNode并且等于NULL，这是一个极其错误的写法。

所以如果我们想要动态的使用结点，就需要创建一个头结点指向SLTNode，这样就可以使用结构体中的数据。

那为什么不这样写 SLTNode plist；然后对结构体进行初始化。那是因为，我们所创建的不是一个顺序表，我们需要记录下一个空间存入的数据与该空间的下一个结点。

2.3、尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//pphead --> &plist
	// *pphead --> plist
	//申请新节点
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾结点
		SLTNode* pcur = *pphead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		//pcur  newnode
		pcur->next = newnode;
	}
}

void SLTPushBack(SLTNode** pphead, SLTDataType x)注意这里使用了二级指针。

为什么要使用二级指针？

由于我们需要修改头指针的内容，而传递指针本质上是值传递，所以我们需要通过二级指针来直接操作头指针的地址，才能真正修改头指针的值。

在顺序表中，由于你是在固定大小的数组上操作，数组的大小和起始地址是固定的，不需要动态分配和改变，所以不需要二级指针。

在链表中，如果直接将创建的头结点的值传入函数中，那么就相当于传值调用，在程序运行完以后，栈帧也会消失，所以需要取地址进行函数调用，这样头结点内容就被修改了。

2.4、申请新结点

//申请新节点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->next = NULL;

	return node;
}

在链表中使用malloc来扩容，而非增容（realloc），当创建好一个新结点时，把数据（x）存放到新结点中的data里面，新结点指向的下一个指针next先置为空，在接下来增删改查时候再做修改。

2.5、尾插

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);                     //判断pphead是否为NULL
	//申请新节点
	SLTNode* newnode = SLTBuyNode(x);   //创建一个新结点
	if (*pphead == NULL)
	{
		*pphead = newnode;      //如果*pphead是已经初始化为NULL，那么直接将新结点等于头结点
	}
	else
	{
		//找尾结点
		SLTNode* pcur = *pphead;     //创建一个新指针等于pphead的
		while (pcur->next)           //pcur->next不等于NULL就一直运行
		{
			pcur = pcur->next;       //一直将pcur往后遍历，直到pcur->next等于NULL
		}
		pcur->next = newnode;        //将原链表pcur->next指向NULL的结点指针指向新的结点
	}
}

为什么我们不适用*pphead来遍历链表，因为我们在打印链表的时候，需要从头结点开始遍历，如果使用*pphead来遍历的话，此时*pphead就走到了链表的末尾，在打印链表的时候就无法打印，所以就需要创建一个指针等于*pphead，借助新创建的指针来进行链表的修改，当新指针走到了链表的末尾，*pphead还是在链表的头结点。

2.6、头插

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLTNode* newnode = SLTBuyNode(x);  //创建新结点
	newnode->next = *pphead;           //将新创建的头结点中指向下一个结点的指针直接指向*pphead
	*pphead = newnode;                 //将*pphead等于newnode，此时头结点还是*pphead
} 

2.7、尾删

//尾删
void SLTPopBack(SLTNode** pphead)
{
	//链表为空：不可以删除
	assert(pphead && *pphead);
	//处理只有一个结点的情况:要删除的就是头结点	
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找 prev ptail
		SLTNode* ptail = *pphead;
		SLTNode* prev = NULL;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
}

............................................

第四个图中，newtail->next = NULL，此时循环停止，将prev->next置为NULL，此时prev就是最后一个结点，接着将不需要的结点newtail中的空间给释放掉.

2.8、头删

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* next = (*pphead)->next;//记录头结点指向的下一个结点
	free(*pphead);   //释放头结点
	*pphead = next;   //将*pphead等于刚刚记录下来的结点，此时就完成了头结点的删除操作
}

2.9、查找链表中的数据

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}

当链表中存放的数据等于x时，返回pcur，否则就返回NULL

2.10、在指定位置之前插⼊数据

//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);        //查找的数据不能为空，需要是一个有效的数

	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);  如果pos等于头结点，那么直接进行头插
	}
	else
	{
		SLTNode* newnode = SLTBuyNode(x);
		//找prev :pos的前一个结点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

例如需要查找的数是pos=3，prev->next中的地址解引用得到的结果就是3，所以prev停止pos结点之前的一个结点。

将newnode->next指针指向pos，接着将prev->next指向newnode。这样就完成了链表的插入。

2.11、在指定位置之后插⼊数据

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

例如pos=2，那么图就是这这样的

2.12、删除pos结点

//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);

	//头删
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

2.13、删除pos之后的结点

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

2.14、销毁链表

//销毁链表
void SListDestroy(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;    //遍历每一个结点，将每一个结点空间进行释放
		free(pcur);
		pcur = next;                   //将释放后的结点，等于下一个结点，直到pcur=NULL
	}
	*pphead = NULL;                    //释放完全部结点以后，将*pphead也置为NULL
}

三、全部源代码

node.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义链表（结点）的结构
typedef int SLTDataType;

typedef struct SListNode {
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead);

//插入
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//删除
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, 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);
//销毁链表
void SListDestroy(SLTNode** pphead);

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "node.h"


void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);//1->2->3->4->NULL

	//SLTPushBack(NULL, 3);
	//SLTPushFront(&plist, 1);
	//SLTPushFront(&plist, 2);
	//SLTPushFront(&plist, 3);
	//SLTPushFront(&plist, 4);
	//SLTPrint(plist); //4->3->2->1->NULL

	//SLTPopBack(&plist);
	//SLTPrint(plist);
	//SLTPopBack(&plist);
	//SLTPrint(plist);
	//SLTPopBack(&plist);
	//SLTPrint(plist);
	//SLTPopBack(&plist);
	//SLTPrint(plist);
	//SLTPopBack(&plist);
	//SLTPrint(plist);
	//
	//SLTPopFront(&plist);
	//SLTPrint(plist);
	//SLTPopFront(&plist);
	//SLTPrint(plist);
	//SLTPopFront(&plist);
	//SLTPrint(plist);
	//SLTPopFront(&plist);
	//SLTPrint(plist);
	//SLTPopFront(&plist);
	//SLTPrint(plist);

	//SLTNode* find = SLTFind(plist, 4);
	//if (find == NULL)
	//{
	//	printf("未找到！\n");
	//}
	//else
	//{
	//	printf("找到了！\n");
	//}
	//SLTInsert(&plist, find, 11);//4->3->2->11->1->NULL
	//SLTInsertAfter(find, 11);
	//SLTPrint(plist);1->11->2->3->4->NULL

	//SLTErase(&plist, find);// 1->2->3->NULL
	//SLTEraseAfter(find);

	//SLTPrint(plist);
	SListDestroy(&plist);
	SLTPrint(plist);
}

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

node.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "node.h"

void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

//申请新节点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->next = NULL;

	return node;
}

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//pphead --> &plist
	// *pphead --> plist
	//申请新节点
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾结点
		SLTNode* pcur = *pphead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		//pcur  newnode
		pcur->next = newnode;
	}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLTNode* newnode = SLTBuyNode(x);
	//newnode *pphead
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
	//链表为空：不可以删除
	assert(pphead && *pphead);
	//处理只有一个结点的情况:要删除的就是头结点	
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找 prev ptail
		SLTNode* ptail = *pphead;
		SLTNode* prev = NULL;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
}
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* next = (*pphead)->next;
	//*pphead --> next
	free(*pphead);
	*pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = SLTBuyNode(x);
		//找prev :pos的前一个结点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//prev newnode --> pos
		newnode->next = pos;
		prev->next = newnode;
	}
}
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	//pos newnode --> pos->next
	newnode->next = pos->next;
	pos->next = newnode;
}
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);

	//头删
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//prev pos pos->next
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);

	//pos pos->next pos->next->next
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}
//销毁链表
void SListDestroy(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}