熟悉 Java 集合框架的朋友肯定对 LinkedList 不陌生面试题里它和 ArrayList 的对比几乎成了固定考点日常开发里它又经常被当作“队列或栈的备胎”来用。但说实话很多同学用 LinkedList 的方式是有问题的——要么拿它当 ArrayList 用然后奇怪为什么性能这么差要么对底层结构完全没概念纯靠死记硬背 API。这篇博文我就从底层结构开始讲把 LinkedList 的设计思路、常用 API、适合场景和常见的坑一次性说清楚希望你看完能对“什么时候该选它、怎么用才稳”有自己的判断。这篇文章适合刚学到集合框架、想系统梳理 Java List 体系的初学者也适合准备面试需要深挖源码细节的开发者。同时那些在项目里对 List 选型犹豫不决、不知道该在 ArrayList 和 LinkedList 之间怎么选的朋友看完之后应该也会有自己的答案。1. 动手前先搞懂LinkedList底层到底长什么样很多初学者第一次接触 LinkedList 时最困惑的一点是它明明也叫 List为什么用起来和 ArrayList 完全不一样根源就在它们的底层存储结构。1.1 从内存布局看懂链表和数组的本质差异ArrayList 底层是一个 Object 数组元素在内存里是一段连续空间每个位置都有天然的下标所以想拿第几个元素直接通过索引算地址就行。你可以把它想象成一列编号整齐的火车车厢车厢从头到尾固定连在一起车厢号和位置一一对应。LinkedList 则完全不同。它底层是一个双向链表每个元素是一个独立的 Node 对象除了存储自己的数据项 item 之外还分别持有指向前一个节点的 prev 引用和指向后一个节点的 next 引用。整个集合就像一群人前后手拉手站成一排第一个人只握着第二个人第二个人只握着第一个人和第三个人……你想找到队伍中间那个戴帽子的人就得从第一个人开始一个个看过去因为没有任何一个人知道自己“编号”是多少。这就是链表和数组在访问方式上的本质差异数组支持随机访问链表只能顺序访问。从内存碎片角度看ArrayList 通常是一整块连续内存扩容后会有一次整体搬移LinkedList 则是一个个零散的 Node 对象分散在堆内存里靠引用串起来。1.2 Node节点和双向链接的设计逻辑先看 LinkedList 内部节点的定义不同 JDK 版本略有差异核心结构一致private static class NodeE { E item; NodeE next; NodeE prev; Node(NodeE prev, E element, NodeE next) { this.item element; this.next next; this.prev prev; } }每个节点就是一个“车厢加前后连接器”。LinkedList 内部只保存三个东西指向第一个节点的 first 指针、指向最后一个节点的 last 指针、以及记录元素个数的 size 变量。为什么用双向而不是单向这个设计很关键。单向链表如果要删除最后一个节点需要从头遍历找到倒数第二个节点来更新它的 next时间复杂度是 O(n)。而双向链表由于每个节点都存了 prev删除尾部节点时可以直接通过 last.prev 找到前一个节点一步搞定。同样道理查询时可以从头部正向搜索也可以从尾部反向搜索这让“中间位置的查找”有机会做优化后面源码部分会细说。LinkedList 实现了很多接口但最核心的两条线一是 List 接口让它具备集合的增删改查能力二是 Deque 接口让它直接可以作为双端队列使用。这也是 LinkedList 能在“队列/栈”场景下大显身手的前提。顺带一提LinkedList 没有实现 RandomAccess 接口。这个接口是个空的标记接口作用是告诉 JDK 里的算法类“我这个集合支持随机访问”。比如 Collections.binarySearch 在搜索时会判断传入的 List 是否 implements RandomAccess是就用索引二分否则退化成迭代器遍历。LinkedList 不支持 RandomAccess语义上就是在提醒使用者别老想着用 get(i) 去碰它老老实实遍历。现在底层的“为什么”清楚了我们进入实用环节看看具体怎么用它。2. 核心API逐个过增删改查的用法和细节LinkedList 的 API 非常多因为它同时实现了 List 和 Deque 两套接口附带了一些栈风格的旧方法。初看会觉得混乱但只要按“增删改查 队列栈专属操作”分类记忆就不会乱了。2.1 初始化方式和最基本的增删操作初始化有三种常用方式// 方式一默认空链表 LinkedListString list1 new LinkedList(); // 方式二传入已有集合 ListString source Arrays.asList(a, b, c); LinkedListString list2 new LinkedList(source); // 方式三匿名内部类双括号初始化不推荐会产生内部类了解即可 LinkedListString list3 new LinkedList() {{ add(a); add(b); }};日常开发推荐方式一和方式二第三种会产生额外的内部类文件还容易造成内存泄漏隐患能不用就不用。最基础的新增方法LinkedListString list new LinkedList(); list.add(a); // 尾部添加等价于 addLast list.addLast(b); // 尾部添加 list.addFirst(c); // 头部添加 list.push(d); // 栈风格等价于 addFirst压栈到头部 list.offer(e); // 队列风格尾部添加 list.offerFirst(f); // 队列风格头部添加你可以把 add、addLast、offer 都当成“从尾巴加”把 addFirst、push、offerFirst 当成“从头加”。它们底层的动作基本一致差别主要在于返回值约束和空值处理add 系列方法在插入后返回 trueoffer 系列是 Queue 接口定义的允许返回 false 表示插入失败但 LinkedList 实现里基本都会成功。我自己项目里会保持统一追加数据固定用 add当队列用固定用 offer不要混着写否则同事 review 代码时还得查 API。删除操作同样有两套list.remove(); // 移除头部元素并返回空列表时抛 NoSuchElementException list.removeFirst(); // 同上 list.removeLast(); // 移除尾部元素空列表时抛异常 list.poll(); // 移除头部元素空列表时返回 null list.pollFirst(); // 同上空列表时返回 null list.pollLast(); // 移除尾部元素空列表时返回 null list.pop(); // 栈风格移除头部元素空列表抛异常这里最关键的区别就是poll 系列空表返回 null 不抛异常remove、pop 系列空表会抛异常。业务上如果数据可能为空优先用 poll 系列避免异常打断流程。2.2 查改方法与队列栈专属API查询方面常用的有这些list.get(0); // 按下标查元素会走链表遍历 list.getFirst(); // 获取头部元素空表抛异常 list.getLast(); // 获取尾部元素空表抛异常 list.peek(); // 查看头部元素空表返回 null list.peekFirst(); // 查看头部元素空表返回 null list.peekLast(); // 查看尾部元素空表返回 null list.contains(a); // 判断是否包含某个元素内部靠 equals 遍历比较 list.indexOf(a); // 正向查找第一个匹配位置 list.lastIndexOf(a); // 反向查找最后一个匹配位置修改操作主要是 setlist.set(0, z); // 把索引 0 位置替换为新元素返回旧值还要注意一个细节LinkedList 的 contains 和 remove(Object) 是用 equals 来比较的。如果你的元素是自定义对象一定要重写 equals 和 hashCode否则默认比较的是引用地址查出来的结果可能和你预期不符。这个坑我在业务代码里遇到过查了半天才发现是两个对象属性一样但 equals 没重写。最后再补充一个 ListIterator 双向迭代器它是 LinkedList 遍历时的隐藏利器// 从前往后遍历 ListIteratorString it1 list.listIterator(); while (it1.hasNext()) { String s it1.next(); } // 从后往前遍历 ListIteratorString it2 list.listIterator(list.size()); while (it2.hasPrevious()) { String s it2.previous(); }2.3 一个完整的实用案例下面用一个小案例把 API 串起来。假设要模拟浏览器的前进后退记录只保留最近 5 条浏览历史public class BrowserHistory { private static final int MAX_SIZE 5; private final LinkedListString history new LinkedList(); public void addPage(String url) { // 新页面加到最前面 history.addFirst(url); // 超过容量就淘汰最旧的 if (history.size() MAX_SIZE) { history.removeLast(); } } public void removePage(String url) { // 删除某条历史记录 history.remove(url); } public String currentPage() { return history.peekFirst(); } public ListString recentPages() { return new ArrayList(history); } Override public String toString() { return history.toString(); } }这个场景就非常契合 LinkedList 的特点浏览记录要频繁在头部插入新数据容量满了淘汰尾部最旧数据头尾操作都是 O(1)非常轻快。如果换成 ArrayList 来做头部插入每一次都要把整个数组元素往后搬移历史记录越长越卡。3. 什么时候该用LinkedList场景判断标准聊完 API重点来了项目里到底什么时候才值得用它我个人的判断标准很朴素——没有特殊理由时优先用 ArrayList真正需要高频头尾增删或者明确要当队列/栈用时才切换到 LinkedList。3.1 高频头尾操作场景先看一个对比在头部反复插入 10 万条数据ArrayList 和 LinkedList 的表现会差多少ArrayList 每次 add(0, element) 都要把现有所有元素整体向后搬一位复杂度 O(n)10 万条数据累计操作量是亿级别的。LinkedList 的 addFirst 每次只创建一个新节点改一下 first 指针复杂度 O(1)差距非常夸张。反过来看尾部追加ArrayList 在容量足够时 add 是 O(1)只有扩容时才 O(n)均摊后也是 O(1)所以大部分场景 ArrayList 并不吃亏。典型的高频头尾操作场景包括消息队列的 FIFO 缓冲尾部入队、头部出队。撤销/重做记录不断在头部插入最新操作同时限制历史条数从尾部淘汰。最近使用列表LRU 的简化版访问过的数据提前到头部超出容量淘汰尾部。判断自己场景是否合适可以问三个问题是不是主要在头和尾操作中间位置的增删频率高吗会不会频繁按索引取值如果前两个回答“是”、后一个回答“否”LinkedList 大概率是合适的。3.2 队列栈与Deque实现LinkedList 因为实现了 Deque 接口天然具备双端队列能力也可以作为栈使用。Java 老版本的 Stack 类继承自 Vector所有方法都加了同步锁性能一般官方也推荐用 ArrayDeque 或 LinkedList 替代。如果你需要一个带有 List 属性的栈LinkedList 很方便如果纯粹做栈或队列更推荐 ArrayDeque它底层是循环数组内存更紧凑实际跑起来通常更快。这里有个很容易纠结的点ArrayDeque 和 LinkedList 谁更值得当队列用我的结论很明确——如果不依赖 null 值做业务判断优先选 ArrayDeque。原因有三个数组实现缓存友好遍历快内存开销小不需要维护 Node 对象。LinkedList 的优势是可以当 List 用、可以按下标访问除此之外在纯队列场景并没有多少优势。还要提醒一句LinkedList 不是线程安全的多线程共享同一个链表实例并同时修改时会出现数据错乱甚至抛异常。并发场景下要么自己加锁要么用 ConcurrentLinkedDeque 或 CopyOnWriteArrayList 等并发容器。3.3 和ArrayList的全面对比我把两者在关键维度上的差异整理成一张表对比维度ArrayListLinkedList底层结构动态数组双向链表随机访问 get(i)O(1)按下标直接定位O(n)需要遍历链表尾部插入O(1) 均摊扩容时 O(n)O(1)直接链接到 last 后面头部插入O(n)所有元素整体后移O(1)更新 first 指针即可中间插入O(n)涉及数据搬移O(n)先遍历定位再链接删除指定对象O(n)查找到后搬移O(n)查找到后直接改指针内存占用数组本身有预留容量但节点无额外开销每个元素都要建 Node额外两个引用加对象头是否实现 RandomAccess是否常见遍历方式下标循环或迭代器迭代器优先从这张表能看出一个核心结论LinkedList 的“快”集中在头尾操作一旦涉及中间位置的增删和随机访问它就不再占优。而且因为 CPU 缓存的原因ArrayList 顺序遍历时通常比 LinkedList 快不少——数组元素在内存中是连续的CPU 预读友好LinkedList 的节点分散在不同内存地址每次访问都可能触发缓存未命中。我见过不少同学因为听说“LinkedList 增删快”就无脑用它结果从中间删数据、用 get(i) 遍历整体性能反而比 ArrayList 慢很多。选型这种事真的得结合自己的具体操作模式来定。4. 源码窥探关键方法背后的性能逻辑前面说了很多“O(1)”“O(n)”为了打消纸上谈兵的疑虑这节直接翻几个关键方法的源码逻辑看看复杂度的结论到底是怎么来的。4.1 尾部添加和头部删除为什么是O(1)以 add(E) 为例它最终调用的是 linkLast 方法逻辑可以理解为void linkLast(E e) { final NodeE l last; final NodeE newNode new Node(l, e, null); last newNode; if (l null) first newNode; else l.next newNode; size; modCount; }整个过程只做了四件事拿到当前最后一个节点new 一个新节点把新节点的 prev 指向旧尾节点更新 last 指针再把旧尾节点的 next 指向新节点。没有任何遍历所以不管链表里已有 1 条还是 100 万条数据添加尾部的开销几乎一样。删除头节点调用 unlinkFirstprivate E unlinkFirst(NodeE f) { final E element f.item; final NodeE next f.next; f.item null; f.next null; first next; if (next null) last null; else next.prev null; size--; modCount; return element; }同样不需要遍历只更新 first 指针并把原头节点的 next 和 item 置空方便 GC 回收。上面代码里出现的 modCount 是 AbstractList 定义的修改计数器每次结构性修改增删元素都会自增。迭代器内部会保存一个初始的 expectedModCount每次遍历都校验一次一旦发现两者不一致就立刻抛 ConcurrentModificationException。这就是 fail-fast 机制作用是在多线程并发修改或单线程遍历时非法删除时尽早暴露问题。理解了 modCount 的机制很多奇怪的异常排查起来就有方向了。4.2 中间插入为什么get(index)会有二分优化随机数 get(index) 的实现核心是 node(index) 方法NodeE node(int index) { if (index (size 1)) { NodeE x first; for (int i 0; i index; i) x x.next; return x; } else { NodeE x last; for (int i size - 1; i index; i--) x x.prev; return x; } }这里用了一个很聪明的优化如果目标下标小于 size 的一半就从头部往后找否则从尾部往前找。这样最坏情况下也只需要遍历 n/2 个节点比单链表从头走到尾要节省一半时间。但注意它仍然是 O(n)只是常数减半。add(int index, E element) 的流程则是public void add(int index, E element) { checkPositionIndex(index); if (index size) linkLast(element); else linkBefore(element, node(index)); }先检查下标合法性如果要插在最后就直接走 O(1) 的 linkLast否则先调用 node(index) 找到目标位置再在目标节点前面链接一个新节点。所以中间插入的复杂度实际上是“定位的 O(n) 链接的 O(1)”并不像网上有些人说的“链表插入天生就是快”。4.3 时间复杂度汇总我把 LinkedList 各操作的时间复杂度汇总一下方便你面试或写文档时直接引用操作时间复杂度说明add(E)O(1)尾部追加不涉及遍历addFirst / pushO(1)头部追加removeFirst / popO(1)头部删除removeLast / pollLastO(1)尾部删除得益于双向指针get(int index)O(n)最坏 n/2 次遍历set(int index, E)O(n)先定位再替换add(int index, E)O(n)先定位再链接remove(Object)O(n)从头部开始逐个 equalscontains(Object)O(n)同上iterator().remove()O(1)迭代到当前节点后直接改指针这套复杂度也解释了 LinkedList 在高频头尾操作场景的优势其他场景它并不比 ArrayList 有本质优势。4.4 内存占用实测分析除了时间复杂度内存开销也值得重视。LinkedList 每个元素都要创建一个 Node 对象这个对象里有一个 item 引用、一个 prev 引用、一个 next 引用外加对象头。在 64 位虚拟机开启压缩指针的情况下一个 Node 对象大约是 24 字节左右再加上 String 等业务对象本身而 ArrayList 里每个元素只是一个引用底层数组最多浪费一点预留容量。实际算一笔账存储 10 万个字符串元素LinkedList 光 Node 对象的额外开销就是 10 万乘以 24 字节大约 2.4MBArrayList 除了数组本身额外开销要小得多。如果你的任务里有百万级以上的中间数据临时存储选 LinkedList 前一定要评估内存否则 GC 压力会让你怀疑人生。5. 踩坑记录LinkedList实战问题汇总最后分享一些我在实际开发中踩过、也帮同事排查过的 LinkedList 坑每一条都是真金白银换来的经验。5.1 遍历时删除元素引发并发修改异常经典错误写法LinkedListString list new LinkedList(Arrays.asList(a, b, c, d)); for (String item : list) { if (b.equals(item)) { list.remove(item); // 抛出 ConcurrentModificationException } }增强 for 循环底层依赖迭代器迭代器会在 next() 时检查 modCount 是否变化而 list.remove 会修改 modCount于是立刻报并发修改异常。正确做法是使用迭代器自身的删除方法IteratorString iterator list.iterator(); while (iterator.hasNext()) { String item iterator.next(); if (b.equals(item)) { iterator.remove(); } }迭代器的 remove 会把当前节点的删除动作同步到迭代器内部维护的 expectedModCount因此不会触发校验失败。如果你需要边遍历边删除这是一个必须养成的好习惯。另外如果删除所有满足条件的元素Java 8 以后可以直接用 removeIflist.removeIf(item - b.equals(item));removeIf 底层也是迭代器模式不需要自己管理并发校验。5.2 for循环get(i)遍历的性能陷阱这是一个典型的二重循环性能事故// 千万不要这么写 for (int i 0; i list.size(); i) { System.out.println(list.get(i)); // 每次 get 都要从头/尾遍历链表 }LinkedList 的 size 是 10 万时这个循环的总操作量是 10 万次 get每次 get 平均走 5 万个节点总计约 5 亿次指针跳转。而 ArrayList 同样的循环只需要 10 万次直接索引定位两者差距是几个量级的。正确写法只有两行代码的区别性能却有天壤之别for (String s : list) { System.out.println(s); }或者显式使用迭代器。增强 for 在 LinkedList 上会退化为迭代器遍历每次 next() 都只需要沿着当前节点的 next 指针走一步总体是 O(n)。这个坑我在代码审查时见过太多次了很多同学会把 ArrayList 的下标遍历习惯带到 LinkedList 上一看压测数据不对先怀疑框架、怀疑 JVM最后才发现是自己遍历方式的问题。5.3 索引越界与空值处理的边界判断LinkedList 的 get、set、add(index, element) 都会校验下标越界时抛 IndexOutOfBoundsException而用 removeFirst、pop、getFirst 时如果链表为空会抛 NoSuchElementException。这本身没问题真正隐蔽的是 null 值。LinkedList 允许存 null 值这意味着你判断某个元素是否存在时contains 可能返回 true但取值却是 null。如果业务里 null 有特殊含义最好统一加一道“是否包含 null”的判断或者用 Optional 包装避免出现“取到了值但值是 null”的困惑。另一个常见边界是下标正好等于 size 的 add 操作。add(size, element) 是合法的等价于尾部追加但 get(size) 一定越界。这种“边界差一”的小问题在写循环往链表中间插入数据时特别容易翻车建议写完后多看两遍边界条件。5.4 自己添加自身的addAll陷阱与双向迭代器选择LLinkedList 的 addAll 有一个隐蔽问题如果往 LinkedList 里 addAll 它自己JDK 的实现里有专门的 copySelf 分支先把原内容复制一份新数组再插入避免迭代器读取时因内容变化而陷入死循环或结果错乱。虽然日常代码里很少有人这么写但如果你在做“把当前列表复制一份追加到尾部”这类操作建议直接这样写逻辑更清晰LinkedListString list new LinkedList(Arrays.asList(a, b)); list.addAll(new LinkedList(list)); // 显式复制一份避免 addAll 自身的特殊分支双向迭代器这一块如果你的需求是同时从头部和尾部开始扫描比如判断某个序列是否为回文LinkedList 有现成的 descendingIteratorIteratorString descIt list.descendingIterator(); while (descIt.hasNext()) { // 从尾部往头部遍历 }配合 listIterator 从前往后遍历你可以在不写嵌套循环的情况下完成双向扫描。这个 API 知道的人不多但在栈回退、历史回放这类场景里非常顺手。5.5 LinkedList 作为 LRU 缓存时的频率问题我见过有人在自制 LRU 缓存时把“最近访问”记为 moveToFirst每次访问某个元素先 remove 再 addFirst。这两个操作单独看都不贵但 remove(Object) 需要从头部开始遍历查找复杂度 O(n)。如果缓存里有几千条数据每次命中的开销都在微秒量级还好数据量到几十万以上就会非常明显。更优的做法是用 LinkedHashMap 的 accessOrder 机制或者用 ConcurrentLinkedDeque 配合外部锁维护。如果业务规模小、数据量几百条用 LinkedList 手动实现倒也够用但数据量一上来还是要选择为 LRU 设计的数据结构别把 LinkedList 硬拗成万能药。下面把这些常见问题整理成一个速查表问题现象可能原因解决方案遍历时删除抛 ConcurrentModificationException集合方法直接修改 modCount用 iterator.remove() 或 removeIf用 get(i) 遍历 LinkedList 很慢每次 get 都是 O(n) 遍历改用增强 for 或迭代器空链表调用 removeFirst 抛异常空表状态下传统方法不允许使用 poll 系列并判空contains 查不到自定义对象未重写 equals / hashCode重写对象的 equals 和 hashCode明明只用尾部插入却比 ArrayList 慢节点对象内存开销大遍历缓存不友好纯尾部操作优先 ArrayList把 LinkedList 当多线程共享队列用LinkedList 不是线程安全用 ConcurrentLinkedDeque 或加锁结尾我个人在实际项目里的经验是LinkedList 从来不是一个“有它就是高级”的炫技结构而是一个在特定形状下特别趁手的工具。真正常用它的人群往往是实现队列、双端队列、栈这类容器或者维护“最近使用列表”一类的场景。除此之外默认选择 ArrayList 几乎不会错。最后再分享一个小技巧如果你在写代码时拿不准该用 ArrayList 还是 LinkedList可以先写一个简单的基准测试就测你业务里最核心的三种操作——插入、删除、遍历数据量按自己线上的峰值来。实测数据往往比理论分析更能说服人也比在论坛里争论“到底谁快”靠谱得多。掌握 LinkedList 的关键不是背 API而是理解它那双向链表的本质然后在正确的位置使用它。
