C语言单链表基础操作：从头到尾实现增删查改

单链表的核心概念与分类

链表（Linked List）是一种物理存储单元上非连续、非顺序的存储结构。与数组（顺序表）不同，链表通过“指针”将各节点串联起来，因此不需要预先分配连续的内存空间，插入和删除元素时无需移动大量数据，时间复杂度为 O(1)（已知位置情况下）。但其随机访问性能较差，且额外的指针域会占用少量内存。

链表的常见形态

在实际开发和学习中，链表根据方向、循环特性和头结点的存在与否，可分为多种类型：

• 单向 vs 双向：单向链表只能向后遍历；双向链表每个节点包含前驱和后继两个指针。
• 循环 vs 非循环：循环链表的尾节点指向头节点，形成闭环；普通链表尾节点指向 NULL。
• 带头 vs 不带头结点：头结点（Head Node）是一个不存储有效数据的哑节点，位于首元节点之前。使用带头结点的链表可以简化空表和第一个节点的边界处理，但并非所有场景都必须使用。

单链表的C语言实现步骤

接下来我们将实现一个不带头结点的单向非循环链表。环境以 VS2019 为例，建议在编写每个功能函数后独立测试，以便快速定位Bug。

第1步：定义结构体与数据类型

我们需要定义节点的结构，包含数据域和指向下一个节点的指针域。为了方便后续扩展和数据类型的修改，通常使用 typedef 重命名。

#include <stdio.h>
#include <stdlib.h>

typedef int SLTDataType;

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

第2步：封装新节点创建函数

频繁的 malloc 操作会使代码臃肿，建议封装成专用函数。注意：新节点的 next 指针必须初始化为 NULL，否则其值为随机垃圾值，极易导致程序崩溃。

// 创建新节点
SLTNode* BuySListNode(SLTDataType x) {
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL) {
		// 实际项目中应检查内存分配是否成功
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

第3步：实现打印功能

打印功能是调试的基础。我们采用 > 符号连接数据，最后输出 NULL 以标识链表结束。

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

第4步：实现头插与尾插

在讨论插入操作时，必须先理解为什么参数需要二级指针 SLTNode** pphead。因为当链表为空或需要在头部插入时，我们需要改变 phead 本身的指向（即改变实参），而传一级指针只能通过形参修改变量内容，无法修改变量地址。只有通过二级指针，才能在函数内部修改调用者持有的头指针地址。

尾插 (Push Back)

找到最后一个节点（其 next 为 NULL），将其指向新节点。若原链表为空，则直接将头指针指向新节点。

// 尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else {
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

头插 (Push Front)

比尾插简单得多。新节点的 next 指向当前头节点，然后更新头指针指向新节点。

// 头插 
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

第5步：实现头删与尾删

删除操作同样涉及二级指针，且在 free 内存后务必将指针置为 NULL，防止产生野指针。

头删 (Pop Front)

记录第二个节点的地址 -> 释放第一个节点 -> 更新头指针。

// 头删
void SListpopFront(SLTNode** pphead)
{
	// 防御性编程：检查链表是否为空
	if (*pphead == NULL) return;
	
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

尾删 (Pop Back)

分为三种情况： 1. 链表为空：直接返回。 2. 链表只有一个节点：释放该节点并将头指针置为 NULL。 3. 多个节点：找到倒数第二个节点，释放最后一个节点，将倒数第二个节点的 next 置为 NULL。

// 尾删
void SListPopBack(SLTNode** pphead)
{
	// 1. 链表为空
	if (*pphead == NULL)
	{
		return;
	}
	// 2. 只有一个结点
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	// 3. 有一个以上的结点
	else {
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		// 找倒数第二个节点
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail); // 释放尾节点
		prev->next = NULL; // 断开链接
	}
}

第6步：查找、插入与删除指定节点

查找 (Find)

从头开始遍历，比较数据域。注意该函数通常只需要一级指针，因为它不修改链表结构。

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

在 pos 前面插入 (Insert Before)

由于是单向链表，无法直接从 pos 反向找到前驱。因此必须从头遍历寻找 pos 的前一个节点。如果 pos 就是头节点，则复用头插逻辑。

// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	if (pos == *pphead) {
		SListPushFront(pphead,x);
	}
	else {
		SLTNode* newnode = BuySListNode(x);
		SLTNode* prev = *pphead;
		// 寻找pos的前驱节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		// 执行插入
		prev->next = newnode;
		newnode->next = pos;
	}
}

删除指定位置 pos (Erase)

同样先判断 pos 是否为头节点（利用现成的头删函数），否则寻找前驱节点，让前驱的 next 跳过 pos，然后释放 pos。

// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	if (pos == *pphead)
	{
		SListpopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		// 断链并释放
		prev->next = pos->next;
		free(pos);
	}
}

完整测试与总结

编写 main 函数进行综合测试，验证头尾插删的正确性。

void TestSList1()
{
	SLTNode* plist = NULL; // 初始为空链表
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 0);
	
	printf("After Push: ");
	SListPrint(plist); // 预期: 0->1->2->3->4->NULL

	// 测试删除
	SListPopBack(&plist); // 尾删 4
	SListPopFront(&plist); // 头删 0
	
	printf("After Pop: ");
	SListPrint(plist); // 预期: 1->2->3->NULL
}

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

关键点回顾

在实际使用中，除了掌握上述基本操作外，还需注意以下问题：

• 内存泄漏：链表使用完毕后，必须编写函数遍历整个链表并 free 每一个节点，最后将头指针置空。
• 野指针：释放节点后，切勿再次使用该节点的指针，务必立即置 NULL。
• 判空保护：在进行 SListpopFront 或访问节点成员前，务必检查指针是否为 NULL。