1. 从整体设计看 LinkedList 在集合框架中的角色1.1 三个核心概念双向链表、Deque 实现、全能选手先把我个人对 LinkedList 的理解说清楚它不是一个简单的“ArrayList 的替代品”而是同时实现了 List 和 Deque 两个接口的“双面手”。List 接口意味着它和 ArrayList 一样支持有序访问、按索引操作、迭代遍历Deque 接口意味着它又能像队列一样从头部或尾部添加、移除、获取元素。这种双接口设计让 LinkedList 在需要“列表 队列/栈”两种语义的场景里用起来非常顺手。底层结构方面LinkedList 的每个节点都保存三个字段自身元素、指向前一个节点的引用、指向后一个节点的引用。头节点first和尾节点last被单独记录下来整个链表通过这些引用串起来。这种结构最直接的效果就是往任意位置插入或删除元素时只需要修改相邻节点的引用指向不需要像数组那样把元素成片搬移。内存层面LinkedList 也没有“容量”这个概念。ArrayList 在扩容时会把旧数组里的元素整体拷贝到新数组而 LinkedList 是真正的“来一个元素、创建一个节点”不存在扩容带来的瞬时内存抖动。1.2 为什么有了 ArrayList 还需要 LinkedList写代码的时候经常会遇到一个疑问ArrayList 能做的 LinkedList 都能做那到底什么场景该选 LinkedList我在实际项目里总结的判断标准有两条第一是否频繁在中间位置插入或删除元素第二是否需要同时以队列/栈的方式操作集合。命中任意一条LinkedList 的价值就出来了。举个例子做任务调度模块时任务队列里有“插队”的需求。用 ArrayList 的话每插一个任务到列表中间后面的任务全部要后移一位一旦数据量到了几千条操作耗时能明显感知出来。换成 LinkedList 之后插入操作只修改前后节点的引用耗时基本稳定数据规模上去之后差距尤其明显。另外一类典型场景是实现撤销/重做功能需要从尾部添加记录、从尾部回退删除记录同时还要遍历查看完整的历史列表。LinkedList 的 addLast 和 removeLast 配合迭代器天然匹配这种操作模式。如果强行用 ArrayList也能实现但语义上就没有那么贴合了。需要特别说明的是LinkedList 的优势是“在已知节点附近插入删除”快而不是“按索引操作”快。如果代码里总是用 get(i) 去遍历LinkedList 反而比 ArrayList 慢得多。这一点选择容器时一定要先想清楚。2. LinkedList 的核心方法详解增删改查与双端操作2.1 基础增删改查方法的使用说明LinkedList 作为 List最基础的一批方法就是 add、get、set、remove。下面直接看代码配合注释说明每个方法的语义import java.util.LinkedList; public class LinkedListBasicDemo { public static void main(String[] args) { LinkedListString list new LinkedList(); // 追加元素add(E e) 默认在尾部追加 list.add(Java); list.add(Python); list.add(Go); System.out.println(初始列表 list); // 指定位置插入add(int index, E element) // 注意 index 范围是 0 到 size()等于 size() 时表示追加到尾部 list.add(1, C); System.out.println(索引1插入 C list); // 获取元素get(int index) String second list.get(1); System.out.println(索引1元素 second); // 修改元素set(int index, E element)返回被替换掉的旧值 String oldValue list.set(2, Rust); System.out.println(索引2旧值 oldValue 修改后 list); // 删除元素remove(int index)返回被删除的元素 String removed list.remove(1); System.out.println(删除索引1 removed 剩余 list); // 直接删除指定元素remove(Object o) 只删除第一个匹配项 boolean isRemoved list.remove(Go); System.out.println(删除 Go isRemoved 剩余 list); // 其他常用方法 System.out.println(元素个数 list.size()); System.out.println(是否为空 list.isEmpty()); System.out.println(包含 Rust list.contains(Rust)); System.out.println(Rust 首次出现的索引 list.indexOf(Rust)); } }几个容易踩坑的地方值得多说一句add(int index, E element) 的 index 参数可以等于 size()但大于 size() 会直接抛 IndexOutOfBoundsException小于 0 也一样抛异常。remove(Object o) 在移除元素时用的是 equals 方法判断相等所以自定义对象一定要正确重写 equals否则会移除不了预期元素。set(int index, E element) 会返回旧值新手经常忽略这个返回值如果业务上需要旧值比如做日志记录就顺手接住。2.2 双端操作方法addFirst / addLast / removeFirst / removeLast / getFirst / getLastLinkedList 是最典型的双端队列实现因为它实现了 Deque 接口所以 Java 6 之后官方推荐优先用 Deque 接口来引用对象而不是直接使用 LinkedList 类型。这一点对于代码的可维护性帮助很大后续要换 ArrayDeque 实现时只改一行就行。双端操作的使用示例import java.util.Deque; import java.util.LinkedList; public class DequeOperateDemo { public static void main(String[] args) { DequeString deque new LinkedList(); // 分别在头尾添加元素 deque.addFirst(头部元素); deque.addLast(尾部元素); deque.add(默认尾部); System.out.println(当前队列 deque); // 获取但不移除头部元素 String head deque.getFirst(); // 获取但不移除尾部元素 String tail deque.getLast(); System.out.println(队首 head 队尾 tail); // 移除并返回头部元素 String removedHead deque.removeFirst(); // 移除并返回尾部元素 String removedTail deque.removeLast(); System.out.println(移除头部 removedHead 移除尾部 removedTail); System.out.println(剩余 deque); } }这里要搞清楚一个概念Deque 接口的操作分为两组一组是 addFirst/addLast/removeFirst/removeLast这组方法在操作失败时会抛异常另一组是 offerFirst/offerLast/pollFirst/pollLast失败时返回 null 或 false。开发中如果数据源不可控比如从外部接口拉取任务列表、逐条塞进队列再处理优先用 offer/poll 系列避免偶尔的空数据导致程序崩溃。还有个细节getFirst/getLast 在队列为空时会抛 NoSuchElementException。所以做循环消费队列时我习惯先用 isEmpty() 判断或者直接用 peek 系列返回 null 来避免异常。2.3 作为队列和栈使用的完整姿势LinkedList 既可以当队列先进先出也可以当栈后进先出。这个特性让它在不少业务场景里可以直接替代 Queue 或 Stack。队列用法DequeString queue new LinkedList(); // 入队 queue.offer(任务1); queue.offer(任务2); queue.offer(任务3); // 出队按先进先出顺序 String task queue.poll(); while (task ! null) { System.out.println(处理 task); task queue.poll(); }栈用法DequeString stack new LinkedList(); // 压栈 stack.push(第一步); stack.push(第二步); stack.push(第三步); // 弹栈按后进先出顺序 while (!stack.isEmpty()) { System.out.println(弹出 stack.pop()); }这里顺便纠正一个初学者常见的误区Java 里有一个 Stack 类但它在设计上有不少历史遗留问题比如它继承了 Vector 的所有方法导致一个栈容器还能按索引任意插入元素语义上不干净。官方自己都建议优先使用 Deque 接口来实现栈逻辑。所以现代代码里基本上用 LinkedList 或 ArrayDeque 就够了。可以说LinkedList 是靠 push/pop/peek 实现栈语义、靠 offer/poll/peek 实现队列语义这一点和纯 List 思维的 ArrayList 完全不同。如果你只是需要一个普通的列表ArrayList 依然是首选一旦涉及队列/栈场景LinkedList 才真正发挥结构优势。3. 实操场景一高频中间插入删除如何优雅实现3.1 场景描述与方案选择有一个比较典型的案例是我之前做过的一个模拟项目X内存里维护一个“在线用户操作日志”列表日志需要按时间顺序排列但又允许用户在某个时间点之前插入一条补充记录。操作频率大约每秒几十次列表规模在 5000 条到 10000 条之间浮动。用 ArrayList 的时候中间插入数据的耗时非常不稳定最差时能明显感觉到抖动。原因有两个一是数组扩容时的整体拷贝二是插入位置之后所有元素的后移。虽然 ArrayList 做了数组拷贝的底层优化但本质上是 O(n) 的操作数据量越大越明显。换成 LinkedList 之后中间插入只涉及节点引用的修改时间复杂度是 O(1)。整体代码改动量很小就是把容器类型从 ArrayList 换成了 LinkedList。这个案例给我一个很深的体会数据结构和业务场景匹配性能收益是立竿见影的。3.2 性能对照示例ArrayList vs LinkedList为了把问题说明白我写了一个简单的压力测试代码对比两种结构在“往列表头部/中间插入 10 万条数据”时的耗时差异。import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class InsertPerformanceCompare { public static void main(String[] args) { int count 100_000; // ArrayList 头部插入 ListInteger arrayList new ArrayList(); long start1 System.nanoTime(); for (int i 0; i count; i) { arrayList.add(0, i); } long cost1 System.nanoTime() - start1; System.out.println(ArrayList 头部插入耗时 cost1 / 1000_000.0 ms); // LinkedList 头部插入 ListInteger linkedList new LinkedList(); long start2 System.nanoTime(); for (int i 0; i count; i) { linkedList.add(0, i); } long cost2 System.nanoTime() - start2; System.out.println(LinkedList 头部插入耗时 cost2 / 1000_000.0 ms); } }在我自己的开发机上跑出来的结果差距非常夸张ArrayList 耗时在几秒级别LinkedList 只有几十毫秒。如果数据量再翻一倍ArrayList 的耗时会接近线性增长而 LinkedList 依然稳定。但注意一个前提LinkedList 的优势来自链表结构调整不需要移动其他元素。如果换成“尾插 随机访问”的场景ArrayList 又反过来吊打 LinkedList。所以每次性能对比都要绑着具体场景说不能笼统说谁更优。3.3 实现细节与坑位提醒从 ArrayList 切换到 LinkedList 时有一个隐藏的大坑遍历方式。很多人写遍历时习惯用 for-index 循环配合 get(i)这在 ArrayList 上是合理的但在 LinkedList 上就是灾难// 灾难现场LinkedList 上用 for get(i) LinkedListString list new LinkedList(); // ... 大量数据 for (int i 0; i list.size(); i) { String s list.get(i); // 每次 get 都从头或尾开始遍历O(n) }上面这段代码总时间复杂度是 O(n²)数据量上万就能感觉到明显的卡顿。正确做法是用迭代器或者增强 for 循环// 推荐迭代器遍历 for (String s : list) { // 处理 s } // 需要删除时用迭代器自带的方法 IteratorString iterator list.iterator(); while (iterator.hasNext()) { String s iterator.next(); if (s.startsWith(temp)) { iterator.remove(); } }这种“坑”在真实项目里非常常见一旦数据量上来线上接口就会突然变慢排查半天发现只是遍历方式写错了。另外LinkedList 在迭代时如果被其他线程修改会触发快速失败机制抛出 ConcurrentModificationException。所以迭代过程中需要删除元素时一定记得用迭代器自己的 remove不要用列表的 remove 方法。4. 实操场景二用 LinkedList 构建一个“最近浏览记录”4.1 需求拆解与数据结构选择模拟一个很常见的小功能用户的最近浏览记录最多保留 5 条新记录到来时自动把最早的记录挤掉。这个需求本质上是一个固定容量的“淘汰队列”类似 LRU 的简化版。用 LinkedList 实现非常直白新浏览记录加到头部如果记录数超过 5就把尾部移除。这里额外考虑一个需求细节同一商品重复浏览不应该出现两条重复记录而是“提到最前面”。这个逻辑用 LinkedList 单独实现需要自己写查重和位置调整过程会稍微绕一点。如果业务再复杂比如需要按访问次数淘汰那就要考虑 LinkedHashMap 或者专门的缓存组件了。这里我只展示最简单的“按时间淘汰”版本。4.2 基于 LinkedList 的实现代码import java.util.LinkedList; public class RecentBrowseHistory { private static final int MAX_SIZE 5; private final LinkedListString history new LinkedList(); /** * 添加一条浏览记录 * 相同记录去重并提到最前面超过容量则移除最旧记录 */ public void addRecord(String itemId) { // 1. 如果已存在先移除旧记录 history.remove(itemId); // 2. 把新记录添加到头部 history.addFirst(itemId); // 3. 超出容量时移除尾部最旧记录 if (history.size() MAX_SIZE) { history.removeLast(); } } public void printHistory() { System.out.println(history); } public static void main(String[] args) { RecentBrowseHistory recent new RecentBrowseHistory(); recent.addRecord(A); recent.addRecord(B); recent.addRecord(C); recent.addRecord(D); recent.addRecord(E); recent.printHistory(); // [E, D, C, B, A] // 再次浏览 BB 被提前 recent.addRecord(B); recent.printHistory(); // [B, E, D, C, A] // 新增 F超出容量最旧的 A 被淘汰 recent.addRecord(F); recent.printHistory(); // [F, B, E, D, C] } }这段代码用到的核心方法其实就三个remove(Object)、addFirst、removeLast。这三个方法在 LinkedList 里都是高效操作逻辑也很直白。读者可以把它作为模板扩展到类似“最近搜索记录”“最近打开文件”等场景。需要注意的一点是如果历史记录数量很大比如上万条用 history.remove(itemId) 去重是 O(n) 操作就不太合适了。更合理的做法是配合 HashMap 做一个索引缓存。不过对于“最近浏览记录”这种限定 5 到 20 条的轻量场景LinkedList 方案是够用的而且代码很短、很好维护。4.3 这个方案的优缺点分析这个方案的优势首先是代码量极小核心增删逻辑不超过三行。其次是内存占用可控因为容量被固定了。再就是语义清晰addFirst 和 removeLast 组合在一起和“新的进、旧的出”的业务表达一一对应。缺点也很明显去重操作需要线性查找数据量大了之后会变慢。另外这个数据结构本身不是线程安全的如果有多个线程同时写浏览记录需要加锁或改用并发容器。还有一点是它只能按“插入时间”淘汰没法处理“访问次数”这类更复杂的淘汰规则。如果要做更完整的 LRU 缓存我一般建议直接用 LinkedHashMap开启 accessOrder 模式即可LinkedHashMapString, String cache new LinkedHashMap(16, 0.75f, true) { Override protected boolean removeEldestEntry(Map.EntryString, String eldest) { return size() 5; } };这段代码是备选方案供大家在业务增长超出 LinkedList 能力边界时参考。5. 源码层面的关键点node() 方法与迭代器机制5.1 为什么 get(i) 在 LinkedList 里这么慢前面我反复提醒避免用 for get(i) 遍历 LinkedList现在从源码层面解释原因这样读者才能真正理解而不是死记结论。LinkedList 的 get(int index) 底层调用的是 node(int index) 方法。它的实现做了一个优化如果 index 小于 size 的一半就从头部往中间找如果 index 大于等于 size 的一半就从尾部往中间找。实际效果就是查找第 i 个节点最多只需遍历 size/2 个节点。这个优化让“单次 get”的耗时不至于太离谱但仍然做不到数组那样的直接索引时间复杂度是 O(n)。用 for 循环挨个 get等于循环里再做遍历整体就是 O(n²)。代码里可以这样理解查找任意索引时链表没有任何“跳转”能力只能沿着 next 或 prev 逐个走。就像一列火车你告诉乘务员要找第 100 节车厢的乘客乘务员只能一节一节走过去没法瞬间到达。5.2 迭代器避免重复遍历的秘密那么为什么迭代器遍历就快呢因为迭代器内部维护了一个“当前节点”的引用每次 next() 就直接返回当前节点的下一个节点从第一个节点走到最后一个节点全程只访问了 n 个节点。也就是说迭代器把“从头反复找”变成了“一次走到底”。这也是我一直在代码细节里强调遍历方式很重要的根本原因。关于迭代器还需要知道两个方法previous()向前遍历需要 ListIterator 接口支持。set(E e)迭代器在遍历时可以安全地把当前元素替换成新值。示例import java.util.LinkedList; import java.util.ListIterator; public class ListIteratorDemo { public static void main(String[] args) { LinkedListString list new LinkedList(); list.add(A); list.add(B); list.add(C); ListIteratorString it list.listIterator(); while (it.hasNext()) { String s it.next(); if (B.equals(s)) { it.set(B2); // 替换当前元素 } } System.out.println(list); // [A, B2, C] // 反向遍历 ListIteratorString reverseIt list.listIterator(list.size()); while (reverseIt.hasPrevious()) { System.out.println(reverseIt.previous()); } } }iterator() 默认从头部开始正向遍历listIterator(index) 可以指定起始位置这在某些业务里非常实用比如从中间某个位置开始向前回放日志。5.3 使用 LinkedList 时的内存布局说明这个点虽然不直接影响功能但理解之后会对“什么时候用 LinkedList”有更准确的判断。LinkedList 的每个节点除了存储元素本身还需要两个额外的引用字段空间开销比 ArrayList 大。存储大量小对象时这个差距会很明显。举个例子存储 100 万个 Integer 对象ArrayList 是一个连续数组加若干个对象引用而 LinkedList 是 100 万个节点对象每个节点都带前后指针。内存占用上 LinkedList 明显更大还伴随更多的对象头开销。所以对内存敏感的场景是个重要考量因素。另外LinkedList 的节点是逐个创建的不是连续内存。这在 JVM 里可能导致更频繁的 GC 压力因为每次 add 都会 new 一个节点对象。这一点在写高性能服务时不能忽略。6. 常见问题与排查技巧实录6.1 高频踩坑速查表问题现象根本原因解决方案迭代时删除元素抛 ConcurrentModificationException迭代过程中调用列表自身的 remove换成 iterator.remove()或者先收集再统一删除用 for get(i) 遍历 LinkedList 极慢get(i) 是 O(n) 查找整体 O(n²)使用迭代器或增强 for 循环空队列调用 getFirst/removeFirst 抛 NoSuchElementException没有先判断 isEmpty改用 peekFirst/pollFirst或提前判空remove(Object) 删除不了预期对象对象没重写 equals/hashCode自定义类重写 equals/hashCode把 LinkedList 直接当 Map 的 key 容器使用改动后 hash 失效修改了作为 key 的对象的属性key 对象设计为不可变误认为 LinkedList 所有操作都比 ArrayList 快随机访问场景下 LinkedList 反而更慢根据场景选择随机访问优先 ArrayList6.2 问题排查思路分享有一次我在排查一个接口性能问题时看到日志里某个方法耗时有 3 秒多。第一反应是数据库慢查询查了一圈发现 SQL 都是毫秒级。最后定位到代码里有一个 20000 条数据的 LinkedList用 for get(i) 做了两层循环匹配。这个案例可以说非常典型。排查这种问题有个经验法则先看数据结构再看算法复杂度。如果确认容器里有大量数据直接检查遍历代码。把循环改成迭代器之后耗时直接降到了 20 毫秒以内。这个差距比很多数据库调优来得都更明显。另外建议大家写代码的时候多想一想“这个操作的时间复杂度是多少”哪怕是粗略的估计也有帮助。比如 add(index) 在 LinkedList 里虽然是 O(1) 节点插入但要先找到 index 对应的节点所以实际上是 O(n)。只有 addFirst/addLast 和直接在迭代器当前位置插入才是真正的 O(1)。这个认识在分析算法复杂度时非常关键。6.3 一个小技巧用 ListIterator 做高效局部增删如果需求是“在遍历过程中在满足条件的元素后面插入一个元素”不要用普通的获取索引再 add 的方式而是直接用 ListIterator 的 addLinkedListString list new LinkedList(); list.add(a); list.add(b); list.add(d); ListIteratorString it list.listIterator(); while (it.hasNext()) { String s it.next(); if (b.equals(s)) { it.add(c); // 在当前位置之前插入因为迭代器已经在 b 的后面 } } System.out.println(list); // [a, b, c, d]这个 API 的优势是插入的复杂度是 O(1)不需要重新查找位置也不需要移动元素。比起先查到目标元素的索引、再调用 add(int, E)性能和代码简洁度都更好。最后聊点个人心得LinkedList 真正适合的项目场景在最后这段内容里我不想再用教学式的口吻总结什么而是分享一些我自己的选型体会。用 LinkedList 几年下来我的感受是大多数业务代码里ArrayList 是默认选项LinkedList 是“特定场景下的优化工具”。日常开发中如果只是存储和遍历数据ArrayList 足够甚至性能更好。但当业务逻辑里明确出现了“频繁头部插入”“队列消费”“栈回溯”“中间插入删除”这些动作时LinkedList 就是最顺手的选择。有一个项目里我用 LinkedList 做任务调度队列核心逻辑是把待执行任务按优先级插入队列头部消费者从尾部取任务。最初用 ArrayList 时头部插入总是拖慢整个调度器换成 LinkedList 后问题消失而且代码可读性也变好了因为 addFirst/removeLast 的语义和业务表达完全一致。另一个提示是不要在一个 LinkedList 对象上同时混合“随机访问”和“频繁插入”两种诉求那样一定会踩到性能的坑。如果你发现代码里出现对同一个 LinkedList 既做大量 get(i) 又做大量 add(index)那更合适的做法是重新设计数据结构而不是继续硬扛。最后写给刚开始学 Java 集合框架的读者LinkedList 是最好的入门“双端结构”教材弄懂了它的节点结构、引用指向、迭代器机制再去看 ArrayDeque、LinkedHashMap都会轻松很多。把这篇文章里的代码亲手敲一遍再自己设计一个小场景比如最近访问记录、任务队列、操作撤销栈去实现对 LinkedList 的理解会上升一个台阶。
