C语言单链表核心操作与实现详解

单链表结构与分类

链表是一种物理存储单元上非连续、非顺序的存储结构。根据方向可分为单向或双向；根据是否包含虚拟头节点可分为带头或不带头；根据首尾连接情况可分为循环或非循环。综合来看共有八种类型，本文将重点讲解最基础的不带头节点的非循环单链表。

单链表的每个节点由两部分组成：

• 数据域：存放实际数据。
• 指针域：指向下一个节点的地址。

通常使用一个头指针 plist 指向链表的第一个节点，最后一个节点的指针域设为 NULL。

#define DataType int
typedef struct SListNode
{
	DataType data;   // 数据域
	struct SListNode *next; // 指向下一个节点的指针
}SListNode;

单链表核心操作

第1步：创建节点

由于链表是逻辑连续而非物理连续的，需要为每个新节点单独在堆区申请内存。若在栈区申请，函数结束后空间会被释放导致悬垂指针。

SListNode* BuySListNode(DataType x)
{
	SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
	if (plist == NULL)
	{
		return NULL; // 内存申请失败处理
	}
	plist->data = x;
	plist->next = NULL;
	return plist;
}

第2步：打印链表

遍历链表并输出数据，用于验证后续操作的正确性。

void SListPrint(SListNode* plist)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur)
	{
		printf("%d-->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

第3步：尾插法（PushBack）

将新节点添加到链表末尾。注意因为要改变头指针 *pplist 的指向（尤其是空表时），参数必须传入二级指针。

1. 若链表为空（*pplist == NULL），直接将头指针指向新节点。
2. 若链表不为空，遍历找到最后一个节点（cur->next == NULL）。
3. 将最后一个节点的 next 指向新节点。

void SListPushBack(SListNode** pplist, DataType x)
{
	assert(pplist);
	if (*pplist == NULL)
	{
		*pplist = BuySListNode(x);
	}
	else {
		SListNode* cur = *pplist;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = BuySListNode(x);
	}
}

第4步：头插法（PushFront）

将新节点添加到链表头部。头插法的优势在于无论链表是否为空，逻辑均可统一，无需分支判断。

1. 创建新节点。
2. 令新节点的 next 指向当前的头节点 *pplist。
3. 更新头指针 *pplist 指向新节点。

void SListPushFront(SListNode** pplist, DataType x)
{
	assert(pplist);
	SListNode* node = BuySListNode(x);
	node->next = *pplist;
	*pplist = node;
}

第5步：尾删法（PopBack）

删除链表最后一个节点。需特别处理链表为空、仅有一个节点和多个节点三种情况，且必须找到倒数第二个节点来断开连接。

1. 空表：直接返回。
2. 单节点：释放该节点，并将头指针置为 NULL。
3. 多节点：使用双指针（prev 和 cur）遍历，当 cur 指向尾部时，prev 即为前驱。将 prev->next 置空，释放 cur 的空间。

void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	if (*pplist == NULL)
	{
		return;
	}
	else if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* prev = NULL;
		SListNode* cur = *pplist;
		while (cur->next)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = NULL;
		free(cur);
	}
}

第6步：头删法（PopFront）

删除链表第一个节点。同样需要注意保存原头节点的指针以进行释放，防止内存泄漏。

1. 保存当前头节点指针。
2. 头指针指向第二个节点（delNode->next）。
3. 释放保存的原头节点空间。

void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	if (*pplist != NULL)
	{
		SListNode* delNode = *pplist;
		*pplist = delNode->next;
		free(delNode);
	}
}

第7步：查找元素

遍历链表寻找值为 x 的节点，返回其地址，未找到返回 NULL。

SListNode* SListFind(SListNode* plist, DataType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

第8步：任意位置后插入

由于单链表只能单向访问，无法通过给定节点 pos 找到其前驱，因此只能在指定节点之后插入。

1. 创建新节点。
2. 新节点的 next 指向 pos->next。
3. pos 的 next 指向新节点。

void SListInsertAfter(SListNode* pos, DataType x)
{
	assert(pos);
	SListNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

第9步：任意位置后删除

同理，只能删除指定节点 pos 之后的节点。

void SListDeleteAfter(SListNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return; // 无后继节点可删
	}
	SListNode* temp = pos->next;
	pos->next = temp->next;
	free(temp);
}

第10步：销毁链表

遍历整个链表，逐个释放节点内存，最后将头指针置空。

void SListDestroy(SListNode** pplist)
{
	assert(pplist);
	SListNode* cur = *pplist;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pplist = NULL;
}

总结

掌握单链表的操作核心在于理解指针的指向变化。特别是在插入和删除操作中，务必理清“先连后断”或“保存旧指针再更新”的顺序，以避免断链或内存泄漏。以上就是C语言单链表基本操作的详细内容，更多关于C语言数据结构优化的资料请关注本站其它相关文章！