ArrayList

• 默认大小为10，每次扩大为1.5倍
• 数组扩容时需要复制旧数组内容到新数组
• 预分配内存，效率高
• 适合绝大多数场景（顺序添加、遍历、随机访问等）。当你需要一个List时，就选它

LinkedList

• 每个节点对应一个Node对象，保存前后指针，增加了内存占用
• 查找指定位置时会先计算与头部和尾部的距离，哪个近就从哪里开始遍历（双向链表）
• 实现了Deque接口，当你需要双向队列或经常变动头部节点时，就选它

实现和复杂度对比

| 类型 | ArrayList | LinkedList |
| —

| —

| —

– |
| 实现方式 | 动态数组 | 双向链表 |
| 内存分步 | 连续 | 不连续 |
| 查询效率 | O(n) | O(n) |
| 随机访问效率 | ***O(1)***，下标访问 | *O(n)*，遍历至指定位置 |
| 随机增加/删除效率 | *O(n)*，需移动数组，但很快 | *O(n)*，遍历找到节点 |
| 头部添加删除效率 | *O(n)*，需移动后续数组 | O(1) |
| 尾部添加删除效率 | *O(1)*，添加时可能需要扩容数组 | O(1) |