单链表核心操作全实现与深度解析
单链表是数据结构中最基础也最核心的线性表之一。熟练掌握其查找、指定位置插入与删除等操作，是深入学习算法与数据结构的关键一步。本文将从零实现单链表的常用接口，详细拆解每一步思路与代码细节，帮助大家真正理解指针操作与链表结构。
一、查找
思路：
遍历链表，pcur 指向头结点。循环判断 pcur 是否为空，若不为空则检查 pcur->data 是否等于目标值。若相等返回当前节点，否则将 pcur 移至下一个节点继续判断。若遍历结束仍未找到，返回 NULL。
代码：
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
SLTNode* pcur = phead;
while (pcur) {
if (pcur->data == x)
return pcur;
pcur = pcur->next;
}
return NULL;
}
时间复杂度： O(n)
二、指定位置之前或之后插入元素
2.1 在指定位置之前插入
思路：
首先需确保头文件非空且不在空位置前插入。找到 pos 的前一个结点 prev，让 prev->next 指向新节点 newnode，然后 newnode->next 指向 pos。若 pos 为头结点，则执行头插操作。
代码：
// 在指定位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
assert(pphead && pos);
// 只有一个节点或 pos 为头结点时，执行头插
if (pos == *pphead)
SLTPushFront(pphead, x);
else {
SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
prev = prev->next;
newnode->next = pos;
prev->next = newnode;
}
}
时间复杂度： O(1)（假设已定位到 pos）
2.2 在指定位置之后插入
思路：
直接修改指针：newnode->next = pos->next，然后 pos->next = newnode。无需遍历，只需传入 pos 即可。即使 pos 为尾结点也能正常工作。
代码：
{
assert(pphead && pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
