LinkedList 与 ArrayList 选型，是集合框架里一道容易被想当然带过的题。很多人在面经里背过“链表插入删除快、数组查询快”，可一旦被问“那为什么 JDK 里很少见到 LinkedList 当主列表用”，往往答不上来。这题真正的考点不在背定义，而在能不能结合读写特征讲清取舍。
先把结论放在前面：随机访问、读多写少的场景选 ArrayList；只在“频繁在两端增删、且几乎不按索引访问”时，LinkedList 才真正占优。LinkedList 的 get(i) 要从较近的一端折半遍历，随机访问是 O(n)，中间插入即便省了数组拷贝，定位本身也要遍历，实际收益常常为负。这题要答好，关键是把“快在哪、慢在哪”讲具体，落到具体的工程场景里。
机制拆解
讲清两者增删查的代价来源。ArrayList 的随机访问是 O(1) 下标直取；但在中间位置插入或删除，要把后半段整体后移或前移（System.arraycopy），是 O(n)。LinkedList 由双向节点串成，节点间通过前驱后继指针相连，addFirst/addLast/removeFirst/removeLast 是 O(1)；可一旦按索引 add(i, e)/get(i)，JDK 会从距离较近的一端（index < size/2 从头部、否则从尾部）逐个走到目标，定位就是 O(n)。所以“链表插入快”只成立在“已经握着目标节点”或“只在两端操作”的前提下，从索引插入并不快。
这些坑的正确绕法
最常见的坑是拿 LinkedList 当中间插入的银弹。以为换成链表就能避开数组拷贝，结果定位开销把省下的时间全吃回去，实测在中等规模列表上比 ArrayList 还慢。真正需要链表优势的场景，是队列、栈、或“已知节点引用后在其附近增删”。
其次是把 LinkedList 当栈用却调错方法。poll/offer 与 remove/add 在空表时行为不同，混用会破坏后进先出语义，或在空栈时抛异常而非返回空。需要栈语义优先用 ArrayDeque，它比 LinkedList 做栈更省内存、更快。
还有一个更隐蔽的坑：忽视了每个节点额外的指针开销。LinkedList 的每个节点除了存数据，还要存前驱、后继两个引用（在 64 位虚拟机、开启压缩指针下通常 24 字节左右），数据量很大时，光节点开销就比 ArrayList 的连续数组高出一截，且链表节点不连续，缓存命中率差，遍历比数组慢。
代码里见真章
看一段能直接跑的代码，把上面的机制落到具体写法上：
// LinkedList vs ArrayList 选型
List<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
al.get(5000); // O(1) 随机访问，下标直取
ll.get(5000); // O(n) 折半遍历：index<size/2 从头部走，否则从尾部
ll.addFirst(1); // O(1) 头插
ll.addLast(2); // O(1) 尾插
// 中间插入：ll.add(index, e) 仍需先遍历定位到目标节点，再改指针
// 每个 Node 额外携带前后指针，内存与缓存都不占优
这段代码值得盯三处：第一处，ArrayList 的随机访问是 O(1)，这是它碾压链表的根本；第二处，LinkedList 的 get 要折半遍历，规模一大就退化；第三处，节点指针开销让链表在大体量下既不省内存也不快。面试讲到这一层，基本就稳了。
这题在面试里怎么问、怎么答
“请简单介绍一下 LinkedList 与 ArrayList 选型，它在 Android 开发中起什么作用？”一句话定位：读多写少、要随机访问选 ArrayList；频繁两端增删且少按索引访问才选 LinkedList。在 Android 里，RecyclerView 的数据源几乎都用 ArrayList（要频繁按位置取 item）；消息队列、历史栈、撤销栈这类只在头尾操作的，才考虑 LinkedList 或 ArrayDeque。如果要把选型沉淀成团队规范，建议加一条：默认 ArrayList，除非能讲清“只两端操作”的硬理由。
“LinkedList 与 ArrayList 选型的底层原理是什么？能不能详细说一下？”从数据结构讲：ArrayList 是连续数组，下标直取 O(1)，中间增删靠 arraycopy 迁移 O(n)；LinkedList 是双向链表，两端 O(1)，按索引访问要折半遍历 O(n)。再补一点：链表节点的非连续布局导致缓存不友好，大列表遍历比数组慢。机制别空讲，配核心代码最稳。
“在使用时遇到过什么问题？”讲真实案例：某功能用 LinkedList 存用户列表并按索引循环访问做高亮，列表到几千条时滑动明显卡顿；profiler 显示大量 Node 遍历。改成 ArrayList 后，按位置访问回到 O(1)，卡顿消失。量化效果最加分。
“和相关的替代方案相比，有什么优劣？”与 ArrayDeque 比，做栈或队列 ArrayDeque 内存更紧凑、速度更快，LinkedList 在这两个角色上已被取代；与 ArrayList 比，LinkedList 仅两端增删占优。选型时要把“中间插入仍需遍历定位”与“节点指针开销”这类代价摆到台面上，再决定是否引入。
再补一个工程上常被忽略的点：迭代与删除的代价差异。ArrayList 迭代中删除中间元素，会触发后续元素整体前移，循环删除多个时是 O(n²)；LinkedList 迭代删除是 O(1) 改指针，但前提是走迭代器的 remove，若用下标 for 循环边遍历边 remove，LinkedList 的每次 remove(index) 都要重新定位，同样退化成 O(n²)。另一个区别是内存与 GC：ArrayList 扩容产生的是整块连续大数组，LinkedList 产生的是大量零散小节点，后者在大体量下更易造成堆碎片与更频繁的年轻代回收。理解了这些，选型就不再是“背结论”，而是对着真实读写特征做权衡。
还有两个常被追问的细节。其一是 Collections.binarySearch 与 List.sort 的前提：二分查找依赖随机访问，链表上用它等于白做，JDK 文档里也直接注明链表应先转成数组。其二是 fail-fast 与选型的关系：ArrayList 的 modCount 校验带来一点遍历开销，但可忽略；真正影响选型的是 GC 与缓存局部性，大列表连续遍历时数组的预取效果明显好于链表。面试里若被追问“什么时候链表确实更优”，可以给两个硬场景：一是队列式的交替出入，二是手上已持有节点引用时在 O(1) 位置插入或删除。除此之外，链表的“插入优势”多半只是传说。
补一个容易被问到的追问：为什么 List 接口不直接提供 addFirst？答案是接口只暴露所有实现都能兑现的最小公共语义，addFirst 属于顺序语义，LinkedList 之外的实现未必支持，所以它留在具体类上。顺着这条线还能讲 ListIterator 与双向遍历——listIterator(int) 支持从指定位置前后走，链表的实现代价依然是 O(n)，而 ArrayList 借助 System.arraycopy 做批量移动，成本集中在被跨越的那一段上，所以"移动 k 个位置"的开销两者接近，真正拉开差距的是"定位"这一步。把定位与移动拆开算，链表的劣势就说得清楚了。
给正在准备面试的你
把 LinkedList 与 ArrayList 选型画成一张对比表：随机访问、两端增删、中间增删、内存布局四行，分别填 O(1)/O(n) 与连续/零散。面试中关于选型的问题，关键在于能够从原理、应用、踩坑三个层面给出有深度的回答。
再补工程案例与踩坑——应用落点是把一个误用 LinkedList 做按索引遍历高亮的逻辑改成 ArrayList，对比前后帧率与 GC 次数。
复习时别孤立刷题：HashMap 底层原理——相邻考点常被一起问，边界提前划清楚。
划两句重点：随机读多、要按下标取元素，ArrayList 的 O(1) 是根本优势；LinkedList 的优势只在两端增删，中间插入仍要遍历定位，节点开销还不占优。
下一篇聊 HashMap 底层原理：数组、链表与红黑树的演进——沿着今天这条主线继续往前走。
如果这篇文章对你有帮助，欢迎点赞、在看、转发三连。你的支持就是这个系列持续更新的动力。
「Android软件开发面试·从入门到精通」连载系列
上一篇：ArrayList-源码与扩容机制：1.5-倍增长的细节
下一篇预告：HashMap-底层原理：数组、链表与红黑树的演进
有任何问题欢迎在评论区留言交流。
