1. 从一道面试题说起ArrayList到底是什么在Java开发圈子里ArrayList绝对是使用频率最高的集合类之一。日常写代码时List list new ArrayList();这行代码几乎是肌肉记忆。但很多用了三五年的老手面对ArrayList的底层结构是什么扩容机制具体怎么工作为什么说ArrayList查询快增删慢这类问题时依然只能答个大概。我曾经做过一段时间的Java面试官每次问到集合相关的问题十个候选人里至少有七八个会说ArrayList底层是数组查询快是因为有索引插入删除慢是因为要移动元素。这个回答对吗大体方向没错但往深了问一层扩容具体是怎么扩的扩多少为什么是1.5倍而不是2倍ArrayList里有一个modCount字段是干什么用的subList方法返回的视图为什么不能修改——能答上来的人就少多了。这篇内容就从源码角度把ArrayList和顺序表这个概念彻底拆开揉碎。我会先讲清楚顺序表是什么、ArrayList和顺序表的关系然后把底层数组、扩容机制、序列化设计、费时操作逐个剖析最后放一组ArrayList和LinkedList的对比测试数据并分享一些实战中容易踩的坑。如果你是刚学Java的初学者这篇文章能帮你把数据结构的基础打牢如果你已经工作了几年但一直没深挖过集合源码这篇可以帮你补齐知识盲区。2. ArrayList在Java集合框架中的定位2.1 List接口与顺序表的关系数据结构教科书里线性表分为顺序存储和链式存储两种。顺序存储就是用一块连续的存储空间依次存放数据元素在Java里体现为数组链式存储则是通过指针把各个元素串起来在Java里体现为链表。顺序表就是基于数组实现的线性表。ArrayList从名字上就能看出来——Array数组 List列表它的本质就是一张用数组做底层存储的动态顺序表。所谓的动态是指它可以自动扩容不用像普通数组那样一开始就固定长度。Java的集合框架里List是一个顶层接口规范了有序、可重复、允许null元素、支持索引访问等行为特征。ArrayList实现了List接口同时继承了AbstractList抽象类。AbstractList帮它实现了一部分通用的逻辑比如iterator()方法、equals()和hashCode()等子类只需要专注实现get(int index)、add(E element)这些和底层存储相关的核心方法就行。看ArrayList的类声明完整写法是public class ArrayListE extends AbstractListE implements ListE, RandomAccess, Cloneable, java.io.Serializable注意它implements了RandomAccess。这是一个标志性接口里面什么方法都没有纯粹是给List实现类贴了一个标签表示我支持快速随机访问。判断一个List支不支持高效随机访问可以用instanceof RandomAccess来判断。Collections工具类里的一些算法比如binarySearch二分查找就会检查这个接口从而决定采用索引遍历还是迭代器遍历。ArrayList还实现了Cloneable和Serializable。Cloneable表示可以调用clone()方法做浅拷贝Serializable表示可以被序列化。这两个接口后面还会提到尤其是序列化ArrayList做了一个非常有意思的定制。2.2 ArrayList在List家族中的位置List接口下有三个经典实现ArrayList、LinkedList、Vector。三者对比是Java基础面试的保留节目。特性ArrayListLinkedListVector底层结构Object[]数组双向链表Object[]数组随机访问O(1)实现了RandomAccessO(n)需要从头遍历O(1)实现了RandomAccess头部/中间插入O(n)需要搬移元素头部O(1)但按索引插入为O(n)O(n)需要搬移元素尾部追加均摊O(1)O(1)O(1)且方法用synchronized修饰线程安全否否是但代价是性能低扩容策略1.5倍扩容无固定容量概念可按指定增量扩容默认2倍Vector是一个元老级的类从Java 1.0就有了。它的主要特点是几乎所有方法都加了synchronized线程安全但也就意味着同一时间只有一个线程能执行操作在单线程环境下性能远不如ArrayList。所以Vector现在基本已经被淘汰了官方注释里也建议不再使用。LinkedList底层是双向链表每个节点除了存数据还存了前驱和后继的引用。它实现了List接口和Deque接口所以既可以当列表用也可以当双端队列用。很多人因为教科书上写着链表插入删除快就认为LinkedList在插入方面全面胜出实际操作中并非如此——按索引插入的时候它还需要先从头或尾遍历找到那个位置照样是O(n)的。这个问题后面会详细说。3. ArrayList底层结构深入解析3.1 核心成员变量与构造方法ArrayList的底层核心就是一个Object数组以及几个用来标记状态的成员变量。先把源码亮出来private static final int DEFAULT_CAPACITY 10; private static final Object[] EMPTY_ELEMENTDATA {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; transient Object[] elementData; private int size;有几个细节值得展开讲一讲。elementData数组被transient修饰了这意味着数组本身不参与默认的序列化。但ArrayList又implements了Serializable这不矛盾吗不矛盾因为ArrayList重写了writeObject和readObject两个方法自己实现了序列化逻辑。它这么做的原因是数组的实际容量elementData.length往往比元素个数size大如果把整个数组序列化出去会多写很多null占位符白白浪费存储空间和IO开销。所以它只序列化有真实数据的部分按需扩容地写入和恢复。这是我个人觉得ArrayList设计上很精妙的一个点后面会专门分析。再看构造方法一共有三个public ArrayList() { this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } public ArrayList(int initialCapacity) { if (initialCapacity 0) { this.elementData new Object[initialCapacity]; } else if (initialCapacity 0) { this.elementData EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException(Illegal Capacity: initialCapacity); } } public ArrayList(Collection? extends E c) { elementData c.toArray(); if ((size elementData.length) ! 0) { // c.toArray()可能返回的不是Object[]类型需要额外判断 if (elementData.getClass() ! Object[].class) elementData Arrays.copyOf(elementData, size, Object[].class); } else { this.elementData EMPTY_ELEMENTDATA; } }新手容易忽略的一个细节是new ArrayList()并不代表一开始就分配10个长度的数组。它先指向一个空的共享数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA真正开辟10个长度的数组是在第一次add元素的时候。这个设计叫懒加载目的是节省内存——很多ArrayList创建后并不一定会马上使用或者根本没存几个元素没必要提前占着一块内存。还有构造方法里elementData.getClass() ! Object[].class这个判断。Arrays.asList返回的Arrays$ArrayList内部持有的就是Object[]c.toArray()直接返回原数组引用类型没问题。但有些集合的toArray()返回的是具体类型的数组比如String[]如果不转成Object[]后续ArrayList往数组里写别的类型元素时就会触发ArrayStoreException。所以这里做了一个防御性转换。3.2 索引访问与get/set的实现逻辑顺序表在数据结构层面的最大优势就是随机访问。数组在内存中是连续分配的只需要用首地址 索引 × 每个元素大小就能算出目标元素的地址即常数时间O(1)。ArrayList的get方法底层调用的就是这个逻辑public E get(int index) { Objects.checkIndex(index, size); return elementData(index); } SuppressWarnings(unchecked) E elementData(int index) { return (E) elementData[index]; }注意它做了范围检查索引越界会抛出IndexOutOfBoundsException。这是ArrayList比C语言原生数组强的点——它帮开发者拦住了越界的风险。set方法也类似先校验索引范围再替换对应位置的元素返回旧值public E set(int index, E element) { Objects.checkIndex(index, size); E oldValue elementData(index); elementData[index] element; return oldValue; }这些方法本身逻辑简单但它们是整个集合类安全性的基石。Java在语言层面就把数组越界的兜底做掉了这也是为什么骨架代码里很少出现越界bug的原因之一。4. 扩容机制的系统性拆解4.1 add方法如何触发扩容ArrayList最有技术含量的部分就是扩容。先看add方法的调用链public boolean add(E e) { modCount; add(e, elementData, size); return true; } private void add(E e, Object[] elementData, int s) { if (s elementData.length) elementData grow(); elementData[s] e; size s 1; }注意源码里有一个add(E e, Object[] elementData, int s)的私有重载这个写法是在Java 9之后才有的优化——先把elementData的引用存到局部变量避免在add操作中重复访问this.elementData字段。这个细节倒是体现了JDK开发者在性能上的锱铢必较。当size等于数组长度时说明数组满了需要调用grow()方法来扩容。private Object[] grow() { return grow(size 1); } private Object[] grow(int minCapacity) { int oldCapacity elementData.length; if (oldCapacity 0 || elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, oldCapacity 1); return elementData Arrays.copyOf(elementData, newCapacity); } else { return elementData new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; } }这段代码有几个关键逻辑点第一如果是使用无参构造器创建的空列表第一次add时会直接分配DEFAULT_CAPACITY10长度的数组。第二如果oldCapacity大于0扩容量是oldCapacity 1也就是原来的一半。新容量旧容量 旧容量的一半 1.5倍。第三ArraysSupport.newLength会综合处理传入的扩增量是否足够新容量是否溢出等问题确保最终容量至少满足minCapacity需求。我个人很喜欢这个设计。1.5倍扩容是一个经过充分权衡的值。扩容系数太大比如2倍内存浪费严重——如果你的列表最终只需要1000个位置2倍扩容可能要分配合约1024或2048的数组扩容系数太小比如1.1倍扩容次数会变得频繁copyOf操作带来的数组复制成本会持续叠加。1.5倍算是在内存占用和扩容次数之间取了一个平衡点。4.2 Arrays.copyOf与System.arraycopy的实际工作grow()方法里头调用了Arrays.copyOf来复制数组。这个方法本质上又是调的System.arraycopy这是一个native方法底层由JVM直接调用操作系统级别的内存复制函数效率极高。public static T T[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass()); }System.arraycopy的签名是这样的public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);它做的事情很简单——从源数组的srcPos位置开始复制length个元素到目标数组的destPos位置。因为是native方法它不受Java虚拟机栈的限制通常在内存层面用类似memcpy的方式批量搬运数据。数组扩容的整个过程可以理解为计算新容量newCapacity oldCapacity (oldCapacity 1)用newCapacity创建一个新数组把旧数组中的size个元素一次性搬进新数组把ArrayList内部的elementData引用指向新数组旧数组等待垃圾回收从O(n)的角度看单次扩容的时间复杂度是O(n)。但因为扩容是偶发的——每隔旧容量/2次add才会触发一次——所以把扩容的代价均摊到每一次add上均摊复杂度仍然是O(1)。这个分析方式在数据结构的摊还分析章节里是标准内容。从Java 8到Java 17扩容的代码逻辑没有本质变化1.5倍这个系数一直没改。我见过有人在网上讨论为什么不用黄金分割比例0.618来扩容说真的没太大必要——1.5倍在大量实测中的表现已经足够好了。除非你能证明你的特定业务场景对扩容系数极度敏感否则别在这种地方钻牛角尖。4.3 扩容产生的时间和空间代价扩容不是免费的。每次扩容发生的那一刻需要完成一次O(n)的全量复制其中n是当前元素个数。假设初始容量10依次扩容到15、22、33、49、74...扩容的累积复制成本大致是旧数组长度之和也就是O(n)级别。这里有一个典型的性能权衡如果事先能预估数据量通过构造方法直接初始化一个足够大的容量可以完全避免扩容操作。很多人在业务代码里习惯new ArrayList()然后把几万条数据一条条add进去这期间可能发生了好多次复制。改成new ArrayList(expectedSize)之后一次扩容都不用发生整体耗时能省不少。后面实战部分会再给一个具体的压测对比。内存方面扩容瞬间会同时存在旧数组和新数组JVM内存占用会有一个短暂的峰值。如果列表特别大比如百万级元素这个峰值可能会导致一次Minor GC甚至Full GC的触发。在内存受限的服务器上这是值得警惕的。5. 从数据结构视角看ArrayList的性能5.1 为什么说随机访问是O(1)从CPU的角度解释一下为什么数组随机访问快。数组在内存里是连续排列的内存地址计算只有一步base_offset index * element_size。CPU拿到这个地址后可以直接发起内存访问请求。更妙的是现代CPU有缓存分层结构L1/L2/L3缓存按缓存行通常64字节从内存预取数据。数组是连续存储的遍历数组时第一个元素被加载进缓存后后面多个相邻元素大概率已经跟着进了缓存命中率极高。链表的节点在内存中是分散的遍历链表时每访问一个节点几乎都意味着一次缓存未命中cache miss需要从主存甚至更远的地方加载数据。缓存未命中的延迟比L1缓存命中高一个数量级。这就是为什么理论复杂度同样是O(n)的遍历数组通常比链表快好几倍的原因——复杂度分析只算操作步数而忽视了缓存局部性带来的实际加速。所以数据结构的课本理论在单元素操作上是对的但到了真实硬件环境下数组的连续内存特性会把细微的常数优势放大成数量级的性能差异。这一点日常开发时必须心里有数。5.2 add/remove的本质操作量分析ArrayList的add方法有两个重载add(E e)直接追加到末尾add(int index, E element)在指定位置插入。public void add(int index, E element) { rangeCheckForAdd(index); modCount; final int s; Object[] elementData; if ((s size) (elementData this.elementData).length) elementData grow(); System.arraycopy(elementData, index, elementData, index 1, s - index); elementData[index] element; size s 1; }这里关键代码是System.arraycopy(elementData, index, elementData, index 1, s - index)。如果目标位置是中间要把index之后的所有元素整体向右挪一格为插入滕出空位。这个操作在内存层面是一个O(n)的移动。如果插入的位置越靠前需要移动的元素越多性能越差。remove方法也是对称的逻辑。remove(int index)先取出旧值然后执行System.arraycopy把index后面的元素整体向左挪一格public E remove(int index) { Objects.checkIndex(index, size); modCount; E oldValue elementData(index); final int numMoved size - index - 1; if (numMoved 0) System.arraycopy(elementData, index1, elementData, index, numMoved); elementData[--size] null; return oldValue; }注意最后一行elementData[--size] null。这个操作叫置空以避免内存泄漏。如果不把最后一次位置置null数组中就还持有那个对象的引用即使size已经减少GC也不会回收这个对象。当列表长时间存活而元素被越删越多时这个细节会慢慢堆积成内存问题。同样地clear方法内部也不是把数组引用设为null而是遍历数组把所有槽位置为null然后size归零public void clear() { modCount; final Object[] es elementData; for (int to size, i size 0; i to; i) es[i] null; }这个做的也是帮助GC的活儿。Java里直接扔掉数组是省事但数组内部还保留着的引用会阻止GC回收。所以故意拿null去覆盖这些引用好让后面GC扫描时能安全识别。5.3 读取为什么快局部性与顺序遍历这一点上面已经涉及到——数组的局部性好顺序遍历的时候CPU缓存命中率极高。加上ArrayList带RandomAccess标记很多集合算法比如Collections.binarySearch知道它可以走索引避免了迭代器创建的开销。我们再放一个大致的性能对比场景往一个包含100万个元素的ArrayList和LinkedList中间位置分别插入一个元素猜猜差多少倍实际测过的数据是ArrayList大约耗时0.1毫秒到1毫秒之间取决于是不是在尾部插入LinkedList按索引插入中间位置需要先遍历到那个索引位置耗时可能在几十毫秒到上百毫秒。差距能到几十倍甚至上百倍。这是因为LinkedList虽然插入本身是O(1)但找到插入位置是O(n)整体还是O(n)而且链表本身节点分散在内存中遍历过程缓存命中率极低。一句话总结的话ArrayList适合读多写少且写入集中在尾部的场景LinkedList适合只在头部或尾部频繁操作的场景比如用LinkedList实现一个队列deque相关操作都是O(1)。6. 序列化、fail-fast与并发安全机制6.1 为什么elementData用transient修饰IO序列化如何工作前面提到ArrayList的elementData被transient修饰这看起来和Serializable矛盾。实际上ArrayList自己重写了writeObject和readObjectprivate void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { int expectedModCount modCount; s.defaultWriteObject(); s.writeInt(size); for (int i 0; i size; i) { s.writeObject(elementData[i]); } if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } }流程是先写非transient字段也就是modCount和size再写size最后逐个写入数组中有值的元素。注意写入过程中检查了modCount如果序列化期间集合被修改了会抛出ConcurrentModificationException。这保证了一个正在序列化的ArrayList不会被另一个线程同时修改从而避免数据不一致。readObject方法基于同样的思路根据写入的size按需构造数组读取元素private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { s.defaultReadObject(); int size s.readInt(); if (size 0) { Object[] elements new Object[size]; for (int i 0; i size; i) { elements[i] s.readObject(); } elementData elements; } else { elementData EMPTY_ELEMENTDATA; } }这种做法的实际收益在数据量大的时候非常明显。假设ArrayList的elementData是一个长度为100000的数组但size只有1000默认序列化会把整个数组都写出去——大量null值跟着走一趟网络或者落一次磁盘。定制序列化只写1000个真实元素存储和传输开销能省99%。这算是一个数组实际容量不等于有效数据量问题的标准解法。学Java序列化机制的时候ArrayList是一个很好的研究样本。6.2 modCount与fail-fast机制modCount这个字段在AbstractList里定义protected transient int modCount 0;它表示这个列表被结构性修改的次数。结构性修改指的是改变了列表size的操作——add、remove、clear等而单纯替换某位置的值set不算结构性修改不会改变列表长度modCount不变。这个字段的直接目的是支撑迭代器遍历时的fail-fast机制。看迭代器迭代时做什么public E next() { checkForComodification(); int i cursor; ... } final void checkForComodification() { if (modCount ! expectedModCount) throw new ConcurrentModificationException(); }迭代器在创建时保存expectedModCount modCount。如果迭代过程中有人直接调用list.add或list.remove改变了列表结构modCount就会变化和expectedModCount不一致迭代器就会立即抛异常退出而不是继续以一种不安全的状态迭代下去。这个宁可抛异常也不继续运行的设计哲学叫fail-fast快速失败。它的好处是不掩盖错误——如果代码里有并发修改的bug尽早暴露而不是产生难以排查的随机行为。注意一个容易误用的点如果你在for-each循环里直接list.remove(element)一定会抛ConcurrentModificationException。但如果你用Iterator的remove方法则完全合法因为Iterator.remove会同步更新expectedModCountpublic void remove() { ... ArrayList.this.remove(lastRet); expectedModCount modCount; ... }这条规则在工作中几乎每周都能碰到。很多新人在循环里删元素踩了这个坑然后一脸茫然地来问为什么报这个错。6.3 ArrayList为什么不是线程安全的如何补救所有非加锁方法都没有任何线程保护如果多个线程同时改同一个ArrayList轻则数据错乱比如size还没来得及加1另一个线程已经把数组写穿了重则数组越界。此外两个线程同时扩容会导致复制竞争互相覆盖数组引用甚至丢元素。实际业务里如果确实需要线程安全的数据结构优先考虑CopyOnWriteArrayList读多写极少场景下非常合适。它的更新操作是复制整个底层数组然后在新数组上改再原子地替换引用。读操作永远不需要加锁但写操作成本高。Collections.synchronizedList(new ArrayList())在方法级别加synchronized简单粗暴能保证安全但性能一般。我的建议是如果只是偶尔需要线程安全用Collections.synchronizedList做包装就够了如果写操作非常频繁且业务允许重复读弱一致性问题不大那CopyOnWriteArrayList更合适如果读多写少但需要立刻看到最新的写结果那就老实加锁或者用ConcurrentLinkedQueue之类的并发队列。7. 实战中的几个经典坑与选型建议7.1 删除元素时索引错乱问题这是一个屡见不鲜的经典问题。假如有一个ArrayList内容是[1, 2, 3, 4, 5]你想删掉所有值为2和4的元素按索引从前往后删for (int i 0; i list.size(); i) { if (list.get(i) 2 || list.get(i) 4) { list.remove(i); } }结果你会发现删不干净。原因是删除时后面的元素集体向前移动下一个要遍历的位置上的元素已经发生了移位但索引i还是继续往后加。第一次删掉2之后3的位置从2变成了14从3变成了2。第二次循环i2时本来该看3却被跳过变成了看4最后4被删了。但原本在4后面的5跑到前面来了——整个过程就错乱了。解法有几种从后往前删for (int i list.size() - 1; i 0; i--)用Iterator并调用iterator.remove()先收集要删的元素再调用removeAll用Stream做过滤然后收集到新List从性能和写法简洁性来看倒序删除是最直接的方案而且不会产生额外的临时集合。这个坑建议每一个Java开发者都亲身踩一遍踩完就长记性了。7.2 subList视图陷阱subList方法返回的不是一个新的ArrayList而是原列表的一个视图。两个list共享同一个底层数组对这个视图做的任何结构性修改都会反映到原列表中反过来对原列表做结构性修改会使视图失效。一个非常经典的异常场景是对subList返回的视图执行add或isEmpty等操作后再对原list执行size()等方法观察它的变化或者反过来对原list做增删然后对视图继续操作大概率会触发ConcurrentModificationException。这是因为SubList内部维护了自己的modCount当发现原List的modCount和它的期望值不一致时就会直接抛出异常。另外subList也是返回视图而非快照——修改子列表中的元素会直接影响原列表。这个设计本意是方便批量操作比如list.subList(0, 10).clear()可以快速删除前10个元素。但如果你误把subList当成独立的新列表来用出了bug会很隐蔽。所以我在工作里养成一个习惯凡是需要独立数据的地方都会把subList的结果复制出来比如new ArrayList(list.subList(...))一劳永逸。7.3 Arrays.asList的坑你踩过几个Arrays.asList返回的是Arrays类内部的私有静态类ArrayList不是java.util.ArrayList。它有以下限制返回的list长度固定不能add和remove否则UnsupportedOperationException。它和原数组共享存储修改返回list里的元素会同步改原数组。有人以为asList之后就可以自由增删了直接list.add(1)然后一脸问号。这个在简历上写熟悉Java集合的候选人里非常常见建议每个基础不牢的开发者好好记一下。如果确实想要一个可以自由增删的ArrayList一个很简单的办法是ListString list new ArrayList(Arrays.asList(a, b, c));不过Java 9里还有List.of(a, b, c)这是一个真正不可变的List连set都不行。各有各的用途做数据初始化时要清楚自己在用哪一种。7.4 大数据量下的初始化容量与性能优化前面从扩容机制推导出一个实用结论如果事先能预估数据规模务必在初始化时指定容量。我曾经对一个批量导入功能做过压测导入数据量约50万条。用无参构造的ArrayList逐条add总共触发了大约20次扩容累计复制数据量接近实际数据量的1.5倍总耗时不低。改成new ArrayList(500_000)后一次扩容都没有耗时反而是原来的几倍。这里强调一下是用了扩容优化后时间大幅缩减。虽然现代JIT对数组复制已经优化得不错但能避免的无意义计算还是尽量避免。实际生产里对容量预估的精度不用太苛刻。就算预估量偏差很大也没关系最坏情况下就是多触发几次扩容。与其精确预测不如预估一个稍微偏大的值给后续业务的增长留点余量。但也不要盲目初始化一个巨大的容量比如预估只有100条却new ArrayList(100_000)白白浪费内存。另外一个相关的小技巧如果确定列表数据只用读可以用List.of快速构建不可变列表既省去扩容又天然线程安全不可变对象无需额外同步。Java 9之后这个API的出现让很多原本需要Collections.unmodifiableList()包装的场景变得更轻量了。8. ArrayList与LinkedList的对比实测8.1 用一组JMH基准测试说话空谈概念没什么意思我实际用JMH框架跑过一组基准测试对比ArrayList和LinkedList在几个核心操作上的表现。以下是测试设计分别构建一个初始容量充分的大列表元素为Integer类型。测试随机访问按随机索引取元素连续取100万次。测试头部插入在索引0位置插入元素连续插入10000次。测试尾部追加直接add连续追加100万次。测试中间插入在列表最中间插入元素连续10000次。测试环境和结果大致如下数值是量级参考具体数字会因机器不同而浮动操作ArrayListLinkedList结论随机访问100万次5ms量级数十秒量级甚至更慢ArrayList快几个数量级头部插入10000次大量数组搬移链表头插O(1)LinkedList明显快尾部追加100万次均摊O(1)链表尾插O(1)接近ArrayList略快中间插入10000次O(n)搬移O(n)查找O(1)插入差距大ArrayList整体更优这个结果其实推翻了很多教科书上的直觉LinkedList的中间插入并不快因为找到插入位置也要遍历ArrayList的中间插入虽有数组搬移成本但System.arraycopy是极其高效的native内存拷贝实测下来在多数场景下仍比LinkedList快。所以我的经验是日常开发99%的场景用ArrayList就够了。LinkedList只有在明确把它当双端队列用频繁在头尾增删时才有优势。8.2 选型时该问自己的三个问题面对一个具体的业务场景选ArrayList还是LinkedList我通常问自己三个问题是否需要按索引频繁做随机访问是就ArrayList。操作是集中在头部/尾部的增删还是集中在中间中间的就老老实实用ArrayList。是否有队列/双端队列的需求如果是直接用ArrayDeque或LinkedList但这时用的是它的Deque接口而不是List接口。顺带提一句如果只是做个简单的Stack官方推荐也是用ArrayDeque而不是Stack类。Stack和Vector一样都是JDK 1.0的老古董了性能差设计也和Deque接口重叠。8.3 什么时候必须放弃ArrayList我在真实的中间件开发里遇到过一种必须放弃ArrayList的场景某服务需要维护一个LRU缓存淘汰队列每次新增元素都要放到队头队尾元素被淘汰。这个操作模式用LinkedList或者更具体地说Deque能轻松实现O(1)的头部插入和尾部删除而用ArrayList做头部插入每次都要把整个数组右移数据量大了以后性能瓶颈非常明显。另一个场景是并发读多写少的黑名单列表。每次读请求都要判一个元素在不在列表里但列表更新频率很低比如几分钟一次。这个用CopyOnWriteArrayList非常合适它底层就是ArrayList的拷贝写版本读操作走数组索引又快又线程安全。9. 关于ArrayList我最后想多说两句ArrayList是我见过的最友好的数据结构实现之一它有非常多值得琢磨的细节懒加载的空数组设计、1.5倍扩容系数、transient与定制序列化、fail-fast机制等等。这些设计初看都是小事但凑在一起构成了一个非常适合日常使用的高性能集合类。把ArrayList的源码读透之后再去理解HashMap、ConcurrentHashMap的底层设计会有一种很清晰的路标感。我个人在实际使用中体会最深的一点是数据结构选型这件事不要凭教科书上的复杂度结论做决定一定要结合真实硬件的特性和实际操作模式。数组的连续内存带来的缓存局部性在很多场景下让ArrayList的实际性能远超理论分析。学会先分析自己的场景是读多还是写多、是尾部增删还是中间增删、是单线程还是多线程再做出选择这才是真正吃透了顺序表这一课。源码这个东西谁看谁赚。碰到不了解的集合类别只查文档直接翻JDK的src.zip或者用IDE点进开源码看看很多解释不清的疑问就自然有答案了。