arraylist适合频繁随机访问，linkedlist适合频繁在头部或中间插入删除；前者基于动态数组，随机访问o(1)，后者基于双向链表，随机访问o(n)；尾部增删两者均o(1)，但arraylist有扩容开销；头部/中间增删linkedlist更优；arraylist内存连续、缓存友好，linkedlist额外空间多、缓存不友好。
ArrayList适合频繁随机访问，LinkedList适合频繁在头部或中间插入删除。
随机访问效率：ArrayList快，LinkedList慢
ArrayList底层是动态数组，通过索引直接计算内存地址，时间复杂度为O(1)。比如 get(500) 就是直接取第501个元素，不依赖前面的数据。
LinkedList是双向链表，没有连续内存，每次 get(i) 都得从头（或尾）开始逐个遍历节点，平均需要走一半长度，时间复杂度为O(n)。即使i接近末尾，也可能从头查起（除非JDK做了优化，但仍是线性查找）。
尾部增删：两者都较快，但ArrayList可能有扩容开销
- ArrayList.add(e)：一般O(1)，但容量不足时需扩容（复制原数组），均摊后仍是O(1)，单次可能达O(n)
- LinkedList.add(e)：尾部插入只需改tail指针和新建节点，稳定O(1)
- ArrayList.remove(size-1)：删末尾元素直接size--，O(1)
- LinkedList.removeLast()：同理，改指针即可，O(1)
头部或中间增删：LinkedList明显占优
在索引0处添加或删除（如add(0, e)、remove(0)）：
- ArrayList必须移动后续所有元素，最坏O(n)
- LinkedList只要调整头节点的prev/next引用，O(1)（前提是已定位到节点；若用add(index, e)，则先要get(index)，查找本身是O(n)，整体仍O(n)，但纯链表操作部分是O(1)）
在中间位置（如index = size/2）插入：ArrayList移动约n/2个元素；LinkedList虽也要先遍历到位置（O(n)），但插入动作本身仍比数组搬移轻量。
内存与缓存友好性：ArrayList更优
ArrayList元素在内存中连续存储，CPU缓存命中率高，遍历时速度快；LinkedList每个节点含前后指针，额外占用空间，且节点分散，缓存不友好，实际运行中常比理论复杂度体现得更慢。
