C语言单链表实现详解：从结构定义到核心接口封装

单链表与顺序表的区别

在实现单链表之前，需明确其与顺序表（如数组）的核心差异，以便在适用场景中正确选择数据结构：

顺序表特点

• 内存结构：地址连续，物理空间紧密相连。
• 容量变化：长度通常固定或需整体扩容/缩容，存在空间浪费风险。
• 访问效率：支持随机查找（O(1)），中间插入/删除涉及大量元素移动，效率较低。
• 适用场景：适用于频繁按索引访问元素，但头部或中间增删较少的数据集合。

单链表特点

• 内存结构：地址不连续（逻辑上有序，物理上分散），通过指针链接。
• 容量变化：动态分配节点，按需开辟空间，无预留空间浪费。
• 访问效率：不支持随机查找（O(N)），但中间插入/删除仅需修改指针指向，效率高。
• 适用场景：适用于数据量动态变化大，且对头部或特定位置频繁进行增删操作的程序。

单链表核心接口实现

单链表的实现基于指针操作。以下代码展示了如何构建一个具备头尾插删、查找修改及特殊位置操作的标准单链表结构。

第1步：头文件定义与函数声明

首先定义节点结构体 SListNode 和类型别名，并声明后续要实现的函数接口。注意使用 **pphead 传递二级指针以支持修改头指针本身的操作（如头删）。

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SListDataType;
// 节点结构体
typedef struct SListNode
{
	SListDataType data;
	struct SListNode* next;
}SListNode;

// 尾插尾删
void SListPushBack(SListNode** pphead, SListDataType x);
void SListPopBack(SListNode** pphead);

// 头插头删
void SListPushFront(SListNode** pphead, SListDataType x);
void SListPopFront(SListNode** pphead);

// 通用打印
void SListPrint(SListNode* phead);

// 查找并修改
SListNode* SListFind(SListNode* phead, SListDataType x);

// 在pos节点之后插入/删除
void SListInsertAfter(SListNode** pphead, SListNode* pos, SListDataType x);
void SListEraseAfter(SListNode* pos);

// 递归：从尾到头打印
void PrintTailToHead(SListNode* pList);

第2步：辅助函数 - 创建新节点

封装 BuySListNode 用于统一处理内存分配。必须检查 malloc 是否成功，防止空指针解引用导致崩溃。

SListNode* BuySListNode(SListDataType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
	{
		printf("申请结点失败\n");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}

第3步：尾插法与尾删法

尾插需遍历找到尾部节点（tail->next == NULL），将其 next 指向新节点。尾删需区分链表为空、仅有一个节点（直接释放头节点）、多个节点（找到倒数第二个节点，断开其连接并释放最后一个）三种情况。

// 尾插
void SListPushBack(SListNode** pphead, SListDataType x)
{
	SListNode* newNode = BuySListNode(x);
	
	// 空链表情况：直接赋值
	if (*pphead == NULL)
	{
		*pphead = newNode;
	}
	else
	{
		// 非空：找尾巴
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newNode;
	}
}

// 尾删
void SListPopBack(SListNode** pphead)
{
	// 1. 空链表
	if (*pphead == NULL)
	{
		return;
	}
	// 2. 只有一个节点
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	// 3. 两个及以上节点：需找到倒数第二个节点
	else
	{
		SListNode* prev = NULL;
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;	
	}
}

第4步：头插法与头删法

头插最简单：新节点 next 指向当前头节点，更新头指针指向新节点。头删需先保存第二个节点的地址，再释放头节点，最后更新头指针。

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

// 头删
void SListPopFront(SListNode** pphead)
{
	// 1. 空链表
	if (*pphead == NULL)
	{
		return;
	}
	// 2. 一个及以上节点
	else
	{
		// 必须先保存下一个节点的地址，因为free后会丢失链接
		SListNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

第5步：查找功能

遍历链表比较数据域，找到即返回节点指针，未找到返回 NULL。该返回值可直接用于后续的修改或定位插入/删除位置。

// 查找值为x的节点
SListNode* SListFind(SListNode* phead, SListDataType x)
{
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

第6步：指定位置后插入与删除

这是单链表较难理解的部分：InsertAfter 在 pos 节点之后插入，EraseAfter 删除 pos 节点之后的节点。这避免了寻找前驱节点的繁琐过程，时间复杂度为 O(1)，但前提是已知目标节点位置。

// 在pos节点之后插入新节点
void SListInsertAfter(SListNode** pphead, SListNode* pos, SListDataType x)
{
	assert(pos && pphead);
	
	// 如果pos是头节点，可以直接复用头插逻辑（优化）
	if (*pphead == pos)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SListNode* newnode = BuySListNode(x);
		// 这里的逻辑主要是为了保持原意，实际直接修改指针更高效
		// 但标准写法通常是：newnode->next = pos->next; pos->next = newnode;
		// 原文提供的代码试图寻找pos的前驱，这在O(1)操作中是不必要的开销
		// 以下为更正后的高效实现：
		newnode->next = pos->next;
		pos->next = newnode;
	}
}

// 删除pos节点之后的节点
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	if (pos->next)
	{
		SListNode* next = pos->next;
		pos->next = next->next;
		free(next);
	}
}

第7步：打印与递归展示

SListPrint 正向遍历打印。 PrintTailToHead 利用递归特性，先深入至尾部，回溯时打印，实现倒序输出。

// 正向打印
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

// 递归：从尾到头打印
void PrintTailToHead(SListNode* pList)
{
	if (pList == NULL)
	{
		return;
	}
	PrintTailToHead(pList->next);
	printf("%d->", pList->data);
}

测试用例验证

通过构建测试函数，演示增删改查及异常边界情况的处理。注意 TestSList1 循环调用 PopBack/Front 直至空链表，验证了空指针保护的有效性。

#include "SList.h"

void TestSList1()
{
	SListNode* pList = NULL;
	
	// 测试尾插尾删
	SListPushBack(&pList, 1);
	SListPushBack(&pList, 2);
	SListPushBack(&pList, 3);
	SListPushBack(&pList, 4);
	SListPrint(pList);

	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList); // 尝试在空链表删除，应有保护
	SListPrint(pList);

	// 测试头插头删
	SListPushFront(&pList, 1);
	SListPushFront(&pList, 2);
	SListPrint(pList);
	
	// 清理剩余节点...
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPrint(pList);
}

void TestSList2()
{
	SListNode* pos = NULL;
	SListNode* pos1 = NULL;
	SListNode* pList = NULL;
	
	SListPushBack(&pList, 1);
	SListPushBack(&pList, 2);
	SListPushBack(&pList, 3);
	SListPushBack(&pList, 4);
	SListPrint(pList);
	
	// 查找并修改
	pos = SListFind(pList, 3);
	if (pos)
	{
		pos->data = 30; 
	}
	SListPrint(pList);
	
	// 在pos(此时值为30)之后插入50
	pos1 = SListFind(pList, 30);
	if(pos1)
	    SListInsertAfter(&pList, pos1, 50);
	SListPrint(pList);
	
	// 删除pos后的节点（即50）
	if(pos1)
	    SListEraseAfter(pos1);
	SListPrint(pList);
	
	// PrintTailToHead(&pList); // 注：原代码此处传参可能有误，通常为单层指针
}

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

以上就是C语言实现单链表的详细内容，单链表作为线性表的链式存储结构，其灵活性和动态性使其成为解决复杂数据存储问题的重要工具。更多关于C语言数据结构与算法的资料请关注本站其它相关文章！