List 实现到底怎么选，我花了一周才搞明白

学完集合框架基础之后我接下来面对的问题是同样是 ListArrayList 和 LinkedList 到底该用哪个网上搜一圈说法五花八门有的说 LinkedList 插入快有的说 ArrayList 才是王道。我写代码试了几次发现完全不是我想的那样。这篇把我折腾了一周才理清楚的几个 List 实现类写下来。如果能帮到另一个刚学的同学那就值了。常见的 List先过一遍Java 里能当 List 用的类还挺多的。但平时最常碰到的大概就这几个。ArrayList — 用得最多的那个ArrayList 底子是数组。就是一个会自动长大的数组。你想往里面塞东西它自己会扩容不用你操心。它最大的优点是随机访问特别快。想取第 5 个元素直接list.get(5)瞬间返回。因为底层是数组数组按索引取元素是一次内存地址计算的事时间复杂度 O(1)。缺点是在中间插东西或者删东西代价比较大。你想想一个数组里每个元素都挨着放你在第 3 个位置插了个新的后面的所有元素都得往后挪一位。要是数据量大这个挪就很肉疼。还有一个容易忽略的点ArrayList 尾部插入效率很高除非触发了扩容。扩容这个事情后面细说它是一次数组复制有大开销。LinkedList — 听起来快但不一定LinkedList 底子是双向链表。每个节点不光存自己的数据还存了前一个和后一个节点的引用。我之前一直以为 LinkedList 插得快因为链表嘛改改指针就行了。但学深了才发现这句话有条件。链表插入确实是 O(1)但前提是你已经站在那个位置了。但问题是你怎么站到那个位置上去如果你说的是在第三个位置插一个新元素你得先从头遍历到第三个位置这个遍历是 O(n)。遍历完了再插O(1)。加起来还是 O(n)。换句话说如果你已经持有要插入位置的节点引用那 LinkedList 的插入确实快。但如果你只是按索引插它跟 ArrayList 比没有优势甚至更慢。ArrayList 挪元素虽然慢但数组的批量搬移操作在 CPU 层面是有优化的。LinkedList 真正擅长的是在头部或尾部的插入和删除只要改改 first 和 last 指针就行不需要遍历。所以 LinkedList 经常被用来实现队列先进先出或者双端队列。另外它的随机访问是 O(n)取中间某个元素得从头一个一个往后找。这一点跟 ArrayList 比差远了。所以如果你要频繁随机按索引取值别用 LinkedList。Vector — 老一辈的线程安全方案Vector 是 JDK 1.0 就有的老前辈。它跟 ArrayList 一样是动态数组但它的方法基本都是 synchronized 的换句话说它是线程安全的。但你基本不会在新代码里看到 Vector。因为它的同步策略太粗暴了就是每个方法加一把锁性能不好。而且有时候你想要的不是每个方法都同步而是一组操作的原子性Vector 给不了这个。现在的做法通常是单线程用 ArrayList多线程用后面会说的 CopyOnWriteArrayList或者用 Collections.synchronizedList 包装一层。Vector 基本上是个历史产物了。Stack — 继承自 Vector 的栈Stack 继承自 Vector所以也是线程安全的。它是个栈后进先出LIFO。用法很简单StackStringstacknewStack();stack.push(a);stack.push(b);Stringtopstack.pop();// bStringpeekstack.peek();// a不移除不过官方文档自己都推荐用 ArrayDeque 来当栈用了。Stack 是基于 Vector 的继承了它所有的同步开销而且 Stack 是类不是接口设计上不够灵活。CopyOnWriteArrayList — 读多写少的场景用它这个类的名字很直白写的时候复制一份。它背后的想法是这样的底层是一个 volatile 修饰的数组。你读的时候直接读这个数组不加锁性能很好。但你要写的时候add、set 这些它会先加锁ReentrantLock然后把整个数组复制一份在复制的新数组上做修改最后把新数组的引用赋给底层数组。这就意味着写操作发生的时候正在读的线程读的还是老数组不会被影响。读写互不干扰。但它有一个很明显的代价每次写都复制整个数组。如果你的代码里写操作很频繁那性能就会很难看。所以它只适合读多写少的场景比如缓存、配置信息这种读取的人很多更新的人很少。理解了这五种 List 实现就可以往下看它们的区别了。大多数时候你只需要记住两个ArrayList 和 LinkedList然后搞清楚怎么选就够了。ArrayList 和 LinkedList到底怎么选这个问题我当时纠结了很久因为网上的说法看多了反而迷糊。后来我自己列了一个对比表一条一条理清楚了。底层结构不同ArrayList 是动态数组LinkedList 是双向链表。这个是最根本的区别其他所有差异都是从这个结构差异推导出来的。插入和删除——不是你想的那样错误印象LinkedList 插入删除比 ArrayList 快。实际情况ArrayList 在尾部插入很快除非扩容在中间插入需要挪元素LinkedList 在头尾插入很快O(1)在中间插入需要先遍历到那个位置O(n)然后才是指针调整O(1)。所以如果你要在中间频繁插入和删除其实两个都不快。但如果是在尾部追加ArrayList 通常比 LinkedList 快因为 ArrayList 操作的是连续内存CPU 缓存友好LinkedList 每个节点分散在内存各处缓存不友好。随机访问差距明显ArrayListO(1)直接用下标算地址。LinkedListO(n)得一个一个往后找。这个差距在实际使用中非常明显。我写了一个简单测试一个包含 10 万个元素的 List用 get 方法随机访问 1000 次ArrayList 基本是瞬间完成LinkedList 慢了好几个数量级。空间占用各有侧重ArrayList 会预留一些容量空间避免频繁扩容但这个预留是连续的内存空间对现代操作系统来说开销不大。LinkedList 每个节点除了存数据还要存前驱和后继两个指针。在 64 位 JVM 上一个对象的额外开销大概 16-24 字节。如果你存 100 万个元素LinkedList 比 ArrayList 多占几十 MB 的内存是很正常的事。应用场景我自己的使用原则是这样的大部分时候用 ArrayList。真的大部分时候。做列表展示、批量处理、数据暂存ArrayList 都够用而且性能不差。需要频繁在头部插入/删除或者要当队列/双端队列用的时候才考虑 LinkedList。Java 官方好像也更推荐用 ArrayDeque 替代 LinkedList 作为队列实现。LinkedList 在很少的改、大量的头尾操作下有优势这种场景其实不多。ArrayList 和 Vector已经不用选了上面提到了 Vector。它跟 ArrayList 的主要区别就两点第一线程安全。Vector 每个公开方法都加上了 synchronizedArrayList 没有。但就像前面说的这种每个方法都加锁的做法比较粗糙。第二扩容机制不同。ArrayList 默认扩容到 1.5 倍。Vector 默认翻倍而且可以指定一个 capacityIncrement 参数来控制每次扩多少。除此之外它俩的底层数组实现基本是一样的。在日常的单线程代码里没有人会用 Vector 替代 ArrayList。面试可能会问到理解到这个程度就可以了。ArrayList 扩容到底是怎么发生的上面提到了好几次扩容,这块展开说一下。什么时候扩容就是当你调用 add 方法发现当前数组已经满的时候。很有意思的是ArrayList 刚创建的时候如果你用的是无参构造器它内部实际上是一个空数组。只有当你往里面加第一个元素的时候它才会初始化成一个长度为 10 的数组。这种懒加载的设计可以节省内存有些 ArrayList 创建出来可能根本没数据。扩多少新容量是旧容量的1.5 倍。intnewCapacityoldCapacity(oldCapacity1);这里 1就是除 2。所以 10 扩容到 1515 扩到 22Java 里整数除法是向下取整的以此类推。Vector 是翻倍。为什么 ArrayList 选择 1.5 倍而不是翻倍一种说法是1.5 倍更节省内存因为翻倍可能导致大量空间闲置1.5 倍在扩容次数和空间浪费之间取了一个平衡。而且 Java 里用移位操作 1计算 1.5 倍非常快。扩容做了什么三步创建一个新数组长度是原来的 1.5 倍用System.arraycopy底层是 native 方法用 C/C 写的把老数组的元素全部复制过去让内部引用指向新数组这个过程不算快尤其是数据量大的时候。复制 10 万个元素到新数组是要花时间的。所以我后来养成一个习惯如果预先知道要存多少数据就指定容量。ListStringlistnewArrayList(10000);这样能省掉多次扩容的复制开销。如果不知道准确数量也可以估计一个大概范围比默认从 10 开始扩容要好。CopyOnWriteArrayList 的原理值得多说几句这个类我刚看到名字的时候觉得太长了CopyOnWriteArrayList 七个词拼一起。但看懂了之后觉得名字起得真好把核心思路直接写在脸上了。volatile 数组底层是一个被 volatile 修饰的数组。volatile 保证了一件事情一个线程修改了这个引用其他线程立刻能看到。这是 Java 内存模型里的 happen-before 规则。写的时候加锁复制当你要 add 一个元素的时候它做的事情是获取 ReentrantLock保证同时只有一个线程在写复制当前数组长度 1把新元素放到最后一个位置用新数组替换掉老数组这个过程我之前读源码的时候觉得很暴力明明只是加一个元素却复制了整个数组。但回头想想这个暴力背后换来的好处是巨大的读操作完全不加锁。读操作不加锁因为数组引用是 volatile 的写得时候替换引用这个操作对其他线程是立即可见的。而读操作只是读取这个 volatile 数组的老引用或者新引用不管读取哪个数据都是一致的。读的人不需要等写的人写的人也不影响读的人。适合什么场景“读多写少”这四个字就是它的适用范围。比如说一个配置列表服务启动的时候加载进去之后基本只读不改。或者一个缓存的白名单偶尔更新一下但每时每刻都有大量线程在读。如果反过来写多读少就千万别用它每次写入都复制整个数组数据量一上去性能就崩了。最后学这几种 List 实现的时候我最大的感受是没有一个全能的实现每个选择背后都是取舍。ArrayList 放弃了线程安全和中间插入的效率换来了最快的随机访问。LinkedList 放弃了随机访问的速度换来了头尾操作的灵活。CopyOnWriteArrayList 放弃了写入的性能换来了无锁读取的线程安全。你在用的时候其实是在做一个权衡我的场景更在乎什么把这个想清楚选哪个实现就是水到渠成的事。下一篇接着写 List 的具体操作遍历的时候改元素会怎样、删元素有哪些坑、多线程环境下到底怎么保证安全。这些都是我自己写代码时踩过的坑到时候一个一个说清楚。