C语言单链表核心接口实现详解：从结构定义到增删查改

周予安

发布时间：2026-10-16 | 4人浏览过

原创

单链表是C语言数据结构中处理动态数据的核心容器。与顺序表不同，它在物理上非连续，通过指针链接逻辑序列，有效解决了频繁扩容带来的空间浪费问题。本文深入解析单链表的节点定义，并逐一拆解遍历、头尾插入/删除及任意位置修改等接口的完整实现代码，特别强调二级指针在维护链表完整性中的关键作用。

一、链表的概念与节点结构

链表（Linked List）是一种物理存储单元上非连续、非顺序的存储结构。其数据的逻辑顺序是通过链表中的指针链接次序实现的。每个节点包含两部分：data 字段存储数据元素，next 字段指向下一个节点的地址。最后一个节点的 next 指向 NULL，作为链表的结束标记。

为了便于后续扩展数据类型并提高可读性，通常使用结构体和宏定义来封装节点：

typedef int SLTDataType;
typedef struct SlistNode
{
	SLTDataType data;
	struct SlistNode* next;
}SLTNode;

如图所示，链表的每个位置存放当前数据与下一个节点的地址。要访问整条链表，只需持有指向第一个节点（头节点）的指针即可。若为空链表，该指针为 NULL。

二、核心接口实现细节

第1步：遍历整个链表

目的：输出或检查链表中的所有元素。
入口：指向头节点的指针 phead。
动作：创建临时指针 cur 初始化指向首节点，循环直至 cur == NULL。每次访问后移动 cur = cur->next。

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

第2步：尾插节点

目的：在链表末尾添加新数据。
入口：指向头指针的二级指针 **pphead 和新数据 x。
参数：必须使用二级指针，因为当链表为空时，需要修改实参中的头指针指向新节点；若仅传一级指针，无法改变外部头指针的值。
步骤： 1. malloc 开辟新节点空间并初始化。
2. 判空：若原链表为空，直接将头指针指向新节点。
3. 遍历找到尾部节点（tail->next == NULL），将尾部的 next 指向新节点。

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (!newnode) { perror("malloc"); return; }
	
	newnode->data = x;
	newnode->next = NULL;
	
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

第3步：头插节点

目的：在链表头部插入新数据。
动作：新节点的 next 指向当前头节点，然后更新头指针为新节点地址。

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (!newnode) { perror("malloc"); return; }
	
	newnode->data = x;
	newnode->next = *pphead;
	*pphead = newnode;
}

第4步：头删节点

目的：移除链表第一个节点。
风险提醒：直接释放头节点会导致丢失后续所有节点的地址。必须先保存第二个节点的地址，再释放头节点，最后更新头指针。

void SListPopFront(SLTNode** pphead)
{
	assert(*pphead); // 确保链表非空
	
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

第5步：尾删节点

目的：移除链表最后一个节点。
关键点：需找到倒数第二个节点（prev）和最后一个节点（tail）。释放 tail 后，将 prev->next 置为 NULL。需特殊处理只有一个节点的情况，此时直接释放并将头指针置空。

void SListPopBack(SLTNode** pphead)
{
	if (*pphead == NULL) return;
	
	// 只有一个节点的特殊情况
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

第6步：查找指定节点

目的：在链表中查找值为 x 的节点，返回其地址，用于后续插入或删除定位。
动作：从头节点开始逐个比对数据域，找到即返回，未找到返回 NULL。

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

第7步：在指定位置前插入

目的：在找到的节点 pos 之前插入新数据 x。
逻辑：因为是单向链表，无法直接通过 pos 找到前驱。需要从头部遍历找到 pos 的前一个节点 prev。先将 prev->next 指向新节点，再将新节点的 next 指向 pos。

void SListInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	if (*pphead == pos) // 插在头部，复用头插逻辑
	{
		SListPushFront(pphead, x);
		return;
	}
	
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = pos;
	prev->next = newnode;
}

第8步：删除指定位置的节点

目的：删除找到的节点 pos。
逻辑：同样需找到 pos 的前驱节点 prev。将 prev->next 指向 pos->next，断开连接后 free(pos)。

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	if (*pphead == pos) // 删除头节点
	{
		SListPopFront(pphead);
		return;
	}
	
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	
	prev->next = pos->next;
	free(pos);
}