带头结点的链表也就是大家常说的“有头链表”在Java面试和日常业务代码里出现的频率极高。很多人背了几遍链表增删改查的代码一遇到“头结点到底存不存数据”“为什么删除第一个节点不用特殊判断”这类问题就卡壳。这篇文章我会用Java完整实现一个带头结点的单链表把节点设计、插入删除、边界判断、与无头链表的区别一次讲透同时附上可直接运行的代码和一套边界测试用例适合Java初学者巩固数据结构基础也适合准备面试的同学拿来复盘。1. 有头链表到底是什么——为什么面试和工程里都绕不开它1.1 有头链表与无头链表的本质区别先搞清楚一个很多人纠结的问题带头结点的链表和不带头结点的链表区别到底在哪。不带头结点的单链表head变量本身就是第一个数据节点的引用。链表为空时head是null删除第一个节点时你必须写head head.next这种特殊逻辑。带头结点的单链表head指向的是一个永远存在的“哨兵节点”这个节点不存储业务数据或者存储链表长度等元信息。真正的第一个数据节点是head.next。链表为空时head.next为null但head本身永远不为null。这看起来只是多了一个节点却让所有操作的代码逻辑发生了质变。举一个最直观的例子在索引0位置插入节点。无头链表需要这样写if (index 0) { newNode.next head; head newNode; } else { // 从头往后找前驱节点 }有头链表不需要任何特判因为索引0位置的前驱节点就是head而head永远存在Node prev head; for (int i 0; i index; i) { prev prev.next; } newNode.next prev.next; prev.next newNode;这就是统一处理的价值。哨兵节点相当于给链表加了一个“永远存在的头杠”你插入、删除任何一个位置思路都是同一个模板找到前驱改两条指针。这样就消除了“空表特殊态”和“头部特殊态”两个最大的心智负担。1.2 头结点的价值从“空指针地狱”到统一处理我在初学链表时写无头版本最痛苦的就是边界条件链表为空时想插入怎么办删除后链表只剩一个节点怎么办遍历时current会不会变成null然后还去访问current.next。这些错误在运行时经常表现为NullPointerException排查起来很费劲。有头链表把“空态”也纳入统一逻辑之后很多边界问题自然消失。比如遍历打印Node current head.next; while (current ! null) { System.out.println(current.data); current current.next; }头结点是哨兵不存数据所以遍历起点天然是head.next遇到空链表head.next是null循环体一次都不执行安全退出。再比如求链表长度你只需要从head.next开始用一个计数器往后走走到null结束不需要像某些无头实现那样为head null单独返回0。从工程角度看头结点还让“链表对象的头引用不需要在插入删除时被重新赋值”。无头链表的头节点有可能在操作中被替换你必须把修改后的头引用一路传出去稍不留神就丢了链表有头链表的头结点固定不变你永远只需要操作head内部的next字段稳定性明显更好。这也是很多代码规范推荐带头结点实现的原因。2. 从零开始搭建节点与链表骨架2.1 节点类设计next指针与data字段链表的基础单元是节点。在Java中我们通常把节点类写成链表的内部静态类public class LinkedListWithHeadE { private static class NodeE { E data; NodeE next; Node(E data) { this.data data; this.next null; } } private NodeE head; private int size; public LinkedListWithHead() { head new Node(null); size 0; } }几个设计细节值得说清楚。next为什么是NodeE类型因为它是引用下一个节点本身就是指向节点对象的引用不需要也不应该用int或int[]来模拟“指针”Java的引用天然就承担了指针的作用。为什么节点类用static因为内部静态类不依赖外部类的实例我们在静态方法或初始化场景创建节点时更自由也不会因为内部类持有外部类引用而造成意料之外的内存驻留。在链表这种场景节点类只关心数据存储和引用关系静态内部类是最稳妥的选择。data字段声明为E也就是泛型参数这样链表可以存放任意类型的对象String、Integer、自己定义的业务类都能放进去。后面讲泛型设计时再展开。2.2 初始化与构造头结点应该存什么构造函数里head new Node(null)头结点的data存的是null。很多人问头结点的数据字段到底放什么正常约定就是放null因为它只是一个占位符不参与业务逻辑。你在遍历、查找、打印时一定要从head.next开始而不是从head开始否则就会把头结点里那个null当成有效数据处理。这是有头链表实现里最容易犯的低级错误我刚写时也在这翻过车。size字段记录当前链表的数据节点数量。这个字段不是可有可无的它能帮我们在插入、删除时做索引合法性校验还能让size()方法的时间复杂度稳定在 O(1)不需要每次遍历数一遍。代价是每次插入删除后要记得维护它忘掉size或size--会导致后续校验全部错乱。2.3 泛型设计为什么不用Object有些初学者图省事直接把节点里的数据字段声明为Object这样什么都能存但取出时就得强转Object data node.data; String name (String) data; // 丑而且运行时可能抛 ClassCastException用泛型E后存储和取出都有编译期类型检查LinkedListWithHeadString list new LinkedListWithHead(); list.addLast(Java); list.addLast(链表); String first list.get(0); // 直接拿 String无需强转一句话总结泛型把类型错误从运行期提前到了编译期而且代码干净得多。Java集合框架里的LinkedListE也是这么设计的我们照着优秀范例抄作业是不会错的。3. 核心操作一步步实现3.1 尾插与头插的选择链表的插入分头插和尾插这里先给两个简单的实现。头插法把新节点插到头结点后面public void addFirst(E data) { NodeE newNode new Node(data); newNode.next head.next; head.next newNode; size; }尾插法遍历到链表尾部再挂上去public void addLast(E data) { NodeE cur head; while (cur.next ! null) { cur cur.next; } cur.next new Node(data); size; }注意头插的顺序先让newNode.next指向head.next再把head.next指向newNode。如果反着来先把head.next改成newNode原来的第一个节点就再也找不到了链表就断掉了。这个顺序问题在链表的任何插入操作里都是重中之重。尾插的时间复杂度是 O(n)因为每次都要从头走到尾部。如果你需要频繁尾插建议额外维护一个tail尾指针这里为了保持单链表最基础的形态先不引入尾指针面试时如果你主动提到“可以用尾指针优化尾插”会是一个加分点。3.2 指定位置插入边界判断是灵魂指定位置插入是链表的标志性操作也是面试高频考点。它的完整实现是public void add(int index, E data) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } NodeE prev head; for (int i 0; i index; i) { prev prev.next; } NodeE newNode new Node(data); newNode.next prev.next; prev.next newNode; size; }我来逐行解释。先校验index的范围。为什么是index size而不是index size因为索引从0开始size代表元素个数插入时允许index size这表示在链表末尾追加一个节点。如果你只允许index size那尾插就必须用另一个方法逻辑就不统一了。然后从头结点向后走index步找到目标位置的前驱节点。注意这里遍历的起点是head不是head.next。为什么因为索引0位置的前驱就是头结点本身。如果我们从head.next开始走走到索引0位置时prev会是第一个数据节点那就没法在链表头部插入了。后面的两步操作newNode.next prev.next; prev.next newNode;这就是链表的经典“缝针”新节点先挂上后面的链表前驱节点再挂上新节点。顺序同样不能乱先处理newNode.next再处理prev.next否则链表会在插入点断开。从时间复杂度看定位是 O(n)插入本身是 O(1)。链表相比数组的核心优势就在这只要给你前驱节点的引用插入就是常数时间不需要像数组那样把后续元素整体后移。3.3 删除操作记得保住next引用删除指定位置的节点public E remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } NodeE prev head; for (int i 0; i index; i) { prev prev.next; } NodeE removed prev.next; prev.next removed.next; removed.next null; size--; return removed.data; }删除的边界校验使用index size因为索引最大到size - 1删除size位置的元素是不存在的。删除的思路同样很固定先找到前驱节点再把前驱的next跨过待删节点直接指向它的后继。有一个细节很多人忽略删除后最好把removed.next置为null。这有什么意义如果不置空被删除的节点还持有原后继节点的引用它可能会无谓地留在可达链上影响JVM垃圾回收的效率。虽然对现代JVM来说这种影响不一定会被立刻感知但养成随手断开引用的习惯总归是干净利落的。删除后别忘了size--并且返回被删节点的数据。返回数据这个动作不是可有可无的它让调用方可以拿到被删除的元素这在很多业务场景里都有用。3.4 遍历与查找循环条件别写错遍历逻辑是链表的“地基”后面很多操作都建立在它之上。基本遍历就是从head.next开始一直走到null结束public void print() { NodeE cur head.next; StringBuilder sb new StringBuilder([); while (cur ! null) { sb.append(cur.data); if (cur.next ! null) { sb.append(, ); } cur cur.next; } sb.append(]); System.out.println(sb); }有个常见的错误写法是while (cur.next ! null)这样会丢掉最后一个节点不打印。要记住遍历整个链表时条件是cur ! null只有你需要“当前节点的下一个节点”做操作时才需要额外判断cur.next是否为null。按值查找元素返回索引位置public int indexOf(E data) { NodeE cur head.next; int index 0; while (cur ! null) { if (data null ? cur.data null : data.equals(cur.data)) { return index; } cur cur.next; index; } return -1; }这里用了一个小技巧data可能为null直接用data.equals(cur.data)会抛空指针。所以要先判断data是否为null。实际上Java 7以后提供了Objects.equals(data, cur.data)这个静态方法它内部帮你做了空值处理if (Objects.equals(data, cur.data)) { return index; }用Objects.equals代码更简洁语义也更清晰。查找的时间复杂度是 O(n)链表在随机访问上没有优势你要找第10个元素就得从头走9步这是链表结构本身的天然特点使用场景要充分考虑到这一点。4. 完整代码与测试用例4.1 完整实现代码把上面的核心操作整合起来得到一版可以直接编译运行的代码import java.util.Objects; public class LinkedListWithHeadE { private static class NodeE { E data; NodeE next; Node(E data) { this.data data; this.next null; } } private NodeE head; private int size; public LinkedListWithHead() { head new Node(null); size 0; } public int size() { return size; } public boolean isEmpty() { return size 0; } public void addFirst(E data) { NodeE newNode new Node(data); newNode.next head.next; head.next newNode; size; } public void addLast(E data) { NodeE cur head; while (cur.next ! null) { cur cur.next; } cur.next new Node(data); size; } public void add(int index, E data) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } NodeE prev head; for (int i 0; i index; i) { prev prev.next; } NodeE newNode new Node(data); newNode.next prev.next; prev.next newNode; size; } public E remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } NodeE prev head; for (int i 0; i index; i) { prev prev.next; } NodeE removed prev.next; prev.next removed.next; removed.next null; size--; return removed.data; } public E get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } NodeE cur head.next; for (int i 0; i index; i) { cur cur.next; } return cur.data; } public int indexOf(E data) { NodeE cur head.next; int index 0; while (cur ! null) { if (Objects.equals(data, cur.data)) { return index; } cur cur.next; index; } return -1; } public void print() { NodeE cur head.next; StringBuilder sb new StringBuilder([); while (cur ! null) { sb.append(cur.data); if (cur.next ! null) { sb.append(, ); } cur cur.next; } sb.append(]); System.out.println(sb); } }这段代码包含了插入头插、尾插、指定位置、删除、查询、遍历、查找等基本操作。从代码量上来说不多但每一行都有它存在的理由。你甚至可以把它当成一个“缩水版”的java.util.LinkedList源码预习思路几乎同源。4.2 测试用例怎么设计写数据结构光有实现还不够必须验证各种边界场景。我一般会按下面这套用例来测public class Demo { public static void main(String[] args) { LinkedListWithHeadString list new LinkedListWithHead(); list.print(); // 空链表期望输出 [] list.addLast(A); list.addLast(B); list.addLast(C); list.print(); // 期望输出 [A, B, C] list.addFirst(X); list.print(); // 期望输出 [X, A, B, C] list.add(2, M); list.print(); // 期望输出 [X, A, M, B, C] list.remove(0); list.print(); // 期望输出 [A, M, B, C] list.remove(list.size() - 1); list.print(); // 期望输出 [A, M, B] list.remove(1); list.print(); // 期望输出 [A, B] System.out.println(list.get(1)); // 期望输出 B System.out.println(list.indexOf(A)); // 期望输出 0 System.out.println(list.indexOf(Z)); // 期望输出 -1 list.add(0, Head); list.print(); // 期望输出 [Head, A, B] } }为什么测试用例里要有头插、尾插、中间插、头删、尾删、中间删这些组合因为链表最容易出错的恰恰是头尾和中点这些特殊位置。头部涉及头结点的处理尾部涉及cur.next null的判断中间位置涉及前驱定位的偏移是否正确。把这几个位置全跑一遍才能充分验证实现的正确性。另外我习惯在测试里故意传入非法索引比如add(-1, X)或者remove(999)确认程序会抛出IndexOutOfBoundsException。没有异常和错误异常是两码事——能正确抛出异常说明边界校验真正生效了。5. 有头链表的高频陷阱与面试热点5.1 空链表、单节点、尾节点的边界测试边界情况是链表实战中最容易翻车的地方。我整理了三个必测场景第一空链表。对空链表执行get(0)应当抛异常因为size 0index size成立。这一点代码里已经覆盖到了。第二单节点链表。链表只有一个节点时删除它之后链表应该重新变成空链表也就是说head.next回到null。我们的remove(0)执行后prev是headremoved是唯一的那个节点prev.next置为removed.next也就是null链表状态正确。第三尾节点。删除最后一个节点时前驱节点是倒数第二个节点removed.next本来就是null不存在失去引用的问题。相反如果删除的恰好是尾节点相当于把倒数第二个节点的next置为null链表长度减一。这三个场景恰好覆盖了链表的“空”、“少”、“尾”三种形态。在面试时如果面试官让你手写链表操作主动说出来“我需要考虑空链表和单节点这两种边界情况”也会显得你经验扎实。5.2 与循环链表、双向链表的对比有头链表带头结点单链表只是链表家族的一种面试中免不了被问到它和其他变体的比较。循环单链表tail.next指向头结点或第一个节点形成一个环。环的好处是从任何一个节点出发都能走到其他任意节点坏处是遍历时必须有一个安全计数器或用哨兵机制否则很容易死循环。如果面试官问如何判断一个链表是否有环经典做法是快慢指针——快指针每次走两步慢指针每次走一步如果有环它们最终会相遇无环时快指针先到null。这段经典逻辑在有头链表上同样适用因为快慢指针只看next引用与头结点是否存在不冲突。不带头结点的单链表我们开头已经详细对比过。无头版本的优点是少一个节点内存上略微节省缺点是代码逻辑要区分“是否第一个节点”整体代码反而更复杂。工程取向上我强烈建议默认用带头结点版本。双向链表每个节点有prev和next两个引用可以双向遍历。Java集合里的LinkedListE和LinkedHashMap内部就是双向链表结构删除节点时因为有prev指针不需要像单链表那样从头找前驱删除性能更好。但双向链表每个节点多一个引用字段内存开销更大。5.3 以有头链表为基础理解高频面试思想链表这部分面试题很多但核心思想总结起来就是两个词引用操作的顺序以及双指针运动节奏。引用操作的顺序我们已经在插入删除里反复强调过了——先挂新节点的next再改前驱的next。这个顺序对任何链表都通用包括反转链表public NodeE reverse(NodeE head) { NodeE prev null; NodeE cur head; while (cur ! null) { NodeE next cur.next; // 先保存后继不然后面会丢 cur.next prev; // 反转指针 prev cur; // 前驱前进 cur next; // 当前节点前进 } return prev; }这是面试必考题代码非常短但短不代表容易核心就在“先保存后继”这一个动作上。我见过不少人在白板上写反转链表写着写着就把next引用搞丢了最后链表从中间断开。反复练习这个思路等于把链表的引用操作练成了肌肉记忆。双指针运动节奏最常见的是快慢指针找中间节点。一个快指针一次走两步一个慢指针一次走一步快指针到链表尾部时慢指针恰好停在中间附近。这个思想在找链表中点、判环、找倒数第K个节点等题目里反复使用。你可以尝试给有头链表实现一个findMiddle()模拟两轮第一轮验证快指针每次走两步不会因为next为null而报错第二轮确认慢指针的位置。从学习路径上讲链表是最适合把“引用思维”练成直觉的数据结构。你把这个带头的单链表实现吃透再去看循环链表、双向链表、各种链表算法题都会发现底层逻辑是一致的区别只是多了几个指针或者多了一个环。这也是为什么几乎每一本数据结构教材、每一个面试突击资料都会把链表放在最前面来讲。它不是简单的“一个节点存数据加一个指针”那么肤浅它是一整套关于引用、边界条件、复杂度分析的思维训练。最后分享一个我自己的实操习惯每次写完链表的插入或删除方法我都会顺手在纸上画一遍指针变化图。不是那种完整的链表长图而是画局部几个节点的引用指向变化。比如插入时画newNode、prev、prev.next三个框标出每一步操作后谁指向谁。看起来笨但排查边界问题特别快。很多在代码层面绕来绕去的 bug在图上三秒钟就能看出是哪个引用没接上。这个方法推荐给你尤其是刚接触链表的时候多画几次图代码里的错误率会明显下降。