ArrayList 与 LinkedList 区别
- 因为 Array 是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的。Array 获取数据的时间复杂度是
O(1),但是要删除数据却是开销很大的，因为这需要重排数组中的所有数据。 - 相对于 ArrayList，LinkedList 插入是更快的。因为 LinkedList 不像 ArrayList 一样，不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组，这是 ArrayList 最坏的一种情况，时间复杂度是
O(n)，而 LinkedList 中插入或删除的时间复杂度仅为O(1)。ArrayList 在插入数据时还需要更新索引（除了插入数组的尾部）。 - 类似于插入数据，删除数据时，LinkedList 也优于 ArrayList。
- LinkedList 需要更多的内存，因为 ArrayList 的每个索引的位置是实际的数据，而 LinkedList 中的每个节点中存储的是实际的数据和前后节点的位置。
- 你的应用不会随机访问数据。因为如果你需要 LinkedList 中的第 n 个元素的时候，你需要从第一个元素顺序数到第 n 个数据，然后读取数据。
- 你的应用更多的插入和删除元素，更少的读取数据。因为插入和删除元素不涉及重排数据，所以它要比 ArrayList 要快。
以上是教科书结论，但其中”LinkedList 插入删除 O(1)”这句话在真实使用中最容易被误用——它有一个隐藏前提。本文把复杂度前提、内存布局、缓存友好性三层补全，给出可直接执行的选型规则。
复杂度表（带前提）
| 操作 | ArrayList | LinkedList |
|---|---|---|
| get(i) 随机访问 | O(1) | O(n) |
| 尾部 add | 摊销 O(1) | O(1) |
| 头部/中部 add | O(n)（搬运） | O(1)，前提是已持有该位置的迭代器/节点引用 |
| 按值查找后删除 | O(n) | O(n) 查找 + O(1) 删除 |
| 迭代器遍历中删除 | O(n) 搬运 | O(1) |
关键澄清：list.add(0, x)、list.remove(i) 这类按索引操作，LinkedList 要先 O(n) 走到第 i 个节点，总体仍是 O(n)，并不比 ArrayList 快多少；只有”迭代过程中就地增删”（迭代器已停在节点上）才是 LinkedList 真正的 O(1) 场景。面试与设计中把”LinkedList 增删快”无条件化，是最常见的误用来源。
内存与缓存：被忽略的决定性因素
- ArrayList 是一块连续内存：对象引用紧凑排列，CPU 缓存行一次加载多个引用，遍历命中率极高
- LinkedList 每个节点独立分配：节点对象头 + 数据引用 + prev/next 两个引用，内存开销约为 ArrayList 的 3-4 倍，且节点散落堆中，遍历时缓存缺失频繁
实测中即使”中部插入”场景，ArrayList 的 O(n) 内存搬运（memcpy 级速度）也常常跑赢 LinkedList 的 O(n) 寻址 + 指针操作 + 缓存缺失。算法复杂度相同量级时，内存布局决定常数项，这是教科书表格不写的部分。
扩容行为
ArrayList 默认初始容量 10，扩容为 1.5 倍并数组拷贝；已知大小时 new ArrayList<>(expectedSize) 可避免多次扩容。LinkedList 无扩容概念，但每个元素都有节点分配成本（高并发下还加剧 GC 压力）。
选型规则（可直接执行）
- 默认 ArrayList：随机访问、遍历、尾部追加占绝大多数业务场景
- 频繁头部插入删除且规模大 → 优先考虑
ArrayDeque（循环数组，两头 O(1)，缓存友好），而不是 LinkedList - 迭代过程中大量就地增删 → LinkedList 或改用”标记-压缩”写法遍历 ArrayList
- 需要队列语义 → ArrayDeque/LinkedBlockingQueue；需要双向遍历 → ListIterator（两者都支持，但 ArrayList 遍历更快）
- 内存敏感的大集合 → ArrayList（节点开销差异在百万级元素时是 GB 级差距）
一个反直觉的基准结论
JMH 基准中常见结果：顺序遍历、按索引读、甚至中等规模的中部插入，ArrayList 全面领先；LinkedList 仅在”超大列表 + 迭代器就地增删”或”持续头部插入”时胜出。所以现代 Java 实践中 LinkedList 的出现频率越来越低——它不是错误答案，而是适用面比印象中窄得多的特化结构。
结论不变但更精确：ArrayList 赢在连续内存与随机访问，LinkedList 赢在持节点引用时的就地增删；选型时先问”我的增删是否持有迭代器位置”，再问”规模与内存是否敏感”，答案自然清晰。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 非鱼小站！
相关推荐
2022-05-07
ConcurrentHashMap 的工作原理及代码实现
ConcurrentHashMap 采用了非常精妙的”分段锁”策略，ConcurrentHashMap 的主干是个 Segment 数组。Segment 继承了 ReentrantLock，所以它就是一种可重入锁（ReentrantLock)。在 ConcurrentHashMap，一个 Segment 就是一个子哈希表，Segment 里维护了一个 HashEntry 数组，并发环境下，对于不同 Segment 的数据进行操作是不用考虑锁竞争的。 这段描述对应的是 JDK7 的实现。JDK8 已经彻底重写了这套机制——抛弃 Segment，改为 CAS + synchronized 锁桶头节点，锁粒度从”段”细化到”单个桶”。两个版本都值得理解：7 看思想，8 看工程。 JDK7：Segment 分段锁 结构：Segment[]，每个 Segment 内含一个 HashEntry[] 并继承 ReentrantLock 并发度：默认 16 个 Segment，最多 16 个写线程互不阻塞 局限：锁粒度固定为段，段内冲突依然串行；size() 需要重试或加锁统计 分段锁的意义在...
2022-05-06
HashMap 的工作原理及代码实现
HashMap 基于 hashing 原理，我们通过 put() 和 get() 方法储存和获取对象。当我们将键值对传递给 put() 方法时，它调用键对象的 hashCode() 方法来计算 hashcode，让后找到 bucket 位置来储存值对象。当获取对象时，通过键对象的 equals() 方法找到正确的键值对，然后返回值对象。HashMap 使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap 在每个链表节点中储存键值对对象。 以上是哈希表的通用原理，但 JDK8 的 HashMap 远不止”数组+链表”这么简单。下面按结构、put 流程、扩容、线程安全四个层面拆透。 结构：数组 + 链表 + 红黑树JDK8 中 HashMap 的桶（bucket）里挂的节点有两种形态： 链表：冲突少时的默认形态，查找 O(n) 红黑树：当链表长度 ≥ 8 且数组长度 ≥ 64 时树化，查找退化为 O(logN) 树化阈值 8 不是拍脑袋：泊松分布下链表长度达到 8 的概率约千万分之六，所以树化是”极端冲突的保险”，正常情况几乎不触发；而数组不足...
2022-05-04
HashMap 和 HashTable 的区别
HashMap 几乎可以等价于 HashTable，除了 HashMap 是非 synchronized 的，并可以接受 null(HashMap 可以接受为 null 的键值 (key) 和值 (value)，而 HashTable 则不行)。 HashMap 是非 synchronized，而 HashTable 是 synchronized，这意味着 HashTable 是线程安全的，多个线程可以共享一个 HashTable；而如果没有正确的同步的话，多个线程是不能共享 HashMap 的。Java 5 提供了 ConcurrentHashMap，它是 HashTable 的替代，比 HashTable 的扩展性更好。 另一个区别是 HashMap 的迭代器 (Iterator) 是 fail-fast 迭代器，而 HashTable 的 enumerator 迭代器不是 fail-fast 的。所以当有其它线程改变了 HashMap 的结构（增加或者移除元素），将会抛出 ConcurrentModificationException，但迭代器本身的 remove()...
2022-04-28
List 和 Set 区别
List, Set 都是继承自 Collection 接口 List 特点：元素有放入顺序，元素可重复。Set 特点：元素无放入顺序，元素不可重复（注意：元素虽然无放入顺序，但是元素在 set 中的位置是有该元素的 HashCode 决定的，其位置其实是固定的） List 接口有三个实现类：LinkedList，ArrayList，Vector。Set 接口有两个实现类：HashSet(底层由 HashMap 实现)，LinkedHashSet 三条特点之外，真正决定选型的是底层数据结构带来的复杂度差异，以及”去重/判含”这类操作在两种集合里的成本天壤之别。本文按语义、实现、复杂度、选型四层展开。 语义差异：有序可重 vs 唯一性 List：序列语义。保留插入顺序、允许重复、支持按索引访问（get(i)）——对应”一批有先后关系的记录” Set：集合语义。元素唯一、不承诺顺序（HashSet）、无索引访问——对应”一个成员资格集合” “Set 无序但位置固定”那句注记的准确解释：HashSet 的迭代顺序由元素 hashCode 与桶分布决定，对同一组元素是...
2022-05-02
ArrayList 与 Vector 区别
同步性：Vector 是线程安全的，也就是说是同步的 ，而 ArrayList 是线程不安全的，不是同步的。 数据增长：当需要增长时，Vector 默认增长为原来一倍 ，而 ArrayList 却是原来的 50% ，这样 ArrayList 就有利于节约内存空间。 说明：如果涉及到堆栈，队列等操作，应该考虑用 Vector，如果需要快速随机访问元素，应该使用 ArrayList 两条区别都对，但都停留在 JDK1.0 时代的认知。今天再谈 Vector，重点应是：为什么它被弃用、”线程安全”为什么名不副实、以及并发 List 的正确选型。 表面区别补全 维度 ArrayList Vector 同步 非同步 方法级 synchronized 扩容 1.5 倍 默认 2 倍（可配 capacityIncrement） 迭代器 Iterator fail-fast Iterator fail-fast + Enumeration（非 fail-fast） 出身 JDK1.2 集合框架 JDK1.0 遗留类 现状 默认选择 遗留兼容，新代码禁用 扩容差异...
2022-05-03
HashSet 和 HashMap 区别
HashMap HashSet HashMap 实现了 Map 接口 HashSet 实现了 Set 接口 HashMap 储存键值对 HashSet 仅仅存储对象 使用 put() 方法将元素放入 map 中 使用 add() 方法将元素放入 set 中 HashMap 中使用键对象来计算 hashcode 值 HashSet 使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以 equals() 方法用来判断对象的相等性，如果两个对象不同的话，那么返回 false HashMap 比较快，因为是使用唯一的键来获取对象 HashSet 较 HashMap 来说比较慢 表格列出了 API 层区别，但最有价值的事实藏在源码里：HashSet 就是 HashMap 包了一层。理解这层包装关系，两者的一切异同都能推导出来。 源码关系：HashSet 是 HashMap 的适配器JDK 中 HashSet 的内部实现极其简单： private transient HashMap<E, Object> ma...
评论
WalineDisqus
