ArrayList和LinkedList的区别及使用场景？
请全面对比Java中ArrayList和LinkedList的区别，包括底层数据结构、插入/删除/查询的时间复杂度、内存占用、扩容机制以及各自的最佳使用场景。
回答
苦行僧
ArrayList：
- 底层：动态数组（Object[]）
- 随机访问：O(1) — 数组索引直接定位
- 尾部插入：均摊O(1)，扩容时O(n)
- 中间插入/删除：O(n) — 需要移动元素
- 扩容：默认容量10，每次扩容1.5倍，Arrays.copyOf
- 内存：连续内存，空间利用率高
LinkedList：
- 底层：双向链表（Node内部类）
- 随机访问：O(n) — 需要遍历
- 首尾插入/删除：O(1)
- 中间插入/删除：O(n) — 需要先找到位置
- 不需扩容
- 内存：每个节点额外存储prev/next指针
选择建议：
- 频繁随机访问 → ArrayList
- 频繁首尾插入删除 → LinkedList（但ArrayDeque更优）
- 主要写操作且数据量大 → ArrayList