实现原理
ArrayList 的实现原理
ArrayList 基本采用“动态数组”的底层结构，核心是一个可变大小的 Object[] elementData，用于承载所有元素，其中 size 记录当前实际元素个数。随着元素增加，内部会进行 动态扩容，以保持连续的内存块和快速访问。访问速度快、随机访问成本低，是这类结构作为包装集合的主力。
扩容策略决定了长期性能，常见实现会按比较保守的倍数放大，例如 1.5 倍甚至 1.6 倍，目标是在减少重分配次数的同时避免过多的空闲内存。此过程通常通过 Arrays.copyOf 将原始数组复制到一个更大的数组来完成。
当在中间位置插入或删除元素时，需要把后续元素向前或向后移动，产生 O(n) 的时间复杂度，但在末尾追加时，若容量足够则为 均摊常数时间（O(1)）。
// 简化的扩容伪代码示例
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 约 1.5 倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
从实现层面看，ArrayList 的核心冲击点在于 连续数组与引用的组合，这带来高效的缓存友好性和快速的下标访问，但也带来容量预估问题和大量的位移成本。
在 Java 实现中，ArrayList 还受益于类型擦除带来的轻量对象封装与引用优化，但本质上仍然是一个非固定大小的引用数组，其容量是可调整的。
LinkedList 的实现原理
LinkedList 采用的是 双向链表（doubly linked list），每个节点通常包含三个域：item、next、prev，通过节点之间的指针建立起一个线性序列。链表的头尾通常由 head 与 tail 指针表示，size 记录链表中元素数量。
由于不存在连续的内存块，任意位置的插入/删除在理论上可以是 O(1) 的时间复杂度（若已定位到节点），但前提是你已经通过遍历定位到该节点。遍历定位需要时间，这使得随机访问在 LinkedList 中的成本较高，通常为 O(n)。
双向链接的结构带来更高的 内存开销，因为每个节点需要额外的 两个指针，以及单独的对象封装。这也意味着访问链表中的数据时，缓存局部性较差，影响实际性能。
// 简化的 Node 结构示例
static class Node {
E item;
Node next;
Node prev;
Node(E element, Node prev, Node next) {
this.item = element;
this.prev = prev;
this.next = next;
}
}
LinkedList 的实现强调了灵活的结点插入与删除能力，尤其在需要频繁在中间位置进行结构调整时表现出优势，因为不涉及大规模元素的移动。
性能对比
访问与搜索性能
ArrayList 在 下标访问 时，底层通过数组下标直接定位元素，时间复杂度为 O(1)，适合随机访问场景。缓存局部性好，连续的内存布局让 CPU 读取效率更高。
LinkedList 的 get/set 等基于索引的访问需要从头部或尾部遍历，最坏情况下为 O(n)，因此对于大量随机访问而言逐渐显得低效。遍历成本随位置变化但总体线性，不如 ArrayList 高效。
为了避免重复遍历，部分实现会在遍历时从头部或尾部选择更近的一端，但这仍然是线性时间。
插入与删除性能
ArrayList 在末尾添加元素通常是 O(1) 均摊时间，但在中间插入或删除时需要移动后续元素，时间复杂度为 O(n)，同时可能触发扩容。大规模中间操作成本高，并且可能引发频繁的内存拷贝。
LinkedList 在已定位位置进行插入或删除时通常是 O(1)，因为只需要调整前后节点指针即可；然而要定位到该位置仍需遍历，综合成本通常为 O(n)。对于频繁在两端进行增删的场景，LinkedList 的优势会更明显。
// 链表插入（伪代码）
Node newNode = new Node<>(value, prev, next);
prev.next = newNode;
next.prev = newNode;
size++;
此外，ArrayList 的连续内存使缓存友好性更高，访问一段连续数据时的缓存命中率通常高于 LinkedList，这也是前者在大多数读多写少的场景更优的原因之一。
空间复杂度对比
ArrayList 的核心是一个可扩容的对象数组，每个元素仅占用一个引用的空间，总的空间主要来自容量与实际元素数之间的差额。内存利用率取决于容量策略。
LinkedList 的每个节点除了存放数据，还要联结前后节点，因而会产生较高的 内存开销，每个元素大致需要额外的两个引用指针。综合而言，LinkedList 的 单位元素内存开销显著高于 ArrayList，在大数据量场景下影响明显。
最佳使用场景
何时选择 ArrayList
当需要快速的 随机访问、大量读取和按下标获取元素时，ArrayList 是更合适的选择。其连续的内存布局也使得 缓存命中率高、性能更稳定，特别是在执行大量读取操作时优势明显。
如果你对未来容量有一定预估，或者可以通过调用 ensureCapacity 提前分配空间，以减少扩容和数据拷贝带来的开销。
代码示例演示了如何以初始容量创建并批量填充数据，以提升初始化阶段的性能。
List list = new ArrayList<>(1000); // 预分配容量
for (int i = 0; i < 1000; i++) {
list.add("item" + i);
}
何时选择 LinkedList
当场景涉及大量在两端或中间进行频繁的插入/删除时，且对随机访问要求不高时，LinkedList 的优势会更加突出。因为不需要像数组一样在中间位置执行大量数据移动，它在维护结构完整性方面更灵活。
如果你需要实现一个双端队列（deque）、或在链表上进行频繁的头尾操作，LinkedList 提供了高效的头尾操作接口，尽管对中间访问的成本较高，但在特定工作负载下可以获得更好的整体性能。
Deque deque = new LinkedList<>();
deque.addFirst("head");
deque.addLast("tail");
deque.removeFirst();
deque.removeLast();
需要注意的是，LinkedList 的内存开销较大以及缓存局部性差，若数据量较大且主要执行读取，通常应优先考虑 ArrayList，在绝对必要的频繁插入/删除场景再考虑 LinkedList。
