数据结构宝典：用11个核心操作吃透单链表的指针艺术

数组（顺序表）擅长快速查找，但在中间插入或删除元素时效率低下，需要大量移动数据，就像在整齐的储物柜中硬塞东西一样麻烦。 现在换个思路。想象一列灵活的火车：每节车厢（数据）都是独立存在的，但它持有一把通往下一节车厢的钥匙（地址）。我们只需当前这把钥匙就能找到下一个数据，无需知道所有数据的位置。 这就是单链表（Singly Linked List）：一种物理存储上非连续、非顺序的灵活数据结构。它以牺牲随机访问的效率，换取了高效的插入和删除能力。掌握链表，你就能掌握解决复杂算法问题的基石。

一、基础概念：从“储物柜”到“灵活车厢”

1.1 链表的概念与结构

链表是一种线性的存储结构。数据元素的逻辑顺序是通过节点中的指针链接次序实现的。链表中的每一块独立申请下来的空间，我们称之为节点（Node/结点）。

在这里插入图片描述

链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。在链表里，每个节点都是独立申请下来的空间。

1.2 节点结构解析

每个链表节点都由两个核心部分组成：

1. 数据域（Data）：用于存储当前节点要保存的实际数据。
2. 指针域（Next Pointer）：一个指针变量，用于存储下一个节点的内存地址。

在 C 语言中，我们定义单链表的节点结构体如下：

// 单链表数据类型，方便以后修改，这里定义为整型
typedef int SLinkListDataType;
// 单链表结构体定义 (即节点结构)
typedef struct SLinkList
{
	SLinkListDataType data;     // 数据域：存储实际的数据
	struct SLinkList* next;     // 指针域：保存下一个节点的地址
}SLNode;

思考： 当我们需要保存的数据类型为字符型、浮点型或自定义的 PersonInfo 结构体时，只需要修改 SLTDataType 的定义即可。

1.3 单链表与数组（顺序表）对比

效率高，只需修改指针

（需先找到位置）随机访问效率高，通过下标

效率低，必须从头遍历

内存分配静态或一次性分配独立申请空间（通常从堆上申请）

二、 单链表操作全集：11个核心函数的深度解析

在掌握了单链表的基础结构和二级指针的奥秘后，我们现在将一一实现所有核心操作。所有操作都基于您提供的

结构体定义。

I. 辅助函数：内存管理

这是我们链表的“零件工厂”，是所有创建操作的基础。所有操作的核心都是：找到前驱节点，然后修改指针。我们将 SLTNode **pphead 作为头指针的地址，方便我们在函数内部修改链表的起点（

）。

1. 申请新节点 (SLNodeBuyNode)

思路： 首先，使用 malloc 函数在堆上动态分配一个

结构体大小的内存空间。然后，将传入的数据

赋值给新节点的 data 域，并将新节点的 next 指针初始化为 NULL，表示它暂时不指向任何后续节点。

注意事项： 必须对 malloc 的返回值进行检查。如果返回 NULL，意味着内存分配失败（通常是系统内存不足），此时应进行错误处理并终止程序（exit(-1)），以保证程序的鲁棒性。

源码：

// SLNodeBuyNode: 申请新节点
SLNode* SLNodeBuyNode(SLinkListDataType x)
{
	// 1. 动态分配单个节点所需的内存空间
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	// 2. 检查内存分配是否成功
	if (newnode == NULL)
	{
		perror("malloc failed to allocate memory");
		exit(-1); // 失败则终止程序
	}
	// 3. 初始化数据域和指针域
	newnode->next = NULL; 
	newnode->data = x;
	return newnode;
}

II. 增删操作 (Insertion & Deletion)

2. 头插 (SLNodePushFront)

思路： 这是链表最快的插入方式。创建新节点后，让新节点的 next 指针指向当前的头节点（即 *pphead），然后将链表的头指针 *pphead 更新为新节点的地址。

注意事项： 必须传入二级指针 (SLNode** pphead)。这是因为我们需要在函数内部修改主函数中头指针变量

的值（让它指向一个新的起始位置），一级指针无法做到这一点。

源码：

// SLNodePushFront: 头插
void SLNodePushFront(SLNode** pphead, SLinkListDataType x)
{
	assert(pphead); 
	SLNode* newnode = SLNodeBuyNode(x);
	// 1. 新节点的 next 指向原头节点 (*pphead)
	newnode->next = *pphead;
	// 2. 更新头指针：让头指针指向新节点
	*pphead = newnode; 
}

3. 尾插 (SLNodePushBack)

思路： 首先判断链表是否为空。如果为空，新节点即为新的头节点。如果不为空，则需要从头节点开始遍历，直到找到最后一个节点（判断条件是当前节点的 next 为 NULL）。找到尾节点后，将其 next 指针指向新节点即可。

注意事项： 空链表边界：必须检查 *pphead 是否为 NULL。同时，由于需要修改

（仅在空链表时），因此仍然需要传入二级指针。

源码：

// SLNodePushBack: 尾插
void SLNodePushBack(SLNode** pphead, SLinkListDataType x)
{
	assert(pphead);
	SLNode* newnode = SLNodeBuyNode(x);
	// 1. 边界情况：如果为空链表
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 2. 遍历找到最后一个节点（pcur->next == NULL）
		SLNode* pcur = *pphead;
		while (pcur->next) 
		{
			pcur = pcur->next;
		}
		// 3. 将原尾节点的 next 指向新节点
		pcur->next = newnode;
	}
}

4. 头删 (SLNodePopFront)

思路： 首先检查链表是否为空。如果不空，用一个临时指针

保存当前头节点，然后将头指针 *pphead 直接指向 temp->next（即原第二个节点）。最后，使用 free(temp) 释放原头节点占用的内存。

注意事项： 内存释放：操作完成后，必须调用 free() 释放被删除节点的内存，防止内存泄漏。空链表检查是必须的。

源码：

// SLNodePopFront: 头删
void SLNodePopFront(SLNode** pphead)
{
	assert(pphead);
    // 1. 边界检查：如果链表为空，直接返回
	if (*pphead == NULL) 
		return;
	// 2. 临时保存原头节点
	SLNode* temp = *pphead;
    // 3. 更新头指针：指向原头节点的下一个节点
	*pphead = temp->next;
    // 4. 释放原头节点内存
	free(temp);
	temp = NULL; // 释放后将指针置空，防止野指针
}

5. 尾删 (SLNodePopBack)

思路： 这是单链表最复杂的基础操作。必须处理空链表和只有一个节点的链表这两种边界情况。对于多节点链表，需要遍历链表，找到倒数第二个节点

。判断条件是 pcur->next->next 为 NULL。找到

后，释放

（即最后一个节点），并将

置为 NULL。

注意事项： 两重边界：必须单独判断并处理链表为空和只有一个节点的情况。在遍历查找时，要确保指针不越界。

源码：

// SLNodePopBack: 尾删
void SLNodePopBack(SLNode** pphead)
{
    assert(pphead);
    // 1. 边界检查：如果链表为空
    if (*pphead == NULL)
        return;
    // 2. 边界检查：如果链表只有一个节点
    if ((*pphead)->next == NULL)
    {
        free(*pphead); 
        *pphead = NULL; 
        return;
    }
    // 3. 寻找倒数第二个节点
    SLNode* pcur = *pphead;
    // 循环条件：找到 pcur 的 next 是最后一个节点
    while (pcur->next->next != NULL)
    {
        pcur = pcur->next;
    }
    // 4. 释放最后一个节点（pcur->next）
    free(pcur->next); 
    // 5. 将倒数第二个节点的 next 置为 NULL，使其成为新的尾节点
    pcur->next = NULL; 
}

III. 位置与销毁操作

6. 指定位置后插入 (SLNodeInsertAfter)

思路： 这是

的高效插入。创建新节点后，让新节点的 next 指针继承 pos->next 的值，相当于连接了链表的后半部分。然后，将

节点的 next 指针指向新节点，完成连接。

注意事项： pos 参数检查：确保传入的

节点指针有效（不为 NULL）。即使

是尾节点，操作也是正确的（新节点的 next 依然是 NULL）。

源码：

// SLNodeInsertAfter: 指定位置后插入
void SLNodeInsertAfter(SLNode* pos, SLinkListDataType x)
{
	assert(pos);	
	SLNode* newnode = SLNodeBuyNode(x);	
	// 1. 新节点的 next 继承 pos 后面所有节点的地址
	newnode->next = pos->next;
	// 2. pos 的 next 指向新节点
	pos->next = newnode;
}

7. 删除 pos 之后的节点 (SLNodeEraseAfter)

思路： 这是

的高效删除。用临时指针

记录要删除的节点（即 pos->next）。然后让

直接指向

，跳过

节点。最后，释放

节点的内存。

注意事项： 节点有效性：必须确保 pos 不是链表的尾节点（即 pos->next 存在），否则无法进行删除操作。操作完成后必须释放

节点的内存。

源码：

// SLNodeEraseAfter: 删除 pos 之后的节点
void SLNodeEraseAfter(SLNode* pos)
{
	// 确保 pos 存在，且 pos 后面有节点
	assert(pos && pos->next); 
	// 1. 临时保存要删除的节点
	SLNode* del = pos->next;
	// 2. 跨越删除节点：pos 的 next 指针直接指向 del 的下一个节点
	pos->next = del->next;
	// 3. 释放被删除节点的内存
	free(del);
	del = NULL;
}

8. 查找 (SLNodeFind)

思路： 从链表头开始，使用工作指针

遍历每个节点。在循环内部，比较当前节点的 data 域是否等于目标值

。如果匹配，则返回当前节点的地址。如果遍历到链表末尾（pcur 为 NULL）仍未找到，则返回 NULL。

注意事项： 函数返回值用于判断是否查找成功。返回 NULL 意味着查找失败。

源码：

// SLNodeFind: 查找
SLNode* SLNodeFind(SLNode* phead, SLinkListDataType x)
{
	SLNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
			return pcur; // 找到，返回节点地址      
		pcur = pcur->next;
	}
	return NULL; // 未找到，返回 NULL
}

9. 指定位置前插入 (SLNodeInsert)

思路： 由于是单链表，在

之前插入必须先找到

的前驱节点

。

1. 边界处理：如果

就是头节点 *pphead，则直接调用头插逻辑。

1. 查找前驱：从头开始遍历，直到找到

满足 pcur->next == pos。

1. 连接：执行

的连接操作。

注意事项： 二级指针：由于可能发生头插（修改 *pphead），因此必须传入二级指针。前驱查找：这是

操作，是单链表在该操作上的性能瓶颈。

源码：

// SLNodeInsert: 指定位置前插入
void SLNodeInsert(SLNode** pphead, SLNode* pos, SLinkListDataType x)
{
	assert(pphead && *pphead && pos); 
	SLNode* newnode = SLNodeBuyNode(x);
	// 1. 边界情况：如果 pos 就是头节点，使用头插逻辑
	if (*pphead == pos)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		// 2. 寻找 pos 的前一个节点 (pcur->next == pos)
		SLNode* pcur = *pphead;
		while (pcur->next != pos)
		{
            // 确保 pos 确实在链表中
			pcur = pcur->next;
		}
		// 3. 执行连接操作 (pcur -> newnode -> pos)
		pcur->next = newnode;
		newnode->next = pos;
	}
}

10. 删除 pos 节点 (SLNodeErasw)

思路： 与前插类似，删除

节点也必须先找到

的前驱节点

。

1. 边界处理：如果

是头节点，则直接使用头删逻辑：更新 *pphead 为 pos->next。

1. 查找前驱：从头遍历找到

满足 pcur->next == pos。

1. 删除：让

指向

，绕过

节点。最后释放

。

注意事项： 边界和内存：必须处理头节点的情况，并且操作完成后必须调用 free(pos)。函数名采用您提供的 SLNodeErasw。

源码：

// SLNodeErasw: 删除 pos 节点 (采用用户指定的函数名)
void SLNodeErasw(SLNode** pphead, SLNode* pos)
{
    assert(pphead && *pphead && pos);
    // 1. 边界情况：如果 pos 是头节点
    if (*pphead == pos)
    {
        // 直接使用头删逻辑：更新头指针
        *pphead = pos->next;
    }
    else
    {
        // 2. 寻找 pos 的前一个节点 pcur
        SLNode* pcur = *pphead;
        while (pcur->next != pos)
        {
            // 如果遍历到链表末尾都没找到 pos，说明 pos 是无效参数
            assert(pcur->next != NULL); 
            pcur = pcur->next;
        }
        // 3. 执行删除：pcur 绕过 pos 节点
        pcur->next = pos->next;
    }
    // 4. 释放 pos 节点内存
    free(pos);
    pos = NULL;
}

11. 销毁链表 (SLNodeDestroy)

思路： 遍历整个链表，依次释放每个节点的内存。为了安全地移动到下一个节点，必须在释放当前节点之前，先用一个临时指针（如

）保存下一个节点的地址。遍历完成后，将头指针 *pphead 置为 NULL。

注意事项： 释放顺序：这是最容易出错的地方。必须是 保存下一地址 -> 释放当前节点 -> 移动到下一地址。最后，必须设置 *pphead = NULL，以清除外部对已销毁链表的引用。

源码：

// SLNodeDestroy: 销毁链表
void SLNodeDestroy(SLNode** pphead)
{
    assert(pphead);
    SLNode* current = *pphead;
    // 循环直到 current 为 NULL
    while (current != NULL)
    {
        // 1. 关键一步：提前保存下一个节点的地址
        SLNode* nextNode = current->next; 
        // 2. 释放当前节点的内存
        free(current);                     
        // 3. current 移动到下一个节点
        current = nextNode;                
    }
    // 4. 最后必须将链表头指针置为 NULL，表示链表已空
    *pphead = NULL; 
}

12. 打印链表 (SLNodePrint)

思路： 从头节点开始，用工作指针

循环遍历链表。每次循环打印当前节点的数据，并将

移动到下一个节点（pcur = pcur->next）。循环直到

为 NULL。

注意事项： 打印风格：通常在结尾打印 NULL，以清晰表示链表的结束。

源码：

// SLNodePrint: 打印链表
void SLNodePrint(SLNode* phead)
{
	// 记录当前节点
	SLNode* pcur = phead;
	printf("链表元素：");
	// 循环条件：pcur 不为 NULL，即当前节点存在
	while (pcur)
	{
		printf("%d->", pcur->data);
		// 移动到下一个节点
		pcur = pcur->next;
	}
	printf("NULL\n"); // 链表末尾的标志
}

三、深度解析：为什么操作单链表需要传二级指针

二级指针在链表操作中的使用，是为了在函数内部彻底改变链表头指针变量（通常命名为

或

）本身所存储的值。

要理解这一点，必须先从C语言的值传递机制入手，也可以参考我的C语言专栏，里面也有相关介绍。

1. C语言的值传递特性（Pass by Value）

在 C 语言中，函数参数的传递总是值传递。这意味着当你调用一个函数时，函数会为所有参数创建一份副本。

错误做法：传入一级指针

假设主函数中有一个头指针变量 phead，它存储着第一个节点的地址

。

如果你调用一个函数 void SLNodePushFront(SLNode* phead, ...)：

1. 传参：函数内部会创建一个局部变量

，并将

的值（

）复制给它。

1. 操作：在函数内部，你对

进行了修改，比如让它指向新节点

。

1. 返回：函数执行完毕，

局部变量被销毁。

结果：你修改的只是

的一个副本。主函数中的原始

变量仍然存储着旧的地址

，链表头部没有真正被更新。新节点虽然被创建，但它没有成为链表的一部分，导致新节点丢失，这部分内容也可以参考我的函数栈帧博客内容。

2. 核心目标：修改指针变量本身

我们需要的不是修改

所指向的内存（即节点数据），而是需要修改

这个变量本身所存储的地址值。

修改节点内部的数据或

头指针

SLNode *第一个节点的地址 (

)

修改

变量，让它存储新地址（如

）

要修改内存地址

处存储的内容（即

变量的值），我们必须知道

这个地址。

3. 解决方案：传入指针的地址

这就是二级指针（指向指针的指针）的作用：

1. 传入：我们将

变量的地址（即

）作为参数传入函数：SLNodePopFront(&phead);。

1. 接收：函数用 SLNode** pphead 来接收这个地址

。此时：

• pphead 存储

（

的地址）。

• *pphead 访问

处的内容，即

变量本身存储的值

。

• **pphead 访问

处的内容，即第一个节点。

关键步骤：修改

当我们执行头删操作时，我们需要让

指向原第二个节点

。

我们通过解引用

来访问

变量：

// temp 存储原头节点 0x1000
SLNode* temp = *pphead; 
// *pphead 指向 phead 变量本身（地址 0xF000）
// 我们将 temp->next (原第二个节点的地址) 赋值给 phead 变量
*pphead = temp->next;

通过这一步赋值，我们成功地间接修改了主函数中

变量的值，实现了链表头部的更新。

4. 总结：哪些操作必须使用二级指针？

只要操作可能导致链表的起始点发生变化，就必须使用二级指针。

1. 头插 (SLNodePushFront)：新节点成为链表的第一个节点，必须修改

。

1. 头删 (SLNodePopFront)：原第二个节点成为新的头节点，必须修改

。

1. 删除指定节点 (SLNodeErasw)：如果删除的恰好是头节点

，则必须修改

。

1. 指定位置前插入 (SLNodeInsert)：如果

是头节点，则退化为头插，必须修改

。

1. 销毁链表 (SLNodeDestroy)：销毁后必须将

置为 NULL，表示链表不存在，必须修改

。

对于遍历、查找、指定位置后插入 (SLNodeInsertAfter) 和删除指定位置后节点 (SLNodeEraseAfter) 等操作，它们只涉及修改内部节点的

指针，或者只读取数据，不涉及修改

变量本身，因此只需要传入一级指针。

四、总结延伸与学习建议

1. 关键知识点回顾

存储下一个节点的地址。原理逻辑连续，物理不连续。所有操作都是对指针变量的修改。C/C++要点节点的内存需动态申请和释放。

和

必须成对出现。边界条件空链表 (

) 和尾节点 (

)。处理链表问题时要优先检查边界条件。

2. 学习建议

1. 可视化思维：画图比写代码重要一百倍！ 在纸上画出节点A、B、C，然后画出指针如何断开和重新连接，再动笔写代码。
2. 二级指针 Node **pphead：这是C语言的难点。当你需要在函数内部修改

指针本身时（即

指向了新的节点），必须传入

的地址。

1. 调试追踪：使用调试工具一步一步观察指针变量的值（地址）是如何变化的，能帮你彻底理解链表的精髓。

3. 两个思考问题

1. 哨兵节点：如果我们在链表头部增加一个不存储数据的“哨兵”头节点，头插和头删操作的代码会发生什么变化？（提示：

永远不会为

了。）

1. 删除指定节点：如果不给你

的前驱节点，只给你一个要删除的节点

，你如何实现

的时间复杂度删除它？（提示：考虑“偷天换日”法。）