- 正确答案：ArrayList基于动态数组实现，支持O(1)随机访问，但插入/删除（非尾部）需移动元素，平均时间复杂度为O(n)；LinkedList基于双向链表实现，不支持高效随机访问（O(n)），但头尾插入/删除为O(1)，中间位置插入/删除在已知节点引用时为O(1)，否则需先查找节点（O(n)）。二者均非线程安全，允许null元素，都实现了List接口和Serializable、Cloneable接口。 - 解答思路：从底层数据结构出发，分析其对核心操作（get、add、remove、indexOf等）的时间复杂度影响；进一步对比内存布局（连续 vs 分散）、缓存友好性、空间开销（ArrayList仅存储元素+少量元数据；LinkedList每个节点额外存储prev/next引用，约多占用16~24字节/元素）；再结合JVM对象模型（如对象头、对齐填充）说明实际内存占用差异；最后根据性能特征映射到典型应用场景。 - 深度知识讲解： 1. ArrayList底层是Object[]数组（JDK 8起为transient Object[] elementData），扩容机制：初始容量为0（空实例），首次add时扩容至10；后续扩容为oldCapacity + oldCapacity >> 1（即1.5倍），通过Arrays.copyOf完成。扩容涉及堆内存分配与数组复制，是潜在性能瓶颈。注意：elementData被声明为transient，序列化时通过writeObject手动序列化有效元素（避免序列化冗余容量），反序列化时重建数组并逐个添加。 2. LinkedList底层是Node双向链表：private static class Node { E item; Node next; Node prev; }。每个Node对象在HotSpot JVM中至少占用：对象头（12字节，含mark word 8字节 + klass pointer 4字节）、item引用（4字节，开启指针压缩）、next/prev引用（各4字节）、对齐填充（若总大小不足16字节倍数则补足）。实测在64位JVM+UseCompressedOops下，单个Node约24字节（12+4+4+4），远超ArrayList单元素4字节引用开销。因此LinkedList空间效率低，且节点分散导致CPU缓存命中率差（cache line不友好）。 3. 随机访问差异本质源于内存局部性原理：ArrayList元素物理连续，CPU预取机制高效；LinkedList节点地址随机分布，每次访问next/prev需重新加载cache line，造成大量cache miss。 4. 迭代器行为差异：ArrayList.iterator()返回内部类Itr，fail-fast机制依赖modCount（修改计数器），任何结构性修改（add/remove）都会使modCount++，迭代中检测到不一致则抛ConcurrentModificationException；LinkedList同理，但其ListIterator还支持add()（在当前节点前插入）和set()，这是由双向链表结构天然支持的。 5. 特殊方法支持：ArrayList无专门头尾快速操作API；LinkedList实现了Deque接口，提供offerFirst/Last、pollFirst/Last、peekFirst/Last等O(1)双端队列操作——这使其可直接作为栈（push/pop）、队列（offer/poll）、双端队列使用，而无需额外包装。 - 典型场景建议： • 优先选ArrayList：需频繁随机访问（如遍历中按索引查值、二分查找、排序、批量拷贝）、内存敏感、读多写少、利用foreach或for(int i=0; i node(int index) { if (index < (size >> 1)) { // 折半优化：从前或从后遍历 Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } LinkedList.addFirst(E e)： public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { final Node f = first; final Node newNode = new Node<>(null, e, f); // O(1)对象创建+指针重连 first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } - 扩展提醒：在高并发场景下，二者均不适用，应选用CopyOnWriteArrayList（读多写少）、ConcurrentLinkedQueue（无界线程安全队列）或Collections.synchronizedList包装；若需排序+快速查找，考虑TreeSet/TreeMap；现代Java开发中，如需不可变集合，优先使用List.of()或guava的ImmutableList。

广电面经

全站热榜

创作者周榜