arraylist linkedlist面试

### ArrayList 和 LinkedList 的比较

#### 数据结构基础
ArrayList 和 LinkedList 是两种常见的列表实现，在 Java 中都实现了 `List` 接口。然而，两者内部的数据存储机制不同，这影响了它们的操作性能。

- **ArrayList** 使用动态数组来保存元素[^3]。
- **LinkedList** 则通过双向链表的方式连接各个节点[^3]。

#### 性能差异分析
对于不同的操作，这两种数据结构表现出显著的不同：

- **随机访问**
- 对于 `ArrayList` 来说，由于其底层基于数组，因此支持高效的索引查找 O(1)。
- 而 `LinkedList` 需要遍历链表才能找到指定位置的元素，时间复杂度为 O(n)，效率较低。

- **插入与删除**
- 当涉及到频繁地向中间或头部添加新项时，`LinkedList` 更具优势，因为只需要调整相邻结点之间的指针即可完成操作，平均时间为常数级别 O(1)。
- 反之，如果是在固定大小接近满载的情况下执行此类动作，则 `ArrayList` 将不得不移动大量现有成员以腾出空间给新的条目，最坏情况下达到线性的开销 O(n)。

// 插入到 List 开头的例子
list.add(0, element);

- **内存占用**
- 每个 `LinkedList` 结点除了储存实际对象外还需额外记录前后链接的信息，所以通常会比相同长度下的 `ArrayList` 占用更多内存资源。

#### 应用场景建议
根据上述特性对比可知：
- 如果应用程序主要涉及大量的读取而较少修改的话，推荐选用 `ArrayList`；
- 若程序中有较多增删需求特别是针对两端的情况，那么 `LinkedList` 或许更适合一些。