线性表之链表详解

欢迎来到我的：世界

希望作者的文章对你有所帮助，有不足的地方还请指正，大家一起学习交流 !

前言

线性表的概述

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

链表的概述

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

内容

链表的结构

链表的结构跟⽕⻋⻋厢相似，并且每节⻋厢都是独⽴存在的；
那么思考一个问题：既然每个车厢都是独立的，那怎么样把他们链接起来？
想要把每节车厢都链起来，就是依赖每节车厢之间的接口，以方便链接；
而在链表中，就需要依赖指针域来将节点都链接起来；

在现实中数据结构的链表实现：

链表节点的定义

链表一共可以分为八种类型（在后面有详解），在这里我以结构最简单的一种来介绍链表的结构：这种结构叫做：无头单向不循环链表 简称 单向链表

但是链表中的每个节点怎么定义,为什么呢？
这里我们需要运用结构体来定义节点；
原因：
1.结构体可以将不同类型的数据组合在一起，根据上述的分析：对于链表的结点，需要存储数据元素（int，float…）和下一个节点的地址；结构体的话就可以很好的将这两种不同类型的数据（数据域和指针域）封装在一起；
2.并且我们要了解：结构体可以比较方便的表示一种复杂的数据结构；而链表的结构也相对比较复杂，所以用结构体定义链表的结构在合适不过了；

//链表的实现
//单向链表的结点的定义
typedef int typeList;//将int类型重命名为typeList
typedef struct SListNode
{
    typeList data;//这样定义数据域的好处就是，可以随时更改任意类型如：char、short...
    struct SListNode* next;//定义指针域，存放下一个节点的地址，以便找到下一个节点
}SLNode;

链表的基本功能

最基础的功能 增 删 查 改

单向链表的初始化

链表开始的时候需要初始化链表，因为初始化能建立一个稳定的起始状态，就像盖房子之前需要先打好地基一样，以确保数据结构符合预期的初始性质；

//直接这样定义即可；
int main()
{
	SLNode*phead=NULL;
	return 0;
}

链表的插入操作

对于单向链表，插入操作可以分为四种：头插,尾插,在查找到的位置之后插入,在查找到的位置之前插入
在这里我先介绍：头插,尾插，其余在后续有介绍

头插操作

头插概述：就是将一个新节点插入到单向链表的头部，使得新节点成为链表的新头部。

• 头插操作是将新节点插入到链表的头部。在单链表中，头节点（ phead ）是访问链表的入口。
• 头插操作需要改变头节点 phead 的指向。新插入的节点将成为新的头节点，原来的头节点将成为新节点的下一个节点。

询问：若将头插操作封装成一个函数，请问怎么传参呢？

• 由于C语言函数参数是值传递，如果只传递一级指针 phead ，在函数内部对phead的修改只是修改了函数内部的一个副本。例如，在函数内 phead = newNode; （ newNode 是新插入的节点）这样的操作，只是改变了函数内部 phead 副本的指向，而不会改变函数外部真正的 phead 。
• 传递二级指针 &phead ，函数接收的是头节点指针phead 的地址。这样在函数内部可以通过解引用二级指针来修改真正的头节点 phead 。比如， *pphead = newNode; （ pphead 是接收二级指针的参数），这种操作会改变函数外部的 phead 的值，使得新插入的节点成为链表的新头节点，从而实现了正确的头插操作。

但是头插要分情况讨论，若本来链表中就没有节点呢？
若有节点怎么办？若没有又该怎么样？
若有节点，就先让新的节点的next域指向头结点*pphead，再让头结点*pphead重新指向这个新的结点，
若没有节点，就直接让*pphead指向新的结点

//头插
void FrontSLNode(SLNode** pphead, typeList n)
{
	assert(pphead);//断言：就是当pphead为NULL，会自动报错，并结束程序；
	//创建新的节点，并将其指针域和数据域都要进行初始化；
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	//初始化指针域和数据域
	newnode->data = n;
	newnode->next = NULL;
	//当链表为空，直接将新的结点插入链表头部
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}
	//链表不为空，新插入的节点将成为新的头节点，原来的头节点将成为新节点的下一个节点。
	newnode->next = *pphead;
	*pphead = newnode;
	return 0;
}

尾插操作

尾插就是指在单链表的末尾插入一个新节点；

• 在单链表中，当进行尾插操作时，需要考虑两种情况：一是链表为空时插入第一个节点，二是链表非空时插入新节点到尾部。
• 首先你要知道，尾插如果当链表一开始为空时，要尾插的话，你就需要改变phead的指向，此时你就需要传入二级指针；(可以这样想：当链表非空时，这时尾插不需要改变phead指针的指向，此时传一级指针就可以)

为什么需要传二级指针：因为

• 当链表为空时，头节点 phead 本身为 NULL 。如果只传一级指针，在函数内部修改 phead 的值（让它指向新插入的节点），这种修改在函数结束后不会影响到函数外部的 phead 变量。因为C语言中函数参数传递是值传递，对于指针变量也不例外。
• 传递二级指针（ &phead ）就可以在函数内部真正地修改头节点 phead 本身的值。例如，在插入第一个节点时，函数内部可以通过 *pphead = newNode; （假设 pphead 是二级指针接收的参数， newNode 是新插入的节点）这样的操作来让外部的phead指向新节点。
• 当链表非空时，通过二级指针也可以方便地遍历到链表的尾部进行插入操作，并且保证对链表结构的修改（如更新尾节点的 next 指针）能够在函数外部生效。

//尾插
void BackSLNode(SLNode** pphead, typeList n)
{
	assert(pphead);
	//创建新节点
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	初始化指针域和数据域
	newnode->data = n;
	newnode->next = NULL;
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}
	//链表不为空,找到尾巴
	SLNode* tem = *pphead;
	while (tem->next)
	{
		tem = tem->next;
	}
	//更新尾结点指向
	tem->next = newnode;
}

链表的删除操作

对于单向链表，删除操作可分为很多种比如：头删,尾删,删除指定位置的结点,删除指定位置之后的结点;接下来我来分别介绍：头删,尾删，后面的会在后续介绍；

当删除头结点时：

• 当要删除头节点时，首先要判断链表是否为空。如果链表为空，那就没有节点可删除。
• 若链表不为空，将头节点指针 phead 指向下一个节点（ *pphead = *pphead->next ）,此时改变了phead的头节点的指向，所以要传二级指针，然后释放原来头节点的内存空间，这样就完成了头节点的删除。

当不是删除头结点时：

• 首先需要遍历链表找到要删除节点的前驱节点。从链表头开始，逐个节点检查，直到找到一个节点（设为 pre ），它的下一个节点（ pre->next ）是要删除的节点。
• 然后将前驱节点 pre 的指针域跳过要删除的节点，即 pre->next = pre->next->next 。
• 最后释放要删除节点的内存空间。

头删操作

头删：就是将第一个节点删掉，然后让第二个节点变成新的节点；

//头删
void FrontDelSLNode(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);//当链表为空时，最好断言一下，否则下面的(*pphead)->next 会报错
	//作为前驱节点，最后要删除
	SLNode* pre = *pphead;
	//只有一个节点的情况
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//两个以上的结点的情况
	SLNode* ret = pre->next;
	*pphead = ret;
	free(pre);
	pre = NULL;
}

尾删操作

尾删：就是删除链表的最后一个节点，让倒数第二个节点的指针域指向NULL；

//尾删
void BackDelSLNode(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLNode* pre = *pphead;
	//只有一个节点的情况
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//两个以上的结点的情况,找到尾结点的前一个节点
	while (pre->next->next)
	{
		pre = pre->next;
	}
	//释放掉最后一个节点
	free(pre->next->next);
	pre->next->next = NULL;
	//再让倒数第二个节点的next域指向NULL
	pre->next = NULL;
}

链表的查找操作

查找:就是在单链表中寻找特定元素或节点，也就是说，传参的时候，可以传数据值或传地址进行查找；
注意：查找就是负责查找，并且返回那个节点而已，并不会改变phead头结点指针的方向，所以此时传一级指针即可；

按值查找：

• 从链表的头节点开始，通过遍历链表逐个比较节点的数据域与目标值。
• 设链表头节点为 phead ，可以使用一个指针 p = phead ，然后在循环中比较 p->data （假设 data 是存储数据的成员）和目标值。如果相等，就找到了目标节点；如果不相等，就将 p = p->next ，继续检查下一个节点，直到 p 为 NULL （表示遍历完链表未找到目标值）。

按址查找：

• 同样从头节点开始，要查找第 n 个位置的节点。定义一个计数变量 count = 1 ，一个指针 p = phead 。
• 当 count < n 且 p 不为 NULL 时，执行 p = p->next 和 count++ 操作。如果 count == n ，此时 p 指向的就是第 n 个节点；如果 p 为 NULL 且 count < n ，则表示链表长度小于 n ，不存在第 n 个节点。

这里我就偷个懒，就实现 按值查找 喽😊

//查找
SLNode* FindSLNode(SLNode* phead, typeList n)
{
	assert(phead);
	SLNode* p = phead;
	while (p)
	{
		if (p->data == n)
			return cour;
		p = p->next;
	}
	return NULL;
}

链表的在指定位置的插入

其实原理也是和头插,尾插原理相同；唯一需要理解的是什么叫在特定位置？这里我们就需要和之前的那个查找操作相结合了，先找到你需要插入的节点，再在对这个节点之前，节点之后进行插入新的节点；
注意，当你在在查找到的位置之前插入，就有可能会改变头结点phead指针的指向，需要传二级指针；但是当你在在查找到的位置之后插入，就不会改变头结点phead指针的指向，所以不需要传二级指针，一级指针就可以了；

在指定位置之前插入

此时传参不但需要查找到的那个节点，还需要将头结点传入进来，是为了遍历链表找到指定的那个节点

//在指定位置之前插入数据
void InsertSLNode(SLNode** pphead, SLNode* pos, typeList n)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);//此时还要对指定位置的结点断言
	//创建新节点，并进行初始化
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	newnode->data = n;
	newnode->next = NULL;

	//当在第一个节点之前插入
	if ((*pphead) == pos)
	{
		//就是头插，直接将头插的代码拿过来，Ctrl C V真的很快乐😍
		FrontSLNode(pphead, n);
		return;
	}

	//其他节点，找到指定位置之前的那个节点
	SLNode* tem = *pphead;
	while (tem->next != pos)
	{
		tem = tem->next;
	}
	//插进来
	tem->next = newnode;
	newnode->next = pos;
}

在指定位置之后插入

在指定位置之后插入，就不存在改变头节点phead的可能性，不需要遍历就能找到指定的那个节点；

//在指定位置之后插入数据
void InsertAfterSLNode(SLNode* pos, typeList n)
{
	assert(pos);
	//创建新节点，并进行初始化
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	newnode->data = n;
	newnode->next = pos->next;
	pos->next = newnode;
}

链表在指定位置的删除

其实和链表的在指定位置的插入的原理相同，先找到这个指定位置，在进行删除操作；
链表在指定位置的删除：可以删除指定位置的结点,删除指定位置之后的结点；

删除指定位置的结点

删除指定位置的结点，需要传头结点用来遍历找到特定位置的结点，也有可能删除头结点phead，所以需要传二级指针；

进行特殊情况的判断：

• 首先判断链表是否为空，如果为空，则无法进行删除操作，直接返回。
• 如果指定位置是第 1 个节点，即删除头节点，这时候只需要将头指针指向头节点的下一个节点，并释放原来头节点的内存空间即可。

步骤：
1.查找要删除节点的前驱节点
2.再删除节点

//删除pos节点
void SLTErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//当为第一个节点,进行头删
	if (pos == (*pphead))
	{
		//相当于进行头删操作
		FrontDelSLNode(pphead);
		return;
	}
	SLNode* tem = *pphead;
	while (tem->next != pos)
	{
		tem = tem->next;
	}
	tem->next = pos->next;

	free(pos);
	pos = NULL;
}

删除指定位置之后的结点

删除指定位置之后的结点,不存在改变头节点phead指针的可能性，所以传一级指针即可；

//删除pos之后的节点
void SLTEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLNode* tem = pos;

	pos = tem->next->next;
	free(tem->next);
	tem->next = NULL;
}

链表的销毁

链表的销毁就是指释放链表中所有节点占用的内存空间，使链表不再使用；
所以要改变头结点phead指针的指向，所以传二级指针；

• 首先需要一个指针ptr来遍历链表，接着使用一个临时指针next来保存当前节点 ptr的下一个节点的位置，然后释放当前节点ptr所占用的内存空间，最后将ptr指针更新为next；重复上述步骤，直到ptr==NULL，这意味着已经办理并释放了链表的所有节点；

//销毁链表
void SListDesTroy(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	SLNode* ptr = *pphead;
	while (ptr != NULL)
	{
		SLNode* next = ptr->next;
		free(ptr);
		ptr = NULL;
	}
	*pphead = NULL;
}

额外的知识：带头单向链表的初始化

链表开始的时候需要初始化链表，因为初始化能建立一个稳定的起始状态，就像盖房子之前需要先打好地基一样，以确保数据结构符合预期的初始性质；
当面对传参问题：
带头链表的初始化可以有两种形式：
1.无参数形式；2.参数形式；

当为无参数形式 ：因为链表的初始化主要是创建一个节点，并将指针域设置成NULL;
例如：这里的InitSLNode函数没有参数；

SLNode* InitSLNode() {
    SLNode* head = (SLNode*)malloc(sizeof(SLNode));
    if (head == NULL) {//这里的malloc向堆区中开辟空间可能失败，所以这边进行判断；
        return NULL;
    }
    //这里最好就将数据域也进行初始化一下，要不然你这个结点的数据域就是一个随机值
    head -> data = 0;
    //将指针域设为NULL，变成一个独立的节点
    head -> next = NULL;
    return head;
}

//无参数形式这样进行初始化
int main()
{
	SLNode*phead=InitSLNode();
	return 0;
}

当为参数形式 ：其实传参数可以根据自身需求进行不同的设置：比如我这时传入的是一个整数为初始值来初始化链表的节点；
这里我们想的是把结构体变成一个链表的结点，所以我们直接传结构体的地址就可以了；我们就可以将这个结构体直接就变成节点；

例如：这里的InitSLNode函数有参数；

//初始化
void InitSLNode(SLNode* phead)
{
	//这里最好就将数据域也进行初始化一下，要不然你这个结点的数据域就是一个随机值
	phead->data = 0;
	//将指针域设为NULL，变成一个独立的节点
	phead->next = NULL;
}

//有参形式这样进行初始化
int main()
{
	SLNode head;
	InitSLNode(&head);

	return 0;
}

这里对于参数形式的传参问题：为什么传结构体的地址？
因为，只有传地址调用的时候可以直接修改结构体的成员（数据域和指针域）；若你只是传结构体变量进来，不能改变结构体的成员（数据域和指针域）
如果还有不太懂的东西，可以去了解一下：传值调用和传址调用的区别；

总结

到了最后：感谢支持

------------对过程全力以赴，对结果淡然处之
也是对我自己讲的