Java手写链表从零实现：核心逻辑与避坑指南-北京尧图网络

如果你写过一阵子Java大概率在面试题或者课程设计里碰上过这么一个问题手写一个链表。说实话我第一次被问到“用Java实现链表”的时候心里是有点懵的——毕竟日常开发里直接ArrayList和LinkedList拿来就用真没自己从头撸过。但恰恰是那次之后我发现能把链表手写明白的人对引用或者说指针的理解会比只会调API的人深一层排查线上问题、读框架源码的时候也明显更顺。这篇文章就从一个实际编码的角度掰开揉碎讲一讲Java链表数据结构的实现思路、边界情况还有我踩过的一些坑。很多教程喜欢一上来就甩代码然后说“你看很简单”。但我不太认同这个方式。链表这东西难点从来不是代码本身而是你脑子里有没有那张“节点引用”的图。你只要图想清楚了代码就是照着图翻译一遍图没想清楚代码写得再漂亮也是虚的。所以这篇文章我会先讲清楚链表的底层逻辑再给实现再讲为什么这么写最后聊聊那些真正让人头皮发麻的边界问题。1. 从数组的短板说起链表到底解决了什么问题1.1 数组的“连续内存”困局先说说为什么需要链表。数组在内存里是一段连续空间这既是它的优势也是它最大的限制。连续意味着可以通过下标直接计算地址所以随机访问是O(1)的但也正因为连续你在中间插入一个元素必须把后面的元素全部往后挪删除也一样。这个挪动操作在数据量小的时候无所谓十万级、百万级数据时就非常肉疼了。还有一个潜在问题扩容。ArrayList底层是数组当容量不够时它会新开一个更大的数组然后把旧数据拷贝过去。这个拷贝是O(n)的虽然均摊下来还能接受但在某些低延迟场景里那一次扩容的卡顿是真的明显。链表就没有这个问题它不需要一段连续内存每个节点独立存在用引用串起来就行理论上只要有零散内存就能用。1.2 链表的本质用引用串起来的离散节点链表的核心元素就两个节点和引用。每个节点保存两个东西——数据本身以及下一个节点的地址。在Java里这个“地址”表现为引用也就是我们常说的指针。public class ListNode { int val; ListNode next; ListNode(int val) { this.val val; } }你看就这么简单。一个val存数据一个next指向下一个节点。当next为null的时候说明这是链表的最后一个节点。链表的头节点是head它就像一列火车的车头通过next一级一级串过去就能访问到所有节点。理解链表的关键就是理解“引用”这层间接关系。每个节点只知道自己下一个节点是谁它不知道后面还有多少个节点也不知道链表的长度。想知道长度从头遍历一遍。想访问第5个节点从头走5步。这就是链表与数组最本质的差异数组是“按索引直达”链表是“按引用顺藤摸瓜”。2. 手写一个单链表从节点类到可用Demo的完整过程2.1 类的骨架设计我们不直接复制JDK的LinkedList而是从一个精简版开始。先定义一个链表类内部维护头节点head和大小size。public class MyLinkedList { private ListNode head; private int size; public MyLinkedList() { head null; size 0; } }head表示第一个节点size表示当前节点数量。可能有同学会问为什么不用虚拟头节点这里先不引入先让逻辑更直白一点。等会讲边界问题的时候我们再聊虚拟头节点的好处。2.2 从头部插入理解“换头”操作头部插入是最直观的操作。新节点来了它的next指向原来的head然后链表的新head换成这个新节点。这个操作的时间复杂度只有O(1)非常快。public void addAtHead(int val) { ListNode newNode new ListNode(val); newNode.next head; head newNode; size; }这里有一个容易被忽略的细节顺序不能反。如果先把head换成了新节点再让新节点的next指向它请问这时候next指向谁指向了它自己形成了一个环原来的链表就丢了。所以必须先让新节点连接旧链表再更新head。2.3 尾部插入先走到最后一个节点尾部插入就稍微绕一点了。因为链表没有保存尾节点的引用你得从头遍历找到最后一个节点然后把next指向新节点。如果链表本来就是空的呢那尾部插入和头部插入就没什么区别了直接让head等于新节点即可。public void addAtTail(int val) { ListNode newNode new ListNode(val); if (head null) { head newNode; } else { ListNode cur head; while (cur.next ! null) { cur cur.next; } cur.next newNode; } size; }这段代码里cur.next ! null这个条件是最容易写错的地方。有人会写成cur ! null结果呢循环结束后cur已经是null了你根本没法给null.next赋值直接空指针。正确理解是我们想找的是“最后一个节点”它满足的条件是“自己没有下一个节点”也就是cur.next null。2.4 遍历与查找别把head弄丢了查找某个下标的节点或者查找某个值都是遍历问题。遍历的时候最忌讳的一件事就是直接用head去移动。比如这样public int get(int index) { while (index-- 0) { head head.next; } return head.val; }代码是能跑但跑完之后你的链表头没了链表是单链表一旦head丢失你没有任何办法找回前面的节点。正确做法是引入一个临时变量cur来移动head始终保持不动。public int get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index); } ListNode cur head; for (int i 0; i index; i) { cur cur.next; } return cur.val; }这是我见过的新手最容易犯的错没有之一。很多同学写了半天测试的时候发现链表越遍历越短就是因为在查找函数里“动”了head。3. 插入和删除的指针游戏边界条件与常见Bug3.1 在任意位置插入先找前驱节点假如要在下标index处插入节点下标从0开始。核心思路是找到“新节点的前驱”也就是原来下标index - 1的节点然后调整两个引用。我画一张逻辑图在脑子里新节点newNode的next指向原index节点前驱节点的next指向newNode。public void addAtIndex(int index, int val) { if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index); } if (index 0) { addAtHead(val); return; } // 找到 index 位置的前驱节点 ListNode cur head; for (int i 0; i index - 1; i) { cur cur.next; } ListNode newNode new ListNode(val); newNode.next cur.next; cur.next newNode; size; }这里有一个经典顺序先让新节点指向后驱再让前驱指向新节点。如果反过来先让前驱指向新节点那么原来的后驱节点就“断连”了你手里又没有它的引用后面就找不回来了。3.2 删除节点别拿“假删除”骗自己删除操作指的是把某个节点从链表中摘掉。对于删除头节点直接head head.next即可。但对于删除中间节点同样需要找到前驱。public void deleteAtIndex(int index) { if (index 0 || index size) { return; } if (index 0) { head head.next; } else { ListNode prev head; for (int i 0; i index - 1; i) { prev prev.next; } prev.next prev.next.next; } size--; }注意prev.next prev.next.next这行逻辑上是把前驱的next直接跨过被删除节点指向它的下一个。被删除的节点就成了“孤儿”。Java里有垃圾回收机制过一会儿它会被自动回收不需要你手动释放。但在C/C里你还得free或者delete一下否则就内存泄漏了。3.3 哨兵节点让你少写一半if上面的写法虽然能跑但回头看处理头节点和中间节点用了完全不同的逻辑每个方法都有一堆if (index 0)判断。有没有办法统一有引入虚拟头节点也叫哨兵节点。哨兵节点是一个不存真实数据的节点永远固定在链表头前面。它的next指向真正的头节点。这样头节点也是“有前驱”的节点了插入、删除的逻辑就统一了永远去找前驱节点前驱的next永远存在。public class MyLinkedList { private ListNode dummyHead; private int size; public MyLinkedList() { dummyHead new ListNode(-1); size 0; } public void addAtIndex(int index, int val) { if (index 0 || index size) throw ...; ListNode prev dummyHead; for (int i 0; i index; i) { prev prev.next; } ListNode newNode new ListNode(val); newNode.next prev.next; prev.next newNode; size; } public void deleteAtIndex(int index) { if (index 0 || index size) return; ListNode prev dummyHead; for (int i 0; i index; i) { prev prev.next; } prev.next prev.next.next; size--; } }你看加了哨兵之后头节点和普通节点一视同仁index 0的特判完全消失了。这可能是我在实现链表时最推荐的一个设计思路与其到处写边界判断不如把数据结构本身改造得不需要边界判断。4. 链表反转一个经典问题的四种写法4.1 迭代反转三根指针逐步“掉头”链表反转是绕不开的经典题。逻辑上其实很简单把每个节点的next从指向后改为指向前。但要实现这一步你得同时记录三个节点前驱prev、当前curr、后继next。public ListNode reverse(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; // 保存后继防止断链后丢失 curr.next prev; // 当前节点指向前驱 prev curr; // 前驱右移 curr next; // 当前右移 } return prev; // 反转后prev就是新链表的头 }第一次实现的时候建议你在纸上画一下每轮循环三个引用的变化。我当年学的时候自己画了三轮循环才彻底看懂curr.next prev就是把箭头掉了个方向prev curr和curr next就是整体右移。一共三步缺一不可顺序不能乱。4.2 递归反转代码很短理解很难递归反转的长相和迭代完全不同代码非常短public ListNode reverse(ListNode head) { if (head null || head.next null) { return head; } ListNode newHead reverse(head.next); head.next.next head; head.next null; return newHead; }很多初学者背下这段代码但过两天就忘了。关键在于理解递归的“信任”reverse(head.next)被调用后它会返回一个已经反转好的链表且新链表的头就是原链表第二个节点。这时候只需要做两件事第一让原来第二个节点现在是新链表的尾指向head第二让head.next置空。结合代码看head.next.next head就是“把下一个节点的next指回当前节点”head.next null是把当前节点的next断掉避免形成环。递归解法有一种“从后往前”的加工顺序打印一下调用栈就能看得很清楚。不过我得提醒一句递归反转在数据量大的时候有风险。链表节点几十万的时候递归深度极大很容易栈溢出。生产环境我一般不推荐递归反转但理解它对于夯实递归思维很有帮助。4.3 反转的实际意义不只是面试题有人会问链表反转看起来花里胡哨的实际工作中用得着吗其实挺常见的。比如某些数据结构的实现需要逆序访问比如实现一个支持“从尾部追加”场景下的栈或者在做大整数运算、LRU缓存淘汰等场景时反向遍历是基础操作。还有一个很实际的场景单向链表的特性决定了你只能往前走当你需要从后往前处理时反转就是一种思路。无论是LeetCode还是公司面试链表反转都只是外层包装真正考察的是你对引用关系是否足够敏感谁会丢失引用哪里会形成环怎么保证每个节点在操作后仍然可达。这三个问题想明白了反转只是顺手的事。5. 双向链表和循环链表更复杂结构的实现逻辑5.1 双向链表的节点设计与删除优势单链表最烦的一点只能从头往后走想删除某个节点还得先找它的前驱代价是O(n)。双向链表就是为了解决这个问题——每个节点不仅知道下一个还知道上一个。class DoublyListNode { int val; DoublyListNode prev; DoublyListNode next; DoublyListNode(int val) { this.val val; } }有了prev引用删除一个已知节点就变成了O(1)操作让它的前驱节点的next指向它的后继让它的后继节点的prev指向它的前驱然后节点自己就算“脱离”了。public void removeNode(DoublyListNode node) { node.prev.next node.next; if (node.next ! null) { node.next.prev node.prev; } }注意这里要判断node.next是否为null因为如果是尾节点node.next.prev就不存在了。这在实现时是个很典型的坑。双向链表的代价也很明显每个节点多了一个引用内存占用大约增加8字节64位JVM上而且插入和删除操作需要维护两个方向的引用代码量几乎翻倍。5.2 循环链表的实现与应用场景循环链表就是把尾节点的next指回头节点形成一个环。判断结束的条件从cur null变成了cur head这个变化看似简单实际实现时很容易写错。如果你不小心让循环链表变成了“死循环”的环而不是“有终点的环”遍历可能永远停不下来。一个更常见的变体是双向循环链表也就是尾节点的next指向头节点头节点的prev指向尾节点。JDK里的LinkedList本质上就是这种结构。循环链表用在哪经典场景是操作系统的进程调度、任务轮询等“边遍历边循环处理”的机制。我早期做一个小型消息队列时就用过循环链表来轮询一批后端服务节点保证每次从上次断点继续往下轮而不是每次从头开始。说实话业务代码里自己手写循环链表的机会很少但手写一遍之后你对JDK中LinkedList的很多设计选型会理解得更透——它为什么要用双向的哨兵节点因为环形结构配合哨兵可以省掉极多的null判断。6. 链表与ArrayList的实测对比别再背“数组查找快、链表插入快”了6.1 理论时间复杂度 vs 真实内存开销教科书上通常画这么一张对比表操作ArrayListLinkedList随机访问O(1)O(n)头部插入O(n)O(1)尾部插入O(1)均摊O(1)中间插入O(n)O(n)内存占用连续数组节点引用这张表本身没错但它只说了一半。另一半是计算机组成原理的东西数组在内存里连续存储CPU访问时可以利用缓存行预读链表节点是离散的跳来跳去很容易缓存不命中。所以现实中的差距往往比理论更大。我做过一个朴素的实验往ArrayList和LinkedList中轮流添加100万个随机数然后从头到尾遍历一遍。结果ArrayList的遍历速度大约是LinkedList的3到5倍原因就是缓存局部性。这个数字在不同机器上会有差异但结论方向基本一致链表的O(1)插入优势经常被它的缓存不友好抵消掉。6.2 什么情况下真的该用链表那链表是不是就没用了当然不是。有这么几类场景链表依然是更合理的方案头部插入或删除特别频繁而且数据量很大。此时ArrayList每次都是O(n)的数组移动链表确实更强。实现LRU缓存等需要频繁增删节点的数据结构。LinkedHashMap内部就是哈希表双向链表的组合。内存不连续的大对象场景。你没法提前预估容量而且剩余内存碎片化严重。需要常数时间的合并、拆分操作。比如把两个链表拼接起来只要调整几个引用就行数组做不到。我的建议是业务代码里能不用手写链表就不用JDK的LinkedList以及各种并发容器已经足够好。但当你确定要做“高频头部操作”时链表是结构上最优雅的选择这时候该上就上。7. 我在真实项目中总结的链表使用经验与避坑清单7.1 最常见的五个坑手写链表的过程中有几个坑我几乎每次都会看到学员或者同事踩到这里一次性列清楚弄丢头节点任何遍历都不应该直接移动head。想移动先赋值给局部变量。插入顺序颠倒新节点先连接后驱再更新前驱的next。顺序反了必断链。循环条件写错while (cur ! null)和while (cur.next ! null)意义完全不同。前者是“访问每个节点”后者是“停在最后一个节点”。删除后size忘记减这个看起来低级但真的很常见。特别是多个分支里都有size--时容易漏掉其中一个。反转时丢引用反转一定要先保存next否则你改完当前节点下一个节点就找不到了。7.2 一个容易忽视的工程细节调试时如何打印链表链表出问题时肉眼检查引用关系基本没戏。我强烈建议写一个printList()工具方法public void printList() { ListNode cur head; while (cur ! null) { System.out.print(cur.val - ); cur cur.next; } System.out.println(null); }在每一步操作后都打印一次尤其是反转和插入操作。打印结果一出来很多逻辑问题就顿时清晰了。这个方法虽然简单但真的是调试链表的神器比你在IDE里断点单步盯着看要高效得多。7.3 我的使用心得以我这些年写Java的经验链表的实现难度不在于“写出来”而在于“想清楚边界”。如果你能把单链表的基本操作、反转、以及为什么用哨兵节点更简洁都用自己的话讲给别人听那你对Java引用的理解就已经超过大多数同行了。我个人的习惯是学任何数据结构都先动手手写一遍写的时候别开IDE的代码提示就靠脑子里的那张引用图。写完单链表再去写双向链表、循环链表最后再对比JDK源码里LinkedList的设计思路。这种“先自己思考、再看大师解法”的学习路径比直接背源码要扎实得多。最后分享一个小技巧如果你在面试里遇到“用Java实现链表”这种题别急着写代码先和面试官确认清楚——是只要单链表的基本功能还是要带反转、哨兵、双向等优化明确需求再动手往往会让面试官觉得你思路清晰。这个习惯在真实项目里也一样适用先把边界和约束聊明白再坐下去写代码。

Java手写链表从零实现：核心逻辑与避坑指南

相关推荐

篡改猴测试版5.1.6193离线安装：解压加载与配置迁移全攻略

CTF学习路线全解析：从赛道选择到实战刷题方法论

Spring Boot选课系统实战：从并发控制到部署上线的完整指南

更多资讯

Codeforces 946G Almost Increasing Array：删除位置与树状数组优化解析

odbcji32.dll丢失修复指南：从SFC扫描到官方数据库驱动完整方案

【一人公司】2026 独立开发新范式：从 v0 到 Cursor，用 TaoToken 统一 Key 打通全链路 AI 提效

一天连开七个仓库对标 Adobe：本周 GitHub 上最猛的个人开发者是他

Zotero Better BibTeX 导入偏好配置指南：花括号大小写保护、AUX 扫描回填与句例化处理

WAMP环境下的网络考试系统设计与实现：从数据库到PHP的完整指南

今日更新

再见，SSE！你好，Streamable HTTP！轻松开发 Streamable HTTP MCP Server 并接入 TaoToken

工业软件标准化路线图：国产替代的落地施工图

VCMI安卓版实操指南：原生运行英雄无敌3的3步技术落地

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？