单链表头节点的作用

§ 401 单链表头节点的作用#

一、问题#

带头节点的单链表为什么要多加一个不存数据的空节点？它”统一了插入删除逻辑”到底统一在哪里？

二、为什么是这样#

单链表的插入和删除依赖前驱节点。在节点 p 后面插入新节点 s：

s->next = p->next;  // s 接上 p 的后继
p->next = s;        // p 指向 s

删除 p 的后继节点 q：

q = p->next;
p->next = q->next;  // 跳过 q
free(q);

这两个操作都以”前驱节点 p”为入口。问题在于：不带头节点时，第一个数据节点没有前驱，所以”在表头插入”和”删除第一个节点”就成了特殊情况——必须单独修改头指针 L，代码出现两条路径。

头节点是人为加在第一个数据节点前面的空节点：

带头节点：   L → [头节点] → [a1] → [a2] → NULL
不带头节点： L → [a1] → [a2] → NULL

有了头节点，a1 的前驱就是头节点。哪怕操作第 1 个位置（i=1），i-1=0 也有节点可找（头节点），代码只需一条路径：找到第 i-1 个节点，在它后面操作。

三、关联#

• 1.3 单链表：带头节点和不带头节点的具体代码对比
• 403-链表四种结构与操作核心：四种链表结构的整体对比

四、我的理解#

头节点像”固定站位的前驱”，它站在所有真实数据前面，让第一个节点不再特殊。

“统一”统一的是代码入口，不是时间复杂度（两种方案都是 $O(n)$）。带头节点后，任何位置的插入删除都走同一条逻辑：找前驱 → 操作。不带头节点时，表头操作必须单独写一段改头指针的代码。

头指针 vs 头节点 vs 首元节点：头指针是指针变量（指向链表起始位置）；头节点是一个实际分配的空节点；首元节点是第一个真实数据节点。有头节点时 L 指向头节点，L->next 才是首元节点。