C++单链表实现全解：从节点定义到核心操作与边界处理

一. 节点声明与内存分配基础

链表的核心在于非连续的内存存储。每个节点内部必须包含存储数据的域以及指向下一个节点地址的指针。当最后一个节点的 Next 指针置为 NULL 时，即表示链表结束。

为了便于后续扩展（例如修改数据类型），我们通常将数据存储类型定义为宏或别名。SLNode 结构体包含 data 字段和指向自身的指针域 Next：

typedef int ListDataType;

typedef struct SListNode
{
	ListDataType  data;
	struct SListNode* Next;
} SLNode;

二. 尾部插入 (Tail Insertion)

尾部插入要求找到当前链表的末尾（Next 为 NULL 的节点），并将其指向新创建的节点。在实际开发中，需要首先封装一个通用的创建节点函数，以便复用内存申请逻辑并统一错误处理。

第1步：封装节点创建函数

所有涉及插入的操作都需要新建节点。我们将 malloc 申请空间和赋初值的逻辑提取出来：

//创建节点
SLNode* SListCreateNode(ListDataType x)
{
	//新开辟一个节点
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (newNode == NULL)
	{
		//空间开辟失败
		printf("SListCreateNode::newNode malloc failed");
		exit(-1);
	}
	newNode->data = x;
	newNode->Next = NULL; 
	return newNode;
}

第2步：实现尾插逻辑

在调用 SListCreateNode 生成新节点后，需要处理两种情况：链表为空和链表非空。若直接对空指针进行解引用遍历会导致崩溃。

//尾部数据插入
void SListPushBack(SLNode** phead, ListDataType x)
{
	SLNode* newNode = SListCreateNode(x);

	//关键判断：当前链表是否为空
	if (*phead == NULL)
	{
		*phead = newNode;
		return;
	}

	//寻找最后一个节点
	SLNode* cru = *phead;
	while (cru->Next != NULL)
	{
		cru = cru->Next;
	}
	//尾节点接入新节点
	cru->Next = newNode; 
}

三. 链表打印 (Traversal)

为了验证后续操作的准确性，我们需要按顺序访问所有节点直至 NULL：

//链表打印
void SListPrint(SLNode* head)
{
	SLNode* cru = head;
	while (cru)
	{
		printf("%d->", cru->data);
		cru = cru->Next;
	}
	printf("NULL\n");
}

四. 头部插入 (Head Insertion)

头插法的逻辑更直接：新节点成为新的首元素，其 Next 指向旧的第一个节点。

//头部数据插入
void SListPushFront(SLNode** phead, ListDataType x)
{
	SLNode* newNode = SListCreateNode(x);
	//新节点指向原头节点
	newNode->Next = *phead;
	//更新头指针
	*phead = newNode;
}

五. 尾部删除 (Tail Deletion) 与边界排错

尾删是初学者最容易出错的操作。不仅要释放尾节点内存，还必须防止前驱节点变成野指针。以下展示了如何通过迭代排查发现并修复三个层级的潜在 Bug：

第一版：未处理空链表

如果链表不存在，传入的空指针会被误用，导致程序崩溃。需加入 assert(*phead) 或在调用前判空。

第二版：未处理仅有一个节点的情况

假设链表只有一个节点，while(cru->Next) 循环不会执行，prve 保持为 NULL。随后执行 prve->Next = NULL 时会产生空指针解引用错误。

第三版：修正后的稳健实现

//尾部数据删除
void SListPopBack(SLNode** phead)
{
	assert(*phead); //防御性断言

	//特判：链表中只有一个节点
	if ((*phead)->Next == NULL) 
	{ 
		free(*phead);
		*phead = NULL; //彻底断开头指针引用
		return;
	}

	SLNode* cru = *phead; 
	SLNode* prve = NULL; 

	//找到倒数第二个节点
	while (cru->Next) 
	{
		prve = cru;
		cru = cru->Next;
	}
	//此时 cru 指向最后一个节点，prve 指向前一个
	free(cru);          
	prve->Next = NULL;  
}

六. 头部删除 (Head Deletion)

头删相对简单，但需注意：必须先保存 NextNode 的地址，否则释放掉头节点后将无法找到后继节点。

//头部数据删除
void SListPopFront(SLNode** phead)
{
	assert(*phead);
	//暂存下一节点地址
	SLNode* NextNode = (*phead)->Next;
	//释放当前头节点
	free(*phead);  
	//更新头指针
	*phead = NextNode;
}

七. 查找指定节点 (Find Node)

从头遍历，比较节点值与目标值 x，若匹配则返回该节点指针；若遍历完仍未找到，返回 NULL。

SLNode* SListFindNode(SLNode* head, ListDataType x)
{
	SLNode* cru = head;
	while (cru)
	{
		if (cru->data == x) return cru;
		cru = cru->Next;
	}
	return NULL;
}

八. 指定位置前插 (Insert Before Pos)

由于单向链表缺乏前驱指针，要在 pos 之前插入，必须先找到 pos 的前一个节点。

void SListInsert(SLNode** phead, SLNode* pos, ListDataType x)
{
	assert(pos);
	
	//优化：如果 pos 就是头节点，直接使用已有的头插逻辑
	if (*phead == pos)
	{
		SListPushFront(phead, x);
		return;
	}
	
	//寻找 pos 的前驱节点 cru
	SLNode* cru = *phead;
	while (cru->Next != pos)
	{
		cru = cru->Next;
	}
	//建立连接：cru -> NewNode -> pos
	SLNode* newNode = SListCreateNode(x);
	newNode->Next = pos;
	cru->Next = newNode;
}

九. 指定位置删除 (Ease/Delete Node)

类似于指定插入，需定位到待删除节点的前驱，将其 Next 指向待删节点的 Next，最后释放内存。同样需要处理 pos 为头节点的特殊分支。

void SListEase(SLNode** phead, SLNode* pos)
{
	assert(pos);
	//若删除的是头节点，直接复用头删逻辑
	if (*phead == pos)
	{
		SListPopFront(phead);
		return;
	}

	SLNode* cru = *phead;
	//定位到 pos 的前一个节点
	while (cru->Next != pos)
	{
		cru = cru->Next;
	}
	//绕过 pos 节点
	cru->Next = pos->Next;
	free(pos);
	pos = NULL;
}

十. 销毁链表 (Destroy)

防止内存泄漏，必须逐个释放节点内存。注意不要在一次 free 后立即使用被释放的指针，需借助临时变量保存下个节点的地址。

void SListDestroy(SLNode** phead)
{
	SLNode* cru = NULL;
	while (*phead)
	{
		cru = (*phead)->Next; //先保存下一个的地址
		*phead = NULL;        //当前节点置空
		free(*phead);         //释放当前节点
		*phead = cru;         //指针后移
	}
}