单链表核心操作全实现
单链表是数据结构中最基础也最核心的线性表之一。熟练掌握其查找、指定位置插入与删除等操作,是深入学习算法与数据结构的关键一步。本文将从零实现单链表的常用接口,详细拆解每一步思路与代码细节,帮助大家真正理解指针操作与链表结构。
查找操作
查找的逻辑很直观:维护一个游标 pcur,从头结点开始向后遍历。当 pcur 不为空时进入循环,检查当前节点数据是否等于目标值。如果相等则返回该节点;否则将 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)。
指定位置前后插入元素
在指定位置之前插入
要在 pos 之前插入新节点,我们需要找到 pos 的前驱节点 prev。让 prev->next 指向新节点,新节点的 next 指向 pos。如何找到 prev?从头结点开始遍历,直到 prev->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(n),但在特定场景下可优化至 O(1)。
在指定位置之后插入
在 pos 之后插入相对简单。我们只需要创建一个新节点,将其 next 指向 pos->next,然后让 pos->next 指向新节点。因为只涉及 pos 及其后继,无需遍历,所以只需传入 pos 指针即可。
// 在指定位置之后插入
{
assert(pphead && pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}


