数据结构：单链表详解

1.单链表的介绍

2.单链表的使用

（1）结点的头/尾部的插入和删除

（2）对特定结点的查找

（3）在指定位置之前/后插入和删除数据

（4）销毁链表

3.链表与顺序表的对比

我以过客之名，祝你前程似锦

一.单链表

1.概念与结构：

概念：链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，就像一节火车，结点是他的车厢

而在具体的编程中，链表的形式实际上是这个样子：

链表由结点组成，而结点由存储的数据和指向下一个节点的指针组成

链表中每个结点都是独⽴申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针 变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点

2.链表的性质：

struct SListNode
{
 int data; //结点数据
 struct SListNode* next; //指针变量⽤保存下⼀个结点的地址
}SLTNode;

当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数 据，也需要保存下⼀个结点的地址（当下⼀个结点为空时保存的地址为空） 当我们想要从第⼀个结点到最后⼀个结点时，只要在当前结点拿上下⼀个结点的地址就可以了

3.链表的初始化和打印：

//text.c文件
#include"SLlist.h"
void text01()
{
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));//申请一个结点大小的空间
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));

	node1->data = 1;
	node2->data = 2;
	node3->data = 3;
	node4->data = 4;                            //将结点里每一个data和next就像赋值（初始化）

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;                                  //将四个结点连接起来

	//打印链表
	SLTNode* plist = node1;
	SLTPrint(plist);
}


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

//SLlist.h文件
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

链表的打印本质上也就是通过一个循环不断地去寻找下一个结点，附上这个图应该会更好理解些：

二.单链表的使用

1.结点的尾/头部的插入和删除:

(1)尾插：

在尾插之前，首先有几点需要特别关注一下：

       第一个就是我在之前的文章里提过的对于双指针的使用：与顺序表拥有一个指针就可以按顺序遍历，修改这块存储在连续物理空间上的数据相比，而链表却是通过结点之间的链接来存储数据，作为包含数据部分和指向下一个结点的指针的结点，要想要修改链表的结点，就不得不对新节点的地址进行修改，也就是指针的指针，即二级指针。

       第二个就是无论是链表也好顺序表也罢，在添加修改数据就避免不了对空间的申请，而这个申请操作却不是百分百成功的，因此就必须要进行对申请空间失败的验证操作

       第三个就是我认为链表最巧妙（也是最不容易理解）的地方就是两个结点之间的联系：

我这里画图详细说一下

//向操作系统申请一个新结点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc failed!");
		exit(1);
	}//防止结点空间申请失败

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)//注意这里的二级指针
{

	SLTNode* newnode = SLTBuyNode(x);
	//当链表为空，phead直接指向newnode结点
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//当链表不为空，要先找到最后一个结点（尾结点）的next指针，与新结点链接起来
		SLTNode* ptail = *pphead;//创建一个临时变量ptail用来作为循环的开头
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;//将原链表的最后一个结点的next指向我们要插入的结点
	}

尾插的时候也要注意两种情况：因为我们并不知道将要插入的链表就是是一个有效链表还是一个空链表，因此就不得不分类讨论，即空链表就将插入的新节点作为链表的第一个结点，当是一个有效链表就遍历链表至最后一个结点然后修改它最后一个结点的next指针，使其指向我们的新节点

(2)尾删：

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* p1 = *pphead;
	SLTNode* p2 = *pphead;
	if ((*pphead)->next == NULL)//->的优先级要比*高，所以这里要多加一个括号
	{
		free(*pphead);
		*pphead = NULL;
	}//判断*pphead的next传的是空结点（如果是就证明这个链表只有一个结点，所以直接释放就行）
	while (p1->next)
	{
		//当p1的next指向的下一个不是NULL时（即没到最后一个结点时）使p2始终跟着p1走，且p2一直在p1前一个
		p2 = p1;
		p1 = p1->next;
	}
	//当程序走到这里时就证明p1已经是最后一个结点了，也就是我们将要删掉的那个结点
	p2->next = NULL;//先将p2与p1断开
	free(p1);
	p1 = NULL;//再对p1进行释放，然后置空

}

这里值得具体关注的有两点，一是我为什么要将多结点的尾删和单结点的尾删分开讨论：单结点的话就不需要区分p1抑或p2，直接释放然后置空就行，而区分p1，p2的主要原因就是尾结点的next必须指向NULL，这也是我想强调的第二点

(3)头插：

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);//创建一个新结点
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* phead = *pphead;
		newnode->next = phead;
		phead = newnode;
	}
}

这里值得注意的就是最后一步的phead = newnode;这一步表示将原来的头结点指针给我们头插的新结点（修改头结点的地址），这里的newnode本身就代表SLTNode类型的指针，所以可以直接修改地址

(4)头删：

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

2.对特定结点的查找：

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
    SLTNode* pcur = phead;
	while (pcur->data != x)
	{
		pcur = pcur->next;
	}
	return pcur;
}

这里跟链表的打印时传递的变量一样，一级指针就足够了（因为不涉及对结点的增删改）

3.在指定位置之前/后插入和删除数据：

(1)指定位置之后插入数据：

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

	SLTNode* pcur = pos->next;//先创建一个临时变量pcur存储pos之后那个结点的地址
	pos->next = newnode;//再将这个地址传递给newnode（pos的next）
	newnode->next = pcur;//最后将newnode的next修改为原来pos后面的那个结点的地址
}

(2)指定位置之前插入数据：

//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (pos == *pphead)
	{
		SListPopFront(pos);
	}
	else
	{
		SLTNode* newnode = BuySListNode(x);
		SLTNode* pcur = *pphead;

		while ((pcur->next) != pos)
		{
			pcur = pcur->next;
		}
		//程序到此处时表示pcur到pos的前一个结点
		pcur->next = newnode;//先将原前一个结点的next指针指向newnode
		newnode->next = pos;//再将newnode的指针指向pos
	}
}

在指定位置之前插入与在指定位置之后插入唯一不同的就是要先验证一下是否为空链表

(3)删除指定位置的数据：

//删除指定位置（pos）数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}

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

(4)销毁链表：

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

三.链表与顺序表的对比

存储方式
‌顺序表‌：顺序表采用顺序存储，在内存中申请一块连续的空间，通过下标进行存储
‌链表‌：链表采用链式存储，每个节点通过指针相互连接，物理空间不一定连续

内存利用率
‌顺序表‌：需要预先分配固定大小的空间，可能导致空间闲置或溢出。扩容时通常以2倍关系扩增，可能造成空间浪费
‌链表‌：按需申请空间，不存在空间浪费问题，但每次插入元素前需要申请新空间

插入和删除操作的效率
‌顺序表‌：在中间位置插入或删除元素时，需要移动多个元素，效率较低。
‌链表‌：只需改变指针的指向，效率较高

随机访问能力
‌顺序表‌：支持通过下标随机访问元素，速度快。
‌链表‌：由于物理空间不连续，无法通过下标直接访问，只能顺序访问，效率较低

应用场景
‌顺序表‌：适用于需要快速访问指定位置数据的场景。‌
‌链表‌：适用于需要频繁在任意位置插入或删除元素的场景。