【数据结构与算法】单链表探秘：解锁数据结构中的灵动链条

大家好，我是小卡皮巴拉

文章目录

一.单链表初探：构建数据结构的基石

1.1 单链表的概念及结构

1.2 节点的理解

1.3 链表的性质

二.单链表的作用：为何它是数据处理的优选

2.1 动态内存管理：内存世界的魔术师

2.2 高效的数据操作：插入与删除的极速体验

2.3 解决特定问题的利器：链表的多面手角色

2.4 内存优化的艺术：链表如何精打细算

2.5 简化算法实现的秘诀：链表带来的直观与简洁

三.单链表的实现：从理论到实践的奇妙旅程

定义单链表节点结构

打印单链表中的所有节点数据

创建一个新结点

尾插

头插

尾删

头删

查找

在指定位置之前插入数据

在指定位置之后插入数据

删除pos位置的结点

删除pos位置之后的结点

销毁

兄弟们共勉！！！

每篇前言

博客主页：小卡皮巴拉

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

想象一下，如果你站在一列缓缓行驶的火车上，这列火车由一节节车厢紧密相连而成，每节车厢都承载着不同的货物或乘客，而车厢之间的连接部分则允许它们作为一个整体在铁轨上前进。现在，让我们把这个生动的场景抽象化，用它来比喻计算机科学中一个非常重要的数据结构——链表。

一.单链表初探：构建数据结构的基石

链表，就像这列火车，由一个个节点（Node）串联而成。每个节点都相当于火车的一节车厢，它包含两部分：一部分用于存储数据，就像车厢里的货物或乘客；另一部分则是一个指针（Pointer），它指向链表中的下一个节点，就像车厢之间的连接部分，让整列火车能够保持连贯并向前行驶。

1.1 单链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。单链表是由一个个节点，通过指针连接在一起形成的。链表中最后一个节点的next指针为空，不指向任何节点。

节点结构：每个结点都包含两个部分，一是存储数据的元素（data域），二是存储指向下一个节点地址的指针（next域）。

1.2 节点的理解

与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/节点”

结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。

图中指针变量 plist保存的是第⼀个结点的地址，我们称plist此时“指向”第一个结点，如果我们希望 plist“指向”第二个结点时，只需要修改plist保存的内容为0x0012FFA0。链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。

1.3 链表的性质

链式机构在逻辑上是连续的，在物理结构上不⼀定连续
结点⼀般是从堆上申请的
从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

结合前⾯学到的结构体知识，我们可以给出每个结点对应的结构体代码

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

二.单链表的作用：为何它是数据处理的优选

2.1 动态内存管理：内存世界的魔术师

与数组等静态数据结构不同，单链表允许在运行时动态地添加或删除节点。这意味着，当需要存储更多数据时，可以创建新的节点并将其添加到链表的末尾；同样，当不再需要某些数据时，可以删除对应的节点并释放其占用的内存。这种动态性使得单链表在处理不确定大小的数据集时非常有用。

2.2 高效的数据操作：插入与删除的极速体验

虽然单链表在随机访问数据方面不如数组高效（因为需要从头节点开始顺序遍历），但在插入和删除操作方面却具有显著优势。在单链表中，插入和删除操作通常只需要调整相邻节点的指针即可，而无需像数组那样移动大量数据。这使得单链表在处理需要频繁插入和删除操作的数据集时更加高效。

2.3 解决特定问题的利器：链表的多面手角色

单链表在解决某些特定问题时具有独特优势。例如，在实现队列（FIFO数据结构）时，可以使用单链表来存储队列中的元素，并通过两个指针（分别指向队头和队尾）来高效地管理队列的入队和出队操作。此外，单链表还可以用于实现哈希表、图的邻接表等复杂数据结构。

2.4 内存优化的艺术：链表如何精打细算

在某些情况下，单链表可以通过减少内存浪费来优化内存使用。例如，当需要存储大量稀疏数据时（即数据集中包含大量空值或无效值），使用单链表可以只存储有效数据及其指针，从而避免为无效数据分配内存。

2.5 简化算法实现的秘诀：链表带来的直观与简洁

单链表的结构简单明了，这使得许多算法的实现变得更加直观和易于理解。例如，在遍历链表时，只需从头节点开始依次访问每个节点即可；在查找特定值时，也可以从头节点开始顺序比较每个节点的数据域。这种简洁性使得单链表成为学习和实践算法的理想选择。

三.单链表的实现：从理论到实践的奇妙旅程

定义单链表节点结构

首先，我们需要定义一个结构体来表示单链表的节点。这个结构体包含两个核心成员：

data：该成员的类型为SLTDataType，它是一个整型数据的别名（通过typedef定义）。data用于存储每个节点中的具体数据。

next：该成员是一个指针，其类型为struct SListNode*。由于我们使用了typedef为结构体起了别名SLTNode，因此这里的类型也可以写作SLTNode*。next指针用于指向链表中的下一个节点，从而实现了节点之间的链接。

这两个成员共同定义了单链表节点的结构，它是构建和操作整个链表的基础。

函数代码：
// 定义节点存储的数据类型  
typedef int SLTDataType;  
  
// 定义单链表节点结构体  
typedef struct SListNode  
{  
    SLTDataType data; // 节点数据，类型为SLTDataType（即int）  
    struct SListNode* next; // 指向下一个节点的指针，类型为struct SListNode*（或SLTNode*）  
} SLTNode; // 结构体别名，方便后续使用

打印单链表中的所有节点数据

首先，我们需要一个函数来遍历并打印单链表中的所有元素。这个函数接收一个指向单链表头节点的指针phead作为参数。

函数内部，我们创建了一个名为pcur的辅助指针，并将其初始化为指向链表的头节点phead。这个辅助指针的作用是遍历链表，同时保持对链表头节点的引用不变，以便在需要时能够重新访问。

接下来，我们使用一个while循环来遍历链表。循环的条件是pcur指针不为NULL，这意味着我们还没有到达链表的末尾。

在循环体内，我们使用printf函数打印当前节点的数据pcur->data，并在其后添加箭头->来表示链表中的链接关系。然后，我们将pcur指针更新为指向链表中的下一个节点pcur->next。

当pcur指针变为NULL时，循环结束，我们打印出NULL来表示链表的末尾。

函数代码：
// 假设SLTNode结构体已经定义，并且SLTDataType为int类型  
void SLTPrint(SLTNode* phead)  
{  
    // 创建一个辅助指针pcur，初始化为指向链表的头节点  
    SLTNode* pcur = phead;  
      
    // 使用while循环遍历链表  
    while (pcur != NULL)  
    {  
        // 打印当前节点的数据，并在其后添加箭头表示链接关系  
        printf("%d -> ", pcur->data);  
          
        // 将pcur指针更新为指向链表中的下一个节点  
        pcur = pcur->next;  
    }  
      
    // 打印NULL来表示链表的末尾  
    printf("NULL\n");  
}

创建一个新结点

首先，我们需要一个函数来创建一个新的单链表节点。这个函数接收一个整型数据x作为参数，并返回一个指向新创建的节点的指针。

函数内部，我们执行以下步骤：

使用malloc函数动态分配一个SLTNode结构体大小的内存空间，并将返回的指针强制转换为SLTNode*类型，赋值给node变量。这个新分配的内存将用于存储新节点的数据。

检查malloc函数是否成功分配了内存。如果node为NULL，则表示内存分配失败。此时，我们使用perror函数打印错误信息，并通过exit函数终止程序运行，以避免潜在的内存访问错误。

将传入的数据x赋值给新节点的data成员，表示该节点存储的数据。

将新节点的next成员初始化为NULL，表示该节点当前不指向任何下一个节点，即它是链表中的一个新末尾节点。

返回指向新创建的节点的指针，以便在链表的其他操作中使用。

函数代码：
// 假设SLTNode结构体已经定义，并且SLTDataType为int类型  
SLTNode* SLTBuyNode(SLTDataType x)  
{  
    // 1. 动态分配内存并初始化node指针  
    SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));  
      
    // 2. 检查内存分配是否成功  
    if (node == NULL)  
    {  
        // 内存分配失败，打印错误信息并终止程序  
        perror("malloc fail!\n");  
        exit(1);  
    }  
      
    // 3. 设置新节点的数据  
    node->data = x;  
      
    // 4. 初始化新节点的next指针为NULL  
    node->next = NULL;  
      
    // 5. 返回指向新节点的指针  
    return node;  
}

尾插

一、函数目的

函数SLTPushBack的目的是实现向一个单链表（由SLTNode结构体表示）的尾部插入一个新节点，新节点的值为参数x。

二、函数实现思路

参数检查

首先使用assert(pphead)检查传入的二级指针pphead是否有效。如果pphead为NULL，则程序会在运行时中断，这确保了函数调用者正确地传入了有效的链表头指针的地址。

创建新节点

SLTNode* newcode = SLTBuyNode(x)调用另一个函数SLTBuyNode创建一个新的链表节点，并将传入的参数x作为新节点的值进行初始化。

处理空链表情况

如果*pphead（即链表头指针指向的地址所存储的链表头节点）为NULL，说明链表为空。此时直接将新创建的节点赋值给*pphead，使链表头指针指向新节点，完成插入操作。

处理非空链表情况

如果链表非空，首先定义一个指针ptail并初始化为*pphead，用于遍历链表找到尾节点。

使用while (ptail->next)循环遍历链表，只要ptail->next不为NULL，就说明ptail不是尾节点，继续将ptail移动到下一个节点。

当循环结束时，ptail指向了链表的尾节点。

最后，将尾节点的next指针指向新创建的节点newcode，完成向链表尾部插入新节点的操作。

函数代码：
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newcode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newcode;
	}
	else
	{
		//链表非空，找尾结点
		SLTNode* ptail = *pphead;
		while (ptail->next)//等价于ptail->next != NULL
		{
			ptail = ptail->next;
		}
		//连接ptail和newnode
		ptail->next = newcode;
	}
}

头插

一、函数目的

函数SLTPushFrond的目的是实现向一个单链表（由SLTNode结构体表示）的头部插入一个新节点，新节点的值为参数x。

二、函数实现思路

参数检查

使用assert(pphead)检查传入的二级指针pphead是否有效。确保函数调用者正确地传入了有效的链表头指针的地址。

创建新节点

SLTNode* newnode = SLTBuyNode(x)调用另一个函数SLTBuyNode创建一个新的链表节点，并将传入的参数x作为新节点的值进行初始化。

插入新节点

首先让新节点的next指针指向当前链表的头节点，即newnode->next = *pphead。

然后更新链表头指针，使其指向新节点，即*pphead = newnode。这样就完成了向链表头部插入新节点的操作。

函数代码：
//头插
void SLTPushFrond(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

尾删

一、函数目的

函数SLTPopBack的目的是实现从一个单链表（由SLTNode结构体表示）的尾部删除一个节点。

二、函数实现思路

参数检查

使用assert(pphead && *pphead)检查传入的二级指针pphead是否有效，并且确保链表不为空。如果pphead为NULL或者链表为空，程序会在运行时中断。

处理只有一个节点的情况

如果链表只有一个节点，即(*pphead)->next == NULL。此时先释放该节点的内存空间，即free(*pphead)，然后将链表头指针置为NULL，即*pphead = NULL，完成删除操作。

处理多个节点的情况

如果链表有多个节点，首先定义两个指针ptail和prev，分别用于指向尾节点和尾节点的前一个节点。初始时，ptail指向链表头节点*pphead，prev为NULL。

使用while (ptail->next)循环遍历链表，只要ptail->next不为NULL，就说明ptail不是尾节点。在循环中，将prev指向当前的ptail，然后将ptail移动到下一个节点。

当循环结束时，ptail指向了尾节点，prev指向尾节点的前一个节点。

然后断开prev与ptail的连接，即prev->next = NULL。接着释放尾节点的内存空间，即free(ptail)，并将ptail置为NULL，完成从链表尾部删除节点的操作。

函数代码：
//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);//链表不为空
	//只有一个结点的情况（要单独处理）
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* ptail = *pphead;
		SLTNode* prev = NULL;

		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//断开prev 与 ptail的连接
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
}

头删

一、函数目的

函数SLTPopFront的目的是实现从一个单链表（由SLTNode结构体表示）的头部删除一个节点。

二、函数实现思路

参数检查

使用assert(pphead && *pphead)检查传入的二级指针pphead是否有效，并且确保链表不为空。如果pphead为NULL或者链表为空，程序会在运行时中断。

删除头节点

首先获取链表头节点的下一个节点指针，即SLTNode* next = (*pphead)->next。

然后释放链表头节点的内存空间，即free(*pphead)。

最后更新链表头指针，使其指向原来头节点的下一个节点，即*pphead = next，完成从链表头部删除节点的操作。

函数代码：
//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

查找

一、函数目的

函数SLTFind的目的是在一个单链表（由SLTNode结构体表示）中查找值为x的节点，并返回该节点的指针。如果未找到，则返回NULL。

二、函数实现思路

初始化指针

定义一个指针pcur并初始化为链表头指针phead，用于遍历链表。

遍历链表

使用while (pcur)循环遍历链表，只要pcur不为NULL，就继续循环。这意味着只要还没有到达链表的末尾，就继续查找。

比较节点值

在循环中，检查当前节点pcur的数据域pcur->data是否等于要查找的值x。如果相等，说明找到了目标节点。

返回结果

如果找到了目标节点，即pcur->data == x，则立即返回当前节点的指针pcur。

如果遍历完整个链表都没有找到目标节点，循环结束后，返回NULL表示未找到。

函数代码：
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur)//pcur != NULL
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//未找到
	return NULL;
}

在指定位置之前插入数据

一、函数目的

函数SLTInsertBefore的目的是在一个单链表（由SLTNode结构体表示）中指定位置的节点pos之前插入一个新节点，新节点的值为参数x。

二、函数实现思路

参数检查

使用assert(pphead && pos)检查传入的二级指针pphead和指定位置节点指针pos是否有效。确保函数调用者正确地传入了有效的链表头指针地址和要插入位置的节点指针。

处理特殊情况（插入位置为头节点）

如果要插入位置的节点pos就是链表的头节点，即pos == *pphead，相当于进行头插操作。此时调用SLTPushFrond函数，在链表头部插入新节点。

处理一般情况

如果插入位置不是头节点，首先调用另一个函数SLTBuyNode创建一个新的链表节点，并将传入的参数x作为新节点的值进行初始化，即SLTNode* newnode = SLTBuyNode(x)。

然后找到要插入位置节点pos的上一个节点prev。通过遍历链表，从链表头开始，使用while (prev->next!= pos)循环，只要prev的下一个节点不是pos，就继续将prev移动到下一个节点。

当循环结束时，prev指向了pos的上一个节点。

接着将新节点与要插入位置的节点pos连接，即newnode->next = pos。

最后将pos的上一个节点prev和新节点连接，即prev->next = newnode，完成在指定位置节点之前插入新节点的操作。

函数代码：
//在指定位置之前插入数据
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && pos);
	//当pos就是头结点，相当于头插
	if (pos == *pphead)
	{
		SLTPushFrond(pphead, x);
	}
	else
	{
		//申请新结点
		SLTNode* newnode = SLTBuyNode(x);
		//找到pos的上一个结点prev
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//将新结点与pos连接
		newnode->next = pos;
		//pos的上一个结点prev和新结点连接
		prev->next = newnode;
	}
}

在指定位置之后插入数据

一、函数目的

函数SLTInsertAfter的目的是在一个单链表（由SLTNode结构体表示）中指定位置的节点pos之后插入一个新节点，新节点的值为参数x。

二、函数实现思路

参数检查

使用assert(pos)检查传入的指定位置节点指针pos是否有效。确保函数调用者传入了有效的节点指针。

插入新节点

首先调用另一个函数SLTBuyNode创建一个新的链表节点，并将传入的参数x作为新节点的值进行初始化，即SLTNode* newnode = SLTBuyNode(x)。

然后将新节点的next指针指向指定位置节点pos的下一个节点，即newnode->next = pos->next。

最后将指定位置节点pos的next指针指向新节点，即pos->next = newnode，完成在指定位置节点之后插入新节点的操作。

函数代码：
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	//申请新结点
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

删除pos位置的结点

一、函数目的

函数SLTErase的目的是在一个单链表（由SLTNode结构体表示）中删除指定位置的节点pos。

二、函数实现思路

参数检查

使用assert(pphead && pos)检查传入的二级指针pphead和要删除的节点指针pos是否有效。确保函数调用者正确地传入了有效的链表头指针地址和要删除的节点指针。

处理特殊情况（要删除的节点是头节点）

如果要删除的节点pos就是链表的头节点，即pos == *pphead，相当于进行头删操作。此时调用SLTPopFront函数，删除链表头部节点。

处理一般情况

如果要删除的节点不是头节点，首先找到要删除节点pos的上一个节点prev。通过遍历链表，从链表头开始，使用while (prev->next!= pos)循环，只要prev的下一个节点不是pos，就继续将prev移动到下一个节点。

当循环结束时，prev指向了要删除节点pos的上一个节点。

然后将prev的next指针指向pos的下一个节点，即prev->next = pos->next，完成链表中节点的连接调整。

接着释放要删除节点pos的内存空间，即free(pos)。

最后将pos指针置为NULL，避免出现悬空指针。

函数代码：
//删除pos位置的结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && pos);
	//要删除的结点就是头结点
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		//找到pos的上一个结点prev
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//将prev和pos的后一个结点连接
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

删除pos位置之后的结点

一、函数目的

函数SLTEraseAfter的目的是在一个单链表（由SLTNode结构体表示）中删除指定位置节点pos之后的节点。

二、函数实现思路

参数检查

使用assert(pos && pos->next)检查传入的指定位置节点指针pos是否有效，并且确保pos不是尾节点（即pos的下一个节点存在）。如果pos为NULL或者pos是尾节点，程序会在运行时中断。

删除节点

首先定义一个指针del指向要删除的节点，即pos之后的节点，SLTNode* del = pos->next。

然后将pos的next指针指向要删除节点的下一个节点，即pos->next = del->next，完成链表中节点的连接调整。

接着释放要删除节点del的内存空间，即free(del)。

最后将del指针置为NULL，避免出现悬空指针。

函数代码：
//删除pos位置之后的结点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

销毁

一、函数目的

函数SListDestroy的目的是销毁一个单链表（由SLTNode结构体表示），释放链表中所有节点占用的内存空间，并将链表头指针置为NULL。

二、函数实现思路

参数检查

使用assert(pphead)检查传入的二级指针pphead是否有效。确保函数调用者正确地传入了有效的链表头指针地址。

遍历并释放节点

定义一个指针pcur并初始化为链表头指针*pphead，用于遍历链表。

使用while (pcur)循环遍历链表，只要pcur不为NULL，就继续循环。

在循环内部，首先存储当前节点pcur的下一个节点指针到next，即SLTNode* next = pcur->next。这是为了在释放当前节点后，能够继续遍历链表。

然后释放当前节点pcur的内存空间，即free(pcur)。

最后将pcur更新为下一个节点，即pcur = pcur->next，这里实际上是将pcur指向之前存储的next指针所指向的节点。

置链表头指针为NULL

当链表中的所有节点都被释放后，将链表头指针*pphead置为NULL，表示链表已被销毁。

函数代码：
//销毁
void SListDestroy(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		//先存储pcur的下一个结点
		SLTNode* next = pcur->next;
		//释放pcur
		free(pcur);
		//pcur找到下一个结点，形成循环
		pcur = pcur->next;
	}
	*pphead = NULL;
}