考虑到 ArrayList 没有大小限制，Java 中的 LinkedList 的目的是什么？
What is the purpose of a LinkedList in Java Considering an ArrayList Has No Size Limit?
在很多帖子中，当我读到 LinkedList 的好处时，我听到的最频繁的好处是在某些情况下 LinkedList 的性能更高，因为插入和删除比数组更快。
具体来说，争论点是数组的使用效率较低，因为为了扩展它们，必须将内容复制到具有更大声明大小的不同数组中。
但是，由于Java 有没有容量限制的ArrayList，所以关于LinkedLists 性能更高的观点似乎并不成立。 Java 中的 LinkedLists 现在已经过时了吗？在 Java 中，在某些情况下 LinkedList 实际上仍然是比 ArrayList 更好的选择？
假设您有一个包含 100,000（或一些类似数量）元素的列表。
假设您想在开头或中间某处插入一个元素。
对于 ArrayList，您需要将每个元素 移回一个位置以腾出空间。显然，这需要 O(n) 次操作。
使用LinkedList，你只需要创建一个新节点并将其插入。如果你已经知道你需要它的位置，这是一个O(1)操作。
反之亦然删除 - 特别是当列表大小变大，并且索引相对于插入和删除变得不那么重要时，链接列表比数组列表具有性能优势。
从教育的角度来看，这是对链表演示概念的折扣，这些概念对于以后扩展到树和图很重要。但这不是你要问的。
ArrayList 内部有一个数组，为了动态它有时需要扩展内部数组。
Internal Working of ArrayList in Java
ArrayList 通过在必要时自动调整自身大小来实现无限容量。因此，它仍必须将元素复制到新位置。唯一的区别是，它是在幕后完成的，而不是要求您（程序员）这样做。
What is the purpose of a LinkedList in Java considering an ArrayList has no size limit?
LinkedList 客观上优于 ArrayList 的情况并不多。
首先是一些基本事实：
- 两种列表类型的大小都是动态的（没有区别）。
ArrayList 每个元素占用的内存比 LinkedList 少。 4 倍或更多。 （每个元素一个指针与三个指针加上堆节点的开销。）- 如果您严重错误地估计了
ArrayList 的初始容量，它会比 LinkedList 使用更多的内存。 （但这确实是一个应用程序错误。）
ArrayList 的大多数操作速度更快。
- 位置操作是
O(1) 与 O(N)
- 对于大型列表，局部性与内存缓存/TLB 缓存/VM 页面未命中的性能影响可能很重要。
- 对于
LinkedList，某些操作可以更快；例如插入和删除。但是，这取决于具体情况；例如插入或删除的位置，或者该操作是否触发支持数组的扩展。
那么在哪些情况下 LinkedList 可能是有利的？
一种情况是在列表的开头添加和删除元素。 LinkedList 为 O(1)，ArrayList 为 O(N)。 （ArrayDeque 通常是比 LinkedList 更好的选择...除了它没有实现 List API。）
第二种情况是遍历一个列表，在遍历过程中添加或删除元素。 LinkedList.listIterator 方法 returns 一个 ListIterator 允许您在当前位置添加或删除元素。这些是 O(1) 个操作。
第三，如果您的应用程序极度不能容忍（例如）列表附加 可能 需要很长时间，那么 LinkedList 可能是有利的。 （想想硬实时应用程序....）
最后，说ArrayList没有大小限制其实是不正确的。它实际上限于略低于 2^31 个元素。这是因为 Java 数组被 JVM 限制为略低于 2^31 个元素。 LinkedList没有这个问题。
Are LinkedLists now obsolete in Java?
没有
class 很少使用（而且一直都是），但它并没有过时。
我记得 Brian Goetz 曾说过，回想起来，实施 LinkedList 可能不值得付出努力。但是鉴于付出了努力，您应该在需要时随意使用 class。
请注意，您需要考虑对列表执行的所有操作。这通常很难提前完成。而且（程序员）的努力通常是不合理的。由于 ArrayList 通常被证明是最佳选择，因此它是大多数程序员的默认选择。
避免过早优化的陷阱....
在很多帖子中，当我读到 LinkedList 的好处时，我听到的最频繁的好处是在某些情况下 LinkedList 的性能更高，因为插入和删除比数组更快。
具体来说，争论点是数组的使用效率较低，因为为了扩展它们，必须将内容复制到具有更大声明大小的不同数组中。
但是，由于Java 有没有容量限制的ArrayList，所以关于LinkedLists 性能更高的观点似乎并不成立。 Java 中的 LinkedLists 现在已经过时了吗？在 Java 中，在某些情况下 LinkedList 实际上仍然是比 ArrayList 更好的选择？
假设您有一个包含 100,000（或一些类似数量）元素的列表。
假设您想在开头或中间某处插入一个元素。
对于 ArrayList，您需要将每个元素 移回一个位置以腾出空间。显然，这需要 O(n) 次操作。
使用LinkedList，你只需要创建一个新节点并将其插入。如果你已经知道你需要它的位置，这是一个O(1)操作。
反之亦然删除 - 特别是当列表大小变大，并且索引相对于插入和删除变得不那么重要时，链接列表比数组列表具有性能优势。
从教育的角度来看，这是对链表演示概念的折扣，这些概念对于以后扩展到树和图很重要。但这不是你要问的。
ArrayList 内部有一个数组，为了动态它有时需要扩展内部数组。 Internal Working of ArrayList in Java
ArrayList 通过在必要时自动调整自身大小来实现无限容量。因此，它仍必须将元素复制到新位置。唯一的区别是，它是在幕后完成的，而不是要求您（程序员）这样做。
What is the purpose of a LinkedList in Java considering an ArrayList has no size limit?
LinkedList 客观上优于 ArrayList 的情况并不多。
首先是一些基本事实：
- 两种列表类型的大小都是动态的（没有区别）。
ArrayList每个元素占用的内存比LinkedList少。 4 倍或更多。 （每个元素一个指针与三个指针加上堆节点的开销。）- 如果您严重错误地估计了
ArrayList的初始容量，它会比LinkedList使用更多的内存。 （但这确实是一个应用程序错误。） ArrayList的大多数操作速度更快。- 位置操作是
O(1)与O(N) - 对于大型列表，局部性与内存缓存/TLB 缓存/VM 页面未命中的性能影响可能很重要。
- 位置操作是
- 对于
LinkedList，某些操作可以更快；例如插入和删除。但是，这取决于具体情况；例如插入或删除的位置，或者该操作是否触发支持数组的扩展。
那么在哪些情况下 LinkedList 可能是有利的？
一种情况是在列表的开头添加和删除元素。 LinkedList 为 O(1)，ArrayList 为 O(N)。 （ArrayDeque 通常是比 LinkedList 更好的选择...除了它没有实现 List API。）
第二种情况是遍历一个列表，在遍历过程中添加或删除元素。 LinkedList.listIterator 方法 returns 一个 ListIterator 允许您在当前位置添加或删除元素。这些是 O(1) 个操作。
第三，如果您的应用程序极度不能容忍（例如）列表附加 可能 需要很长时间，那么 LinkedList 可能是有利的。 （想想硬实时应用程序....）
最后，说ArrayList没有大小限制其实是不正确的。它实际上限于略低于 2^31 个元素。这是因为 Java 数组被 JVM 限制为略低于 2^31 个元素。 LinkedList没有这个问题。
Are LinkedLists now obsolete in Java?
没有
class 很少使用（而且一直都是），但它并没有过时。
我记得 Brian Goetz 曾说过，回想起来，实施 LinkedList 可能不值得付出努力。但是鉴于付出了努力，您应该在需要时随意使用 class。
请注意，您需要考虑对列表执行的所有操作。这通常很难提前完成。而且（程序员）的努力通常是不合理的。由于 ArrayList 通常被证明是最佳选择，因此它是大多数程序员的默认选择。
避免过早优化的陷阱....