「Java 进阶之路」系列 Day21写在前面模块二收尾了从这篇开始进入模块三——集合框架。ArrayList和LinkedList是最常被拿来对比的一对很多人张口就是数组适合查、链表适合改但一问到LinkedList插入一定比ArrayList快吗就容易想岔。这篇从底层结构讲起把这个常见误解纠正过来。一、是什么两种完全不同的底层结构LinkedList底层头节点节点节点尾节点ArrayList底层一段连续的Object数组 下标0 下标1 下标2 下标3ArrayList内部是一段连续的数组Object[] elementData每个元素紧挨着存放靠下标直接定位LinkedList是一条双向链表每个节点各自存着数据、以及指向前一个/后一个节点的引用元素在内存里是分散的靠一个个跳指针才能找到目标节点。二、为什么会有性能差异结构决定了访问方式数组因为是连续内存知道下标就能直接算出内存地址一步到位链表没有这种按下标计算地址的能力想找到第 N 个节点只能从头或从尾LinkedList会根据下标离哪端近选择方向一个个往后跳跳 N 次才能到。这个结构性差异决定了两者操作的时间复杂度全面不同操作ArrayListLinkedList按下标随机访问 get(index)O(1) 直接计算地址O(n) 要从头或尾跳指针过去在头部插入删除O(n) 后面所有元素要整体后移O(1) 只改头节点的指针在尾部插入删除O(1) 通常直接追加除非要扩容O(1) 只改尾节点的指针在中间插入删除O(n) 定位是O(1)但要移动后续元素O(n) 移动指针是O(1)但定位到这个位置要遍历内存占用较低只存数据本身较高每个节点还要多存两个指针引用表格里最容易被忽略的一行是中间插入删除——很多人只记住链表插入删除是O(1)却忘了这个O(1)指的是改指针这一步本身但在中间位置插入删除之前你必须先找到这个位置而链表定位到中间某个下标同样得老老实实一个个跳过去是O(n)。所以严格来说在一个已知下标的中间位置插入删除ArrayList和LinkedList的总耗时都是O(n)只是O(n)里具体在忙活的事情不一样——一个在搬元素一个在跳指针。真正能让LinkedList发挥O(1)优势的场景是已经拿着一个指向目标位置的Iterator直接在当前位置insert/remove不需要重新从头定位——这也是为什么LinkedList实现的ListIterator支持add/remove操作是它相比ArrayList真正的优势场景而不是随便传一个下标进去插入就一定快。三、怎么用ArrayList 的扩容机制ArrayList默认初始容量是 10当元素个数超过当前数组容量时会触发扩容源码里的核心逻辑是// 简化后的ArrayList扩容逻辑privateObject[]grow(){intoldCapacityelementData.length;intnewCapacityoldCapacity(oldCapacity1);// 新容量约等于旧容量的1.5倍elementDataArrays.copyOf(elementData,newCapacity);// 拷贝到一个新数组returnelementData;}扩容的代价是一次完整的数组拷贝容量从10到15、从15到22每次扩容都要把旧数组的内容整个复制到新数组里这也是O(n)的操作。如果能提前预估数据量用带初始容量的构造方法new ArrayList(1000)能省掉扩容过程中反复拷贝的开销。LinkedList完全没有这个问题——它不需要连续内存来一个元素就new一个节点挂上去没有容量不够、整体搬家这种烦恼但代价是每个节点都要额外存两个引用prev、next元素少的时候这个开销占比不明显元素一多内存占用会明显高于ArrayList。四、实际选型LinkedList 用得比想象中少现代 Java 开发里LinkedList实际使用频率远低于很多人的想象。原因是绝大多数业务场景是遍历读取或者尾部追加这两种操作ArrayList都是强项需要频繁在两端进出当队列/栈用的场景ArrayList家族里的ArrayDeque通常性能更好——ArrayDeque底层是循环数组没有LinkedList每个节点额外存指针的内存开销Java 官方文档也建议优先用ArrayDeque而不是LinkedList来实现栈或队列LinkedList真正的用武之地是那种拿着迭代器边遍历边在当前位置插入删除的场景这在实际业务代码里并不常见五、面试追问Q1ArrayList 和 LinkedList 的核心区别是什么底层数据结构不同ArrayList是连续的动态数组靠下标直接计算地址访问LinkedList是双向链表靠节点间的指针一个个跳转访问。这个结构差异决定了两者在随机访问、插入删除等操作上的时间复杂度完全不同。Q2在集合中间位置插入一个元素LinkedList 真的比 ArrayList 快吗不一定。如果只是传入一个下标去插入LinkedList定位到这个下标同样需要从头或尾遍历是O(n)插入本身改指针才是O(1)两者加起来还是O(n)和ArrayList需要搬移后续元素的O(n)本质上是一个量级只是具体耗时在做的事情不同。LinkedList真正的O(1)优势只体现在已经持有指向目标位置的Iterator、直接在当前位置操作时。Q3ArrayList 的扩容机制是怎样的默认初始容量是10元素个数超过当前数组长度时触发扩容新容量大约是旧容量的1.5倍oldCapacity oldCapacity 1然后把旧数组的全部元素拷贝到新数组里。这个拷贝过程是O(n)的开销如果能预估数据规模用带初始容量的构造方法能减少扩容次数。Q4为什么说 LinkedList 在实际项目中用得比想象中少因为大部分业务场景是遍历读取或者尾部追加这些操作ArrayList效率更高即使是需要频繁两端进出的队列/栈场景ArrayDeque通常比LinkedList性能更好、内存占用更低LinkedList每个节点要多存两个指针引用。LinkedList真正适合的场景——边遍历边在当前位置插入删除——在实际业务代码里并不多见。Q5LinkedList 比 ArrayList 多占用的内存开销体现在哪LinkedList的每个节点除了存储数据本身还要额外存两个引用字段分别指向前一个和后一个节点而ArrayList的数组里每个位置只存数据本身没有这类额外的指针开销。数据量越大LinkedList这部分额外的内存占用就越明显。下一篇预告Day22 讲HashMap的底层原理——数组加链表加红黑树的混合结构扩容机制是怎么运作的这是集合框架里面试问法最深的一个。