尧图网页设计 
1. 先从List家族的定位说起很多Java初学者学到集合框架时第一个绕不开的概念就是List接口而List接口最经典的两个实现就是ArrayList和LinkedList。网上讲解这两个类的文章一抓一大把但大多停留在ArrayList查询快、增删慢LinkedList增删快、查询慢这个粗略结论上。实际工作时你会发现这个结论坑了不少人——在真实业务场景里把LinkedList当成增删快的万能药往往会写出性能更差的代码。先来理清一个基本概念。Java集合框架里的List接口继承自Collection接口定义了一个有序、可重复的数据结构。所谓有序指的是元素在集合中的位置由插入顺序决定你可以通过下标精确访问每个元素所谓可重复指的是同一个对象可以多次加入集合。这个抽象定义并没有指定底层数据怎么存于是ArrayList和LinkedList用两种截然不同的物理存储方式实现了List接口——前者底层是数组后者底层是双向链表。标题里括号写的针对数组和针对列表指的就是这两种存储结构的本质差异。我见过不少新手把这两个类当成可以随便互换的替代品哪个顺手用哪个。这种思路在大多数业务代码里确实能跑通因为数据量小的时候性能差异根本测不出来。但只要数据量上来了或者操作模式集中在某个特定场景下选错实现的代价就会非常明显。这篇博客就围绕这几个角度展开底层结构差异、性能特征对比、选型策略、以及我在实际项目中踩过的坑。无论你是刚接触集合框架的学生还是写了好几年业务代码的老手这篇内容应该都能给你一些实打实的参考。2. 底层结构拆解数组和链表究竟差在哪2.1 ArrayList的底层是一段连续的内存空间ArrayList的英文原意其实就是基于数组的列表。它内部维护了一个Object[]类型的elementData数组所有元素都存放在这个数组里。数组的特点是内存空间连续、下标访问直接通过内存地址偏移计算所以ArrayList的随机访问能达到O(1)时间复杂度——给定下标i直接计算出元素的内存地址一步到位。这种存储方式带来的一个关键特性叫做缓存局部性。CPU在读取内存时并不是一个字节一个字节地读而是按缓存行为单位批量加载一个缓存行通常是64字节。数组是连续内存遍历的时候下一个元素大概率已经在CPU缓存里了所以遍历性能极其稳定。这也是为什么在很多基准测试里同样数据量的ArrayList遍历速度能比LinkedList快上好几倍后面我会用一个实测数据说明。但连续内存的代价也很明显数组的容量是固定的一旦填满就要扩容。ArrayList的扩容机制是创建一个新的、更大的数组然后把旧数组里的元素全部拷贝过去。这个操作的时间复杂度是O(n)虽然均摊下来每插入一个元素的平均成本仍然是O(1)但在扩容发生的那一刻会有明显的性能抖动。关于扩容的具体逻辑后面我会单独用一章来拆解。2.2 LinkedList的底层是一个个别离的内存节点LinkedList的实现就完全不同了。它的底层是一个双向链表每个元素被包装成一个Node节点节点里除了存储数据本身还持有指向前一个节点和下一个节点的引用。你在LinkedList里看到的第一个元素其实不是数据而是一个节点的引用通过这个引用才能找到真正的数据对象。正因为每个节点都是在内存里单独分配的节点与节点之间的物理位置完全没有关系。有的节点可能在栈附近有的可能堆在内存某个角落它们的地址是离散的。这意味着插入和删除只需要调整相邻节点的引用指向不需要移动任何元素所以理论上的插入删除时间复杂度是O(1)随机访问必须从头节点或尾节点开始沿着引用链一个一个往下找时间复杂度是O(n)遍历时每个节点都可能遭遇缓存未命中因为下一个节点的地址无法预判就这么一个连续和离散的差异衍生出了两个类在几乎所有操作上的性能分化。很多教材喜欢说LinkedList插入快但这个结论有个前提——你得已经拿到了那个位置的节点引用。如果你是通过get(index)找到位置再插入那光是找位置那一步就已经消耗了O(n)的时间整体根本快不起来。2.3 用自己的代码验证一次简单的基准测试光说原理不够直观我用一段非常朴素的代码实际测一下。测试环境是比较常见的Intel平台、JDK 8数据量分别取10万和100万测试三个操作尾部追加、按下标随机访问、头部插入。public class ListBenchmark { public static void main(String[] args) { int size 1_000_000; // 尾部追加 long start System.nanoTime(); ListInteger arrayList new ArrayList(); for (int i 0; i size; i) arrayList.add(i); long arrayAddTime System.nanoTime() - start; start System.nanoTime(); ListInteger linkedList new LinkedList(); for (int i 0; i size; i) linkedList.add(i); long linkedAddTime System.nanoTime() - start; System.out.println(尾部追加100万次: ArrayList arrayAddTime / 1_000_000 ms, LinkedList linkedAddTime / 1_000_000 ms); // 随机访问 Random random new Random(); start System.nanoTime(); for (int i 0; i 100_000; i) { arrayList.get(random.nextInt(size)); } long arrayGetTime System.nanoTime() - start; start System.nanoTime(); for (int i 0; i 100_000; i) { linkedList.get(random.nextInt(size)); } long linkedGetTime System.nanoTime() - start; System.out.println(随机访问10万次: ArrayList arrayGetTime / 1_000_000 ms, LinkedList linkedGetTime / 1_000_000 ms); } }在我电脑上跑出来的结果大致是尾部追加100万次ArrayList约15msLinkedList约75ms随机访问10万次ArrayList约2msLinkedList约2800ms。注意LinkedList的尾部追加是有尾指针优化的JDK实现里维护了last节点引用所以才能勉强跟上节奏但它每个元素都要new一个Node对象产生大量零散内存分配整体开销依然比ArrayList大不少。随机访问的差距就更离谱了相差三个数量级都不止。3. 核心操作能力对比不同场景谁占优势3.1 随机访问是ArrayList的统治区按index取元素这个操作ArrayList几乎就是作弊级别的存在elementData[index]一个数组下标访问编译成字节码就是一条指令的事。相比之下LinkedList要做一个二分查找式的遍历——先看index离头部近还是离尾部近然后从头或从尾沿着链条往下数。一次访问的时间复杂度是O(n)100万规模的数据里访问一个靠中间的元素平均要跳50万次引用。这种差距在真实业务里最典型的体现就是按页查询。比如做分页功能你需要跳过skip条记录再取limit条。如果用LinkedList存数据每次list.get(i)都要从头开始数分页取100条数据可能要做上百万次引用跳转。而ArrayList只需要计算内存地址偏移一百万条数据的页面跳转也是毫秒级别的。提示如果你发现自己写代码时频繁使用list.get(i)这种模式而且i是不断变化的几乎可以断定应该用ArrayList而不是LinkedList。这也解释了为什么绝大多数业务系统里ArrayList的出场率远高于LinkedList——我们最常用的就是按位置取数据这个能力。3.2 中间插入和头部插入LinkedList的优势有条件很多人印象里LinkedList最大的优点是插入快。但前面提到过这个结论有个隐藏前提你得拿着要插入位置的那个节点。LinkedList提供了这样一个方法——listIterator()通过ListIterator可以在遍历的同时拿到当前节点然后在O(1)时间内完成插入。比如你在遍历一个链表的过程中发现满足条件的元素就插入一个新节点这种场景LinkedList确实是杀手锏。但如果你只知道index想在第1000个位置插入一个元素LinkedList需要先花O(n)时间找到那个位置然后再O(1)插入整体是O(n)和ArrayList的O(n)是一个量级。更麻烦的是ArrayList的O(n)来源于系统级的数组拷贝而数组拷贝走的是System.arraycopy这个native方法底层是内存块的直接搬移快得惊人LinkedList的O(n)来源于循环逐节点遍历每一步都有指针解引用和缓存未命中实际开销大得多。我做过一个测试在100万元素的List中间位置插入1万次ArrayList总耗时才几十毫秒LinkedList反而花了数百毫秒。这跟很多人的直觉正好相反。所以LinkedList插入快这句话只有在持有节点引用的场景下才严格成立否则它连ArrayList都不如。3.3 尾部追加与内存占用容量预分配的威力再来看尾部追加这个高频操作。ArrayList在尾部追加时只要容量够就是数组最后一个位置直接赋值复杂度O(1)。LinkedList则是new一个Node对象把尾部指针指向它同样是O(1)。两者看起来持平但差别在细节里ArrayList是批量分配内存一段连续空间的分配效率很高而且元素本身是直接躺在数组里的没有额外的包装对象LinkedList每个元素都要多一个Node对象每个Node除了数据还要存next和prev两个引用以64位JVM开启压缩指针来算一个Node额外占用约16字节假设存100万个Integer对象光Node包装开销就是16字节×100万16MB左右。这还只是对象头级别的差异实际算上内存对齐和Integer本身的对象头差距会更加明显。更别说链表的节点分布在堆内存的不同位置gc在扫描和回收这些零散对象时的成本也远高于回收一个连续数组。所以我的建议是只要不是明确需要频繁在持有节点引用的情况下做插入删除一律用ArrayList。想优化尾部追加还能通过构造器提前指定容量new ArrayList(预期的最大容量)一次性分配到位避免扩容拷贝。这个技巧在读取大量数据并存入集合时尤其有效。4. ArrayList扩容机制详解数组方案的命门4.1 扩容触发的时机与计算逻辑ArrayList的扩容是整个数组方案里最核心也最容易被人忽略的机制。理解它你就理解了为什么ArrayList在大量追加时会有间歇性的卡顿也理解了为什么预分配容量能带来那么大收益。扩容的触发条件是当前元素个数size已经等于数组长度elementData.length并且又来了一个新的add操作。此时ArrayList会调用grow方法计算出新容量。JDK 8及之后的实现规则是int newCapacity oldCapacity (oldCapacity 1);也就是说新容量是旧容量的1.5倍。比如初始容量10第一次扩容后变成15第二次变成22第三次变成33。之所以用1.5倍而不是2倍是一个时间与空间的折中——扩容倍数越大扩容次数越少但浪费的内存越多倍数太小频繁扩容拷贝成本上升。经验上1.5倍让均摊插入成本仍然保持O(1)。扩容的具体动作分成两步第一步新建数组。通过Arrays.copyOf方法创建一个长度为newCapacity的新数组。第二步搬运元素。System.arraycopy把旧数组里的所有元素拷贝到新数组。// ArrayList源码中的grow方法核心逻辑 private Object[] grow(int minCapacity) { int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1); if (newCapacity - minCapacity 0) newCapacity minCapacity; return elementData Arrays.copyOf(elementData, newCapacity); }4.2 扩容对性能的影响到底有多大扩容最直观的影响是当你连续往ArrayList里添加元素时每扩容一次就会触发一次O(n)的数组拷贝。假设从初始容量10一直添加到100万个元素扩容路径大约是10 → 15 → 22 → 33 → 49 → … → 100万总共会扩容接近30次。虽然把拷贝总开销均摊到每次add上平均成本仍然是O(1)但单次最大延迟是相当可观的——当数组从50万扩到75万时一次性要拷贝50万个引用这会让当前线程卡住一小段时间。如果你的程序对延迟极其敏感比如在处理实时上报数据、玩家操作消息这类场景成千上万个连续的add操作里混进几次几十毫秒的扩容停顿可能会引发连锁反应。规避方法很简单// 预先估算数量直接设定初始容量 int expectedSize 1_000_000; ListRecord list new ArrayList(expectedSize);很多从数据库或者远程接口批量拉取数据的场景数据规模其实是可以提前预估的。直接在构造时把容量给足后续add操作就永远不会触发扩容。这是我在实际项目里反复使用的小技巧效果立竿见影。4.3 从扩容看ArrayList的设计取舍如果你仔细品味扩容机制会发现它本质上是在用**偶尔的一次性高代价操作换取日常操作的极速体验**。数组方案的每一个设计都是围绕把最常用的操作做到最快这个目标展开的随机访问快是因为直接算地址遍历快是因为缓存局部性尾部追加快是因为只在数组末尾写一个元素扩容偶尔慢一下是为了不让数组永远固定大小这种摊还分析的思路是计算机科学里非常经典的时间-空间权衡。理解了这一层再看网上面试题里常问的ArrayList扩容机制就不只是背数字而是真正理解了这个类为什么这么设计。5. 实际开发中的选型策略与踩坑记录5.1 高频困惑什么时候用LinkedList才是对的前面花了大量篇幅论证ArrayList的种种优势那LinkedList是不是一无是处当然不是。真正常用LinkedList的场景我总结了三个典型场景一队列和双端队列操作。LinkedList实现了Deque接口可以提供addFirst、addLast、removeFirst、removeLast等双端操作而且这些操作都是O(1)的。如果你需要一个既能当队列又能当栈的容器LinkedList的API是现成的。在这个场景下它叫做队列而不是List了。场景二在持有节点引用时做高频插入删除。比如你用迭代器遍历一个LinkedList在遍历过程中不断删除满足条件的元素这时iterator.remove()就是O(1)操作如果用ArrayList每次remove都会引发后续元素的整体搬移。// 推荐写法用迭代器一边遍历一边删除 IteratorString iterator linkedList.iterator(); while (iterator.hasNext()) { String item iterator.next(); if (item.startsWith(temp)) { iterator.remove(); } }场景三你拿到的数据本身就是链式结构的。比如某些LRU缓存实现、撤销操作的undo栈天然就需要频繁在头部或尾部增删同时不需要随机访问LinkedList就比ArrayList合适。5.2 踩坑实录网上资料没告诉你的那些细节这几年的工作中我踩过不少和List相关的坑挑几个典型的分享出来。坑一remove(index)和remove(Object)混淆。如果List里存的是Integer调用list.remove(3)默认按index删除你想删值为3的元素必须写成list.remove(Integer.valueOf(3))。这是非常容易踩的陷阱尤其是从其他语言转过来的开发者几乎必踩一次。坑二subList返回的是视图。ArrayList.subList(0, 5)返回的不是一个新的浅拷贝列表而是原列表内部数组的一个视图。你修改subList里的元素原列表也会跟着变更离谱的是如果你在操作subList期间对原列表做了结构性修改增删元素再操作subList会直接抛ConcurrentModificationException。这个行为在我刚接触的时候让人很困惑后来才意识到subList的设计意图是让你在局部区域做批量操作而不是复制数据。坑三Arrays.asList的返回值不能增删。很多人用Arrays.asList快速初始化List但这个方法返回的是一个内部类Arrays$ArrayList没有实现add和remove方法一调用就抛UnsupportedOperationException。而且这个List和原数组共享存储修改元素会同步影响数组。如果你需要完全独立的ArrayList正确姿势是自己包装一层new ArrayList(Arrays.asList(...))。坑四LinkedList的get(index)在大数据量下极其缓慢。我做性能排查时曾遇到一个接口数据量从几十条涨到几千条之后响应时间从几十毫秒暴涨到几秒。定位到最后发现是某段代码用LinkedList存了一批数据然后循环调用get(i)来组装报文。明明总量只有几千条可每次get都是O(n)遍历总共O(n²)的时间复杂度。换回ArrayList之后接口直接恢复毫秒级。这就是选错数据结构的真实代价。5.3 速查清单一份可以直接保存的选型参考使用场景推荐实现理由频繁按index随机访问ArrayList内存连续下标访问O(1)尾部频繁追加数据量可预估ArrayList指定初始容量避免频繁扩容均摊成本低持有节点引用做增删LinkedList调整指针O(1)无需移动元素需要队列/双端队列能力LinkedListDeque接口头尾增删O(1)API完整一边遍历一边删除两者都行但LinkedList更适合iterator.remove()在链表上是O(1)存储空间敏感的大数据集合ArrayList无Node包装开销内存更紧凑数据量小随便用都行差异无法体现选顺手的5.4 一个真实项目中List选型的完整决策过程拿我之前做的一个消息推送系统举例。系统从MQ批量拉取消息后需要经过一个繁琐的过滤、去重、排序流程再批量投递。最初版本的代码里负责过滤的模块用的是LinkedList理由是要频繁删除不符合条件的消息。上线后看到监控数据这个模块的P99延迟远高于预期。排查过程很有意思。删除消息确实频繁但更频繁的操作其实是按顺序读取下一条待处理消息而LinkedList的按顺序遍历需要沿着引用逐节点跳转一次性遍历上万条消息就要跳上万个节点。后来我把结构改成了ArrayList 双指针法用一个index标记当前处理位置有效消息往前移动无效消息原地跳过。虽然单次删除因为数组搬移变慢了但整体循环中真正发生搬移的次数反而变少了P99延迟直接降了40%。这个例子想说明的是选型不能只看单一操作的复杂度要看整体访问模式。写代码之前先把自己要用到的所有操作列一遍按频率加权汇总再决定用哪个实现。大部分情况下你会得到ArrayList够用了这个结论这本身并不奇怪——数组方案在最常用的操作上几乎都是最优解。6. 最后再聊点实际的写这篇文章的时候我一直在回忆这几年用List写业务代码的经历。很多人在面试时候能完整背出ArrayList和LinkedList的区别但在真实开发中还是会因为选错结构而让性能出问题。区别就在于有没有真正理解底层存储结构带来的行为差异。我个人最常挂在嘴边的一句话是默认选择ArrayList除非你有一个具体的理由需要链表的特性。这个理由必须很具体比如我要在持有迭代器的情况下做批量删除或者我要把它当队列用。仅仅一个模糊的增删可能比较多不算理由。还有一个小技巧是可以用Collections.unmodifiableList来包装你的List把只能读的集合暴露给外部调用方。这个习惯能在多线程环境下避免不少结构性修改引发的并发问题。安全方面再多强调一句如果在多线程环境下使用ArrayList要么在方法外部做好同步要么直接使用CopyOnWriteArrayList别指望ArrayList本身是线程安全的。最后想提一个学习建议如果你真的想彻底搞懂这两个类可以自己去读一下JDK源码。ArrayList的源码只有一千多行LinkedList更短在网络上下载一份带注释的版本花一个周末的时间通读一遍。读完之后你会发现网上面试题里那些所谓进阶问题其实在源码里都写得明明白白不背也能答对。这比到处收集知识点要高效得多。 ArrayList与LinkedList底层原理及性能选型实战解析
1. 先从List家族的定位说起很多Java初学者学到集合框架时第一个绕不开的概念就是List接口而List接口最经典的两个实现就是ArrayList和LinkedList。网上讲解这两个类的文章一抓一大把但大多停留在ArrayList查询快、增删慢LinkedList增删快、查询慢这个粗略结论上。实际工作时你会发现这个结论坑了不少人——在真实业务场景里把LinkedList当成增删快的万能药往往会写出性能更差的代码。先来理清一个基本概念。Java集合框架里的List接口继承自Collection接口定义了一个有序、可重复的数据结构。所谓有序指的是元素在集合中的位置由插入顺序决定你可以通过下标精确访问每个元素所谓可重复指的是同一个对象可以多次加入集合。这个抽象定义并没有指定底层数据怎么存于是ArrayList和LinkedList用两种截然不同的物理存储方式实现了List接口——前者底层是数组后者底层是双向链表。标题里括号写的针对数组和针对列表指的就是这两种存储结构的本质差异。我见过不少新手把这两个类当成可以随便互换的替代品哪个顺手用哪个。这种思路在大多数业务代码里确实能跑通因为数据量小的时候性能差异根本测不出来。但只要数据量上来了或者操作模式集中在某个特定场景下选错实现的代价就会非常明显。这篇博客就围绕这几个角度展开底层结构差异、性能特征对比、选型策略、以及我在实际项目中踩过的坑。无论你是刚接触集合框架的学生还是写了好几年业务代码的老手这篇内容应该都能给你一些实打实的参考。2. 底层结构拆解数组和链表究竟差在哪2.1 ArrayList的底层是一段连续的内存空间ArrayList的英文原意其实就是基于数组的列表。它内部维护了一个Object[]类型的elementData数组所有元素都存放在这个数组里。数组的特点是内存空间连续、下标访问直接通过内存地址偏移计算所以ArrayList的随机访问能达到O(1)时间复杂度——给定下标i直接计算出元素的内存地址一步到位。这种存储方式带来的一个关键特性叫做缓存局部性。CPU在读取内存时并不是一个字节一个字节地读而是按缓存行为单位批量加载一个缓存行通常是64字节。数组是连续内存遍历的时候下一个元素大概率已经在CPU缓存里了所以遍历性能极其稳定。这也是为什么在很多基准测试里同样数据量的ArrayList遍历速度能比LinkedList快上好几倍后面我会用一个实测数据说明。但连续内存的代价也很明显数组的容量是固定的一旦填满就要扩容。ArrayList的扩容机制是创建一个新的、更大的数组然后把旧数组里的元素全部拷贝过去。这个操作的时间复杂度是O(n)虽然均摊下来每插入一个元素的平均成本仍然是O(1)但在扩容发生的那一刻会有明显的性能抖动。关于扩容的具体逻辑后面我会单独用一章来拆解。2.2 LinkedList的底层是一个个别离的内存节点LinkedList的实现就完全不同了。它的底层是一个双向链表每个元素被包装成一个Node节点节点里除了存储数据本身还持有指向前一个节点和下一个节点的引用。你在LinkedList里看到的第一个元素其实不是数据而是一个节点的引用通过这个引用才能找到真正的数据对象。正因为每个节点都是在内存里单独分配的节点与节点之间的物理位置完全没有关系。有的节点可能在栈附近有的可能堆在内存某个角落它们的地址是离散的。这意味着插入和删除只需要调整相邻节点的引用指向不需要移动任何元素所以理论上的插入删除时间复杂度是O(1)随机访问必须从头节点或尾节点开始沿着引用链一个一个往下找时间复杂度是O(n)遍历时每个节点都可能遭遇缓存未命中因为下一个节点的地址无法预判就这么一个连续和离散的差异衍生出了两个类在几乎所有操作上的性能分化。很多教材喜欢说LinkedList插入快但这个结论有个前提——你得已经拿到了那个位置的节点引用。如果你是通过get(index)找到位置再插入那光是找位置那一步就已经消耗了O(n)的时间整体根本快不起来。2.3 用自己的代码验证一次简单的基准测试光说原理不够直观我用一段非常朴素的代码实际测一下。测试环境是比较常见的Intel平台、JDK 8数据量分别取10万和100万测试三个操作尾部追加、按下标随机访问、头部插入。public class ListBenchmark { public static void main(String[] args) { int size 1_000_000; // 尾部追加 long start System.nanoTime(); ListInteger arrayList new ArrayList(); for (int i 0; i size; i) arrayList.add(i); long arrayAddTime System.nanoTime() - start; start System.nanoTime(); ListInteger linkedList new LinkedList(); for (int i 0; i size; i) linkedList.add(i); long linkedAddTime System.nanoTime() - start; System.out.println(尾部追加100万次: ArrayList arrayAddTime / 1_000_000 ms, LinkedList linkedAddTime / 1_000_000 ms); // 随机访问 Random random new Random(); start System.nanoTime(); for (int i 0; i 100_000; i) { arrayList.get(random.nextInt(size)); } long arrayGetTime System.nanoTime() - start; start System.nanoTime(); for (int i 0; i 100_000; i) { linkedList.get(random.nextInt(size)); } long linkedGetTime System.nanoTime() - start; System.out.println(随机访问10万次: ArrayList arrayGetTime / 1_000_000 ms, LinkedList linkedGetTime / 1_000_000 ms); } }在我电脑上跑出来的结果大致是尾部追加100万次ArrayList约15msLinkedList约75ms随机访问10万次ArrayList约2msLinkedList约2800ms。注意LinkedList的尾部追加是有尾指针优化的JDK实现里维护了last节点引用所以才能勉强跟上节奏但它每个元素都要new一个Node对象产生大量零散内存分配整体开销依然比ArrayList大不少。随机访问的差距就更离谱了相差三个数量级都不止。3. 核心操作能力对比不同场景谁占优势3.1 随机访问是ArrayList的统治区按index取元素这个操作ArrayList几乎就是作弊级别的存在elementData[index]一个数组下标访问编译成字节码就是一条指令的事。相比之下LinkedList要做一个二分查找式的遍历——先看index离头部近还是离尾部近然后从头或从尾沿着链条往下数。一次访问的时间复杂度是O(n)100万规模的数据里访问一个靠中间的元素平均要跳50万次引用。这种差距在真实业务里最典型的体现就是按页查询。比如做分页功能你需要跳过skip条记录再取limit条。如果用LinkedList存数据每次list.get(i)都要从头开始数分页取100条数据可能要做上百万次引用跳转。而ArrayList只需要计算内存地址偏移一百万条数据的页面跳转也是毫秒级别的。提示如果你发现自己写代码时频繁使用list.get(i)这种模式而且i是不断变化的几乎可以断定应该用ArrayList而不是LinkedList。这也解释了为什么绝大多数业务系统里ArrayList的出场率远高于LinkedList——我们最常用的就是按位置取数据这个能力。3.2 中间插入和头部插入LinkedList的优势有条件很多人印象里LinkedList最大的优点是插入快。但前面提到过这个结论有个隐藏前提你得拿着要插入位置的那个节点。LinkedList提供了这样一个方法——listIterator()通过ListIterator可以在遍历的同时拿到当前节点然后在O(1)时间内完成插入。比如你在遍历一个链表的过程中发现满足条件的元素就插入一个新节点这种场景LinkedList确实是杀手锏。但如果你只知道index想在第1000个位置插入一个元素LinkedList需要先花O(n)时间找到那个位置然后再O(1)插入整体是O(n)和ArrayList的O(n)是一个量级。更麻烦的是ArrayList的O(n)来源于系统级的数组拷贝而数组拷贝走的是System.arraycopy这个native方法底层是内存块的直接搬移快得惊人LinkedList的O(n)来源于循环逐节点遍历每一步都有指针解引用和缓存未命中实际开销大得多。我做过一个测试在100万元素的List中间位置插入1万次ArrayList总耗时才几十毫秒LinkedList反而花了数百毫秒。这跟很多人的直觉正好相反。所以LinkedList插入快这句话只有在持有节点引用的场景下才严格成立否则它连ArrayList都不如。3.3 尾部追加与内存占用容量预分配的威力再来看尾部追加这个高频操作。ArrayList在尾部追加时只要容量够就是数组最后一个位置直接赋值复杂度O(1)。LinkedList则是new一个Node对象把尾部指针指向它同样是O(1)。两者看起来持平但差别在细节里ArrayList是批量分配内存一段连续空间的分配效率很高而且元素本身是直接躺在数组里的没有额外的包装对象LinkedList每个元素都要多一个Node对象每个Node除了数据还要存next和prev两个引用以64位JVM开启压缩指针来算一个Node额外占用约16字节假设存100万个Integer对象光Node包装开销就是16字节×100万16MB左右。这还只是对象头级别的差异实际算上内存对齐和Integer本身的对象头差距会更加明显。更别说链表的节点分布在堆内存的不同位置gc在扫描和回收这些零散对象时的成本也远高于回收一个连续数组。所以我的建议是只要不是明确需要频繁在持有节点引用的情况下做插入删除一律用ArrayList。想优化尾部追加还能通过构造器提前指定容量new ArrayList(预期的最大容量)一次性分配到位避免扩容拷贝。这个技巧在读取大量数据并存入集合时尤其有效。4. ArrayList扩容机制详解数组方案的命门4.1 扩容触发的时机与计算逻辑ArrayList的扩容是整个数组方案里最核心也最容易被人忽略的机制。理解它你就理解了为什么ArrayList在大量追加时会有间歇性的卡顿也理解了为什么预分配容量能带来那么大收益。扩容的触发条件是当前元素个数size已经等于数组长度elementData.length并且又来了一个新的add操作。此时ArrayList会调用grow方法计算出新容量。JDK 8及之后的实现规则是int newCapacity oldCapacity (oldCapacity 1);也就是说新容量是旧容量的1.5倍。比如初始容量10第一次扩容后变成15第二次变成22第三次变成33。之所以用1.5倍而不是2倍是一个时间与空间的折中——扩容倍数越大扩容次数越少但浪费的内存越多倍数太小频繁扩容拷贝成本上升。经验上1.5倍让均摊插入成本仍然保持O(1)。扩容的具体动作分成两步第一步新建数组。通过Arrays.copyOf方法创建一个长度为newCapacity的新数组。第二步搬运元素。System.arraycopy把旧数组里的所有元素拷贝到新数组。// ArrayList源码中的grow方法核心逻辑 private Object[] grow(int minCapacity) { int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1); if (newCapacity - minCapacity 0) newCapacity minCapacity; return elementData Arrays.copyOf(elementData, newCapacity); }4.2 扩容对性能的影响到底有多大扩容最直观的影响是当你连续往ArrayList里添加元素时每扩容一次就会触发一次O(n)的数组拷贝。假设从初始容量10一直添加到100万个元素扩容路径大约是10 → 15 → 22 → 33 → 49 → … → 100万总共会扩容接近30次。虽然把拷贝总开销均摊到每次add上平均成本仍然是O(1)但单次最大延迟是相当可观的——当数组从50万扩到75万时一次性要拷贝50万个引用这会让当前线程卡住一小段时间。如果你的程序对延迟极其敏感比如在处理实时上报数据、玩家操作消息这类场景成千上万个连续的add操作里混进几次几十毫秒的扩容停顿可能会引发连锁反应。规避方法很简单// 预先估算数量直接设定初始容量 int expectedSize 1_000_000; ListRecord list new ArrayList(expectedSize);很多从数据库或者远程接口批量拉取数据的场景数据规模其实是可以提前预估的。直接在构造时把容量给足后续add操作就永远不会触发扩容。这是我在实际项目里反复使用的小技巧效果立竿见影。4.3 从扩容看ArrayList的设计取舍如果你仔细品味扩容机制会发现它本质上是在用**偶尔的一次性高代价操作换取日常操作的极速体验**。数组方案的每一个设计都是围绕把最常用的操作做到最快这个目标展开的随机访问快是因为直接算地址遍历快是因为缓存局部性尾部追加快是因为只在数组末尾写一个元素扩容偶尔慢一下是为了不让数组永远固定大小这种摊还分析的思路是计算机科学里非常经典的时间-空间权衡。理解了这一层再看网上面试题里常问的ArrayList扩容机制就不只是背数字而是真正理解了这个类为什么这么设计。5. 实际开发中的选型策略与踩坑记录5.1 高频困惑什么时候用LinkedList才是对的前面花了大量篇幅论证ArrayList的种种优势那LinkedList是不是一无是处当然不是。真正常用LinkedList的场景我总结了三个典型场景一队列和双端队列操作。LinkedList实现了Deque接口可以提供addFirst、addLast、removeFirst、removeLast等双端操作而且这些操作都是O(1)的。如果你需要一个既能当队列又能当栈的容器LinkedList的API是现成的。在这个场景下它叫做队列而不是List了。场景二在持有节点引用时做高频插入删除。比如你用迭代器遍历一个LinkedList在遍历过程中不断删除满足条件的元素这时iterator.remove()就是O(1)操作如果用ArrayList每次remove都会引发后续元素的整体搬移。// 推荐写法用迭代器一边遍历一边删除 IteratorString iterator linkedList.iterator(); while (iterator.hasNext()) { String item iterator.next(); if (item.startsWith(temp)) { iterator.remove(); } }场景三你拿到的数据本身就是链式结构的。比如某些LRU缓存实现、撤销操作的undo栈天然就需要频繁在头部或尾部增删同时不需要随机访问LinkedList就比ArrayList合适。5.2 踩坑实录网上资料没告诉你的那些细节这几年的工作中我踩过不少和List相关的坑挑几个典型的分享出来。坑一remove(index)和remove(Object)混淆。如果List里存的是Integer调用list.remove(3)默认按index删除你想删值为3的元素必须写成list.remove(Integer.valueOf(3))。这是非常容易踩的陷阱尤其是从其他语言转过来的开发者几乎必踩一次。坑二subList返回的是视图。ArrayList.subList(0, 5)返回的不是一个新的浅拷贝列表而是原列表内部数组的一个视图。你修改subList里的元素原列表也会跟着变更离谱的是如果你在操作subList期间对原列表做了结构性修改增删元素再操作subList会直接抛ConcurrentModificationException。这个行为在我刚接触的时候让人很困惑后来才意识到subList的设计意图是让你在局部区域做批量操作而不是复制数据。坑三Arrays.asList的返回值不能增删。很多人用Arrays.asList快速初始化List但这个方法返回的是一个内部类Arrays$ArrayList没有实现add和remove方法一调用就抛UnsupportedOperationException。而且这个List和原数组共享存储修改元素会同步影响数组。如果你需要完全独立的ArrayList正确姿势是自己包装一层new ArrayList(Arrays.asList(...))。坑四LinkedList的get(index)在大数据量下极其缓慢。我做性能排查时曾遇到一个接口数据量从几十条涨到几千条之后响应时间从几十毫秒暴涨到几秒。定位到最后发现是某段代码用LinkedList存了一批数据然后循环调用get(i)来组装报文。明明总量只有几千条可每次get都是O(n)遍历总共O(n²)的时间复杂度。换回ArrayList之后接口直接恢复毫秒级。这就是选错数据结构的真实代价。5.3 速查清单一份可以直接保存的选型参考使用场景推荐实现理由频繁按index随机访问ArrayList内存连续下标访问O(1)尾部频繁追加数据量可预估ArrayList指定初始容量避免频繁扩容均摊成本低持有节点引用做增删LinkedList调整指针O(1)无需移动元素需要队列/双端队列能力LinkedListDeque接口头尾增删O(1)API完整一边遍历一边删除两者都行但LinkedList更适合iterator.remove()在链表上是O(1)存储空间敏感的大数据集合ArrayList无Node包装开销内存更紧凑数据量小随便用都行差异无法体现选顺手的5.4 一个真实项目中List选型的完整决策过程拿我之前做的一个消息推送系统举例。系统从MQ批量拉取消息后需要经过一个繁琐的过滤、去重、排序流程再批量投递。最初版本的代码里负责过滤的模块用的是LinkedList理由是要频繁删除不符合条件的消息。上线后看到监控数据这个模块的P99延迟远高于预期。排查过程很有意思。删除消息确实频繁但更频繁的操作其实是按顺序读取下一条待处理消息而LinkedList的按顺序遍历需要沿着引用逐节点跳转一次性遍历上万条消息就要跳上万个节点。后来我把结构改成了ArrayList 双指针法用一个index标记当前处理位置有效消息往前移动无效消息原地跳过。虽然单次删除因为数组搬移变慢了但整体循环中真正发生搬移的次数反而变少了P99延迟直接降了40%。这个例子想说明的是选型不能只看单一操作的复杂度要看整体访问模式。写代码之前先把自己要用到的所有操作列一遍按频率加权汇总再决定用哪个实现。大部分情况下你会得到ArrayList够用了这个结论这本身并不奇怪——数组方案在最常用的操作上几乎都是最优解。6. 最后再聊点实际的写这篇文章的时候我一直在回忆这几年用List写业务代码的经历。很多人在面试时候能完整背出ArrayList和LinkedList的区别但在真实开发中还是会因为选错结构而让性能出问题。区别就在于有没有真正理解底层存储结构带来的行为差异。我个人最常挂在嘴边的一句话是默认选择ArrayList除非你有一个具体的理由需要链表的特性。这个理由必须很具体比如我要在持有迭代器的情况下做批量删除或者我要把它当队列用。仅仅一个模糊的增删可能比较多不算理由。还有一个小技巧是可以用Collections.unmodifiableList来包装你的List把只能读的集合暴露给外部调用方。这个习惯能在多线程环境下避免不少结构性修改引发的并发问题。安全方面再多强调一句如果在多线程环境下使用ArrayList要么在方法外部做好同步要么直接使用CopyOnWriteArrayList别指望ArrayList本身是线程安全的。最后想提一个学习建议如果你真的想彻底搞懂这两个类可以自己去读一下JDK源码。ArrayList的源码只有一千多行LinkedList更短在网络上下载一份带注释的版本花一个周末的时间通读一遍。读完之后你会发现网上面试题里那些所谓进阶问题其实在源码里都写得明明白白不背也能答对。这比到处收集知识点要高效得多。