Java 中 ArrayList 和 LinkedList 的区别

ArrayList

在 Java 中，ArrayList 是一个可调整大小的数组。它属于 java.util 包。与固定大小的常规数组不同，ArrayList 可以在添加或删除元素时动态地增长或收缩。

ArrayList 的主要特点

• 动态调整大小：无需预先指定大小。
• 允许重复元素：与 set 不同，它允许重复。
• 维护插入顺序：元素按照添加的顺序存储。
• 随机访问：使用基于索引的方法进行快速检索。
• 非同步：与 Vector 不同，ArrayList 不是线程安全的。

阅读更多 Java ArrayList

LinkedList

LinkedList 是 List 和 Deque 接口的双向链表实现。它也使用动态数组，就像 ArrayList 一样。LinkedList 中的每个元素都存储为一个节点。每个节点包含：数据（实际元素）、指向下一个节点的引用、指向前一个节点的引用（在双向链表中）。

LinkedList 的主要特点

• 高效的插入/删除
• 维护插入顺序
• 实现了 List 和 Deque
• 非同步

阅读更多 Java LinkedList

Java 中 ArrayList 和 LinkedList 的示例

让我们看一个简单的示例，我们在其中使用 ArrayList 和 LinkedList。

输出

arraylist: [Andrew, John, Lucy, Peter]
linkedlist: [Akshat, Satwik, Aryan, Hrithik]

因此，ArrayList 和 LinkedList 都实现了 List 接口并维护插入顺序。它们都是非同步类。

ArrayList vs. LinkedList

注意事项

以下是关于 ArrayList 和 LinkedList 的一些重要注意事项。

• 当添加或删除的速率高于读取速率时，请选择 LinkedList。另一方面，当读取场景的频率高于添加或删除速率时，ArrayList 的优先级高于 LinkedList。
• 由于 ArrayList 的元素存储比 LinkedList 更紧凑；因此，与 LinkedList 相比，ArrayList 更具缓存友好性。因此，与 LinkedList 相比，ArrayList 发生缓存未命中的几率较低。通常认为 LinkedList 的缓存局部性较差。
• LinkedList 的内存开销比 ArrayList 大。这是因为在 LinkedList 中，我们有两个额外的链接（next 和 previous），因为需要存储前一个和下一个节点的地址，而这些链接会消耗额外的空间。ArrayList 中不存在这样的链接。

Java ArrayList 和 LinkedList 简答题

1. 哪种数据结构更适合频繁插入和删除元素的场景？

1. ArrayList，因为它使用动态数组。
2. LinkedList，因为它使用双向链表。
3. ArrayList，因为它更具缓存友好性。
4. LinkedList，因为它以连续的方式存储元素。

2. LinkedList 的内存开销与 ArrayList 相比如何，为什么？

1. LinkedList 的内存开销较低，因为它使用节点指针。
2. ArrayList 的内存开销较高，因为它需要动态调整大小。
3. LinkedList 的内存开销较高，因为它为每个元素存储额外的链接（next 和 previous）。
4. ArrayList 的内存开销较低，因为它以连续的方式存储元素。

3. 在性能方面，为什么在随机访问操作中 ArrayList 可能优于 LinkedList？

1. ArrayList 元素的存储方式是带有链接的节点，从而加快了访问速度。
2. LinkedList 元素的存储方式是连续的，这加快了访问速度。
3. ArrayList 为随机访问提供恒定时间复杂度（O(1)）。
4. LinkedList 为随机访问提供恒定时间复杂度（O(1)）。

4. ArrayList 和 LinkedList 之间一个重要的与缓存相关的性能差异是什么？

1. LinkedList 的缓存友好性更好，因为元素以连续的方式存储。
2. ArrayList 的缓存友好性更好，因为元素以连续的方式存储。
3. LinkedList 的缓存局部性较差，因为元素以非连续的方式存储。
4. ArrayList 的缓存未命中率较高，因为元素以非连续的方式存储。

5. 以下哪些接口由 ArrayList 和 LinkedList 实现，LinkedList 额外提供了哪些功能？

1. 两者都实现了 Set 接口；LinkedList 额外实现了 Deque。
2. 两者都实现了 List 接口；LinkedList 额外实现了 Deque。
3. ArrayList 实现 List 和 Queue；LinkedList 只实现 List。
4. 两者都实现了 Collection 接口；LinkedList 额外实现了 Stack。