arraylist 查询性能远优于 linkedlist：前者基于连续数组，支持 o(1) 索引访问且缓存友好；后者需遍历链表，平均 o(n)，节点分散导致缓存失效。
ArrayList 和 LinkedList 虽然都实现 List 接口，但底层结构完全不同，直接决定了它们在增、删、改、查操作上的性能差异。
底层数据结构：数组 vs 双向链表
ArrayList 底层是动态扩容的 Object[] 数组，元素在内存中连续存储，支持通过索引直接定位。它内部维护 elementData 数组和 size 计数器，默认初始容量为 10，扩容时一般变为原容量的 1.5 倍。
LinkedList 底层是双向链表，每个节点（Node）包含三部分：数据项 item、前驱引用 prev、后继引用 next。头节点 first 和尾节点 last 保证 O(1) 的首尾操作，但所有节点在堆内存中分散存储，没有连续地址关系。
查询（get / set）性能：ArrayList 明显占优
ArrayList 支持随机访问，get(i) 直接计算内存偏移量，时间复杂度为 O(1)；CPU 缓存友好，局部性原理生效。
LinkedList 的 get(i) 必须从 first 或 last 出发遍历，平均需走 n/2 步，时间复杂度为 O(n)；且节点分散，无法利用 CPU 缓存预取。
- 实测 10 万元素下：ArrayList 查询耗时通常
- LinkedList 不实现
RandomAccess接口，JDK 会据此优化遍历策略（如避免用普通 for 循环遍历）
插入与删除性能：位置决定优劣
尾部操作（add / remove last）两者都高效：
- ArrayList 尾插均摊 O(1)，仅扩容时触发 O(n) 数组复制
- LinkedList 尾插始终 O(1)，只需修改
last指针
头部操作（addFirst / removeFirst）LinkedList 占绝对优势：
- ArrayList 头插需整体右移所有元素，O(n)
- LinkedList 头插仅新建节点并调整
first和原首节点的prev，O(1)
中间位置插入/删除（add(index) / remove(index)）两者都是 O(n)：
- ArrayList 需移动后续元素
- LinkedList 需先遍历到目标位置（O(n)），再修改指针（O(1)）
内存占用与适用场景
ArrayList 内存更紧凑：只存数据，无额外指针开销；适合大数据量、频繁读取、尾部操作为主的场景（如日志缓存、分页列表）。
LinkedList 每个元素多占 16 字节（64 位 JVM 下两个对象引用），空间放大明显；适合小数据量、高频首尾增删、需模拟栈/队列/双端队列的场景（如任务调度缓冲区）。
实际开发中，90% 以上列表场景首选 ArrayList —— 因为随机访问更常见，而首部插入在业务逻辑中极少出现，且其内存与缓存优势在现代硬件上收益显著。
