ArrayList和LinkedList是什么？
- ArrayList： ArrayList是Java集合框架中的一个类，它实现了List接口，底层基于数组实现。ArrayList的特点是支持动态数组，可以自动扩容，适合顺序访问和随机访问。
- LinkedList： LinkedList也是Java集合框架中的一个类，同样实现了List接口，但底层基于链表实现。LinkedList的特点是支持高效的插入和删除操作，但随机访问的性能相对较差。
区别与优缺点对比
ArrayList和LinkedList区别
| ArrayList | LinkedList | |
|---|---|---|
| 获取指定元素 | 速度很快 | 需要从头开始查找元素 |
| 添加元素到末尾 | 速度很快 | 速度很快 |
| 在指定位置添加/删除 | 需要移动元素 | 不需要移动元素 |
| 内存占用 | 少 | 较大 |
| 集合 | 底层结构 | 增删效率 | 改查效率 |
|---|---|---|---|
| ArrayList | 可变数组 | 较低,数组扩容 | 快,索引定位 |
| LinkedList | 双向链表 | 较高.通过链表追加 | 慢 |
-
**存储结构：**ArrayList使用数组作为底层数据结构，数据在内存中是连续存储的，因此支持随机访问非常快速。LinkedList则使用链表作为底层数据结构，每个元素都包含指向前后元素的指针，插入和删除操作非常高效。
-
**插入与删除操作：**在ArrayList中，如果插入或删除元素，可能会导致数组元素的移动，从而影响性能。而LinkedList在插入和删除操作上具有明显优势，因为只需修改指针的指向，不需要移动大量元素。
-
**随机访问性能：**由于ArrayList的数组连续存储特性，它在随机访问上具有很好的性能。通过索引即可直接访问元素。而LinkedList需要从头或尾开始遍历链表，随机访问性能较差。
-
**内存占用：**由于LinkedList每个元素都需要存储前后指针，相对于ArrayList会占用更多的内存空间。如果需要存储大量数据，考虑内存占用也是一个重要因素。
-
**迭代性能：**在迭代（遍历）操作上，ArrayList由于连续存储的特性，性能通常较好。而LinkedList在迭代操作上由于需要通过指针跳转，性能相对较差。
-
扩容机制：
ArrayList当容量不足时，会进行扩容操作，涉及到复制元素，开销较大。LinkedList不需要扩容，按需添加节点。
使用ArrayList的场景：
- 需要频繁进行随机访问，例如根据索引获取元素。
- 数据集合相对固定，不需要频繁的插入和删除操作。
- 内存占用相对较少，不会造成严重的资源浪费。
使用LinkedList的场景：
-
需要频繁进行插入和删除操作，尤其是在中间位置。
-
不关心随机访问性能，而更关注插入和删除的效率。
-
可能需要更少的内存占用，尤其是在元素数量较少的情况下。
参考：《Think In Java》
