arraylist随机访问快（o(1)），但中间插入/删除慢（o(n)）；linkedlist头尾增删快（o(1)），但随机访问慢（o(n)）；选型需结合实际操作模式，而非仅看理论复杂度。
ArrayList 随机访问快，但中间插入/删除慢
因为 ArrayList 底层是动态数组，支持通过下标直接定位元素，get(int index) 是 O(1) 时间复杂度。但一旦在中间位置调用 add(int index, E element) 或 remove(int index)，就要把后续所有元素整体拷贝移动，最坏是 O(n)。
常见错误：用 ArrayList 在循环中反复 remove() 满足条件的元素，没注意索引偏移，导致漏删或 IndexOutOfBoundsException；或者误以为 list.add(0, x) 很便宜，实际每次都在头部插入，性能急剧下降。
- 适合场景：读多写少、频繁按索引查值、需要
Arrays.binarySearch()或Collection.toArray()的场合 - 注意扩容：初始容量默认是 10，触发扩容时会新建数组并
System.arraycopy()，有额外开销；若已知大致大小，建议构造时传入initialCapacity - 线程不安全：多线程环境下直接使用会出错，别指望“偶尔跑一次没问题”
LinkedList 插入删除快，但随机访问极慢
LinkedList 是双向链表实现，addFirst()、addLast()、removeFirst()、removeLast() 全是 O(1)；在已有 ListIterator 位置附近增删也是 O(1)。但它的 get(int index) 必须从头或尾开始遍历指针，平均 O(n/2)，比 ArrayList 慢一个数量级。
很多人以为 “LinkedList 适合频繁增删”，却忽略了前提：必须是头尾操作，或已有迭代器定位点。用 list.get(i) 再 remove(i) 实际是两次遍历，比 ArrayList 还慢。
立即学习“Java免费学习笔记（深入）”；
- 适合场景：当逻辑天然符合队列（
offer()/poll()）、栈（push()/pop()）或需在遍历中动态增删（配合ListIterator）时才真正受益 - 内存开销大：每个元素额外存两个指针（
prev和next），对象头+引用本身比数组元素占用多 50% 以上内存 - 不支持快速随机访问：
subList()返回的是SubList视图，但底层仍是链表遍历，不是切片优化
选型不能只看“理论复杂度”，得看真实操作模式
面试常问“什么情况选哪个”，但真实项目里，多数人卡在“根本没想清楚自己在做什么操作”。比如：
- 用
for (int i = 0; i —— 这是典型误用，无论 <code>ArrayList还是LinkedList都很糟糕；正确做法是用Iterator.remove()或removeIf() - 需要频繁按条件查找后删除：先用
Stream.filter()收集新列表，比原地删更清晰且往往更快 - 数据量小（LinkedList，要当数组就用
ArrayList） - 若真需要头尾高效 + 随机访问，考虑
ArrayDeque（非List实现，但比LinkedList更省内存、缓存友好）
别忽略替代方案：Vector、CopyOnWriteArrayList、Collections.synchronizedList
面试可能延伸问线程安全。记住：Vector 是历史遗留类，所有方法加了 synchronized，但锁粒度太粗，实际并发性能差；CopyOnWriteArrayList 适合读远多于写的场景（如监听器列表），但每次写都复制整个数组，大数据量写操作代价极高；Collections.synchronizedList(new ArrayList()) 只是对单个方法加锁，复合操作（如先 size() 再 get()）仍需手动同步。
真正高并发场景，通常应跳过这些 List，改用 ConcurrentHashMap 模拟集合，或用 java.util.concurrent 下更合适的结构（如 ConcurrentLinkedQueue）。
List<String> safeList = Collections.synchronizedList(new ArrayList<>());
// 下面这段仍然不是线程安全的！
if (safeList.size() > 0) {
String first = safeList.get(0); // 中间可能被其他线程清空
}
链表和数组的选择，本质是时间与空间、局部性与灵活性的权衡。很多人死记“ArrayList 查快、LinkedList 增删快”，却忘了现代 CPU 缓存对连续内存的偏好——哪怕 ArrayList 删除要搬动数据，只要数组不大，也常常比 LinkedList 遍历几十个分散对象更快。
