何时在 Java 中使用 LinkedList 而不是 ArrayList？

柔光的暖阳◎ 2024-03-30 10:26 22阅读 0赞

## 问： ##

我一直是一个简单使用的人：

List names = new ArrayList<>();

我使用接口作为可移植性的类型名称，因此当我提出这样的问题时，我可以重新编写我的代码。

何时应在 ArrayList 上使用 LinkedList，反之亦然？

## 答1: ##

> huntsbot.com高效搞钱，一站式跟进超10+任务平台外包需求

总结 ArrayList 与 ArrayDeque 在许多 比 LinkedList 更多的用例中更可取。如果您不确定 — 只需从 ArrayList 开始。

TLDR，在 ArrayList 中访问元素需要恒定时间 \[O(1)\]，添加元素需要 O(n) 时间 \[最坏情况\]。在 LinkedList 中，插入元素需要 O(n) 时间，访问也需要 O(n) 时间，但 LinkedList 使用的内存比 ArrayList 多。

LinkedList 和 ArrayList 是 List 接口的两种不同实现。 LinkedList 使用双向链表实现它。 ArrayList 使用动态调整大小的数组来实现它。

与标准链表和数组操作一样，各种方法将具有不同的算法运行时。

对于LinkedList

get(int index) 是 O(n) （平均有 n/4 步），但是当 index = 0 或 index = list.size() - 1 时为 O(1) （在这种情况下，您也可以使用 getFirst( ) 和 getLast())。 LinkedList 的主要好处之一

add(int index, E element) 为 O(n) （平均有 n/4 步），但当 index = 0 或 index = list.size() - 1 时为 O(1) （在这种情况下，您也可以使用 addFirst() 和 addLast()/add())。 LinkedList 的主要好处之一

remove(int index) 是 O(n) （平均有 n/4 步），但是当 index = 0 或 index = list.size() - 1 时为 O(1) （在这种情况下，您也可以使用 removeFirst( ) 和 removeLast())。 LinkedList 的主要好处之一

Iterator.remove() 是 O(1)。 LinkedList 的主要好处之一

ListIterator.add(E 元素) 是 O(1)。 LinkedList 的主要好处之一

注意：许多操作平均需要 n/4 步，最佳情况下的步数恒定（例如 index = 0），最坏情况下需要 n/2 步（列表中间）

对于ArrayList

获取（整数索引）是 O(1)。 ArrayList 的主要好处

add(E element) 是 O(1) 摊销，但 O(n) 最坏情况，因为必须调整数组的大小和复制

add(int index, E element) 是 O(n) （平均有 n/2 步）

remove(int index) 是 O(n) （平均有 n/2 步）

Iterator.remove() 是 O(n) （平均有 n/2 步）

ListIterator.add(E element) 是 O(n) （平均有 n/2 步）

注意：许多操作平均需要 n/2 步，最佳情况下（列表末尾）的步数恒定，最坏情况下（列表开头）需要 n 步

LinkedList 允许使用迭代器 进行恒定时间的插入或删除，但只能按顺序访问元素。换句话说，您可以向前或向后遍历列表，但在列表中查找位置所花费的时间与列表的大小成正比。 Javadoc 说 “索引到列表中的操作将从开头或结尾遍历列表，以较近者为准”，因此这些方法是 O(n) (n/4 步），但对于 index = 0 O(1)。

另一方面，ArrayList 允许快速随机读取访问，因此您可以在恒定时间内抓取任何元素。但是从任何地方添加或删除，但最后需要将所有后面的元素转移过来，要么打开一个开口，要么填补空白。此外，如果添加的元素多于基础数组的容量，则会分配一个新数组（大小的 1.5 倍），并将旧数组复制到新数组，因此添加到 ArrayList 是 O (n) 在最坏的情况下但平均保持不变。

因此，根据您打算执行的操作，您应该相应地选择实现。迭代任何一种 List 实际上同样便宜。 （迭代 ArrayList 在技术上更快，但除非您正在做一些真正对性能敏感的事情，否则您不必担心这一点——它们都是常量。）

当您重新使用现有迭代器来插入和删除元素时，使用 LinkedList 的主要好处就出现了。这些操作可以在 O(1) 中通过仅在本地更改列表来完成。在数组列表中，数组的其余部分需要移动（即复制）。另一方面，在 LinkedList 中搜索意味着在最坏的情况下遵循 O(n) 中的链接（n/2 步），而在 ArrayList所需位置可以通过数学计算并在 O(1) 中访问。

使用 LinkedList 的另一个好处是当您从列表的头部添加或删除时，因为这些操作是 O(1)，而它们是 O(n) 对于 ArrayList。请注意，ArrayDeque 可能是 LinkedList 的一个很好的替代方法，用于添加和删除头部，但它不是 List。

此外，如果您有大型列表，请记住内存使用量也不同。 LinkedList 的每个元素都有更多开销，因为还存储了指向下一个和前一个元素的指针。 ArrayLists 没有这种开销。但是，无论是否实际添加了元素，ArrayLists 都会占用为容量分配的内存。

ArrayList 的默认初始容量非常小（Java 1.4 - 1.8 为 10）。但是由于底层实现是一个数组，如果添加很多元素，则必须调整数组的大小。为避免在您知道要添加大量元素时调整大小的高成本，请构造具有更高初始容量的 ArrayList。

如果从数据结构的角度来理解这两种结构，LinkedList 基本上是一个包含头节点的顺序数据结构。 Node 是两个组件的包装器：一个 T 类型的值 \[通过泛型接受\] 和另一个对链接到它的 Node 的引用。所以，我们可以断言它是一个递归数据结构（一个节点包含另一个节点，另一个节点有另一个节点，依此类推…）。如上所述，在 LinkedList 中添加元素需要线性时间。

ArrayList 是一个可增长的数组。它就像一个常规数组。在幕后，当添加一个元素并且 ArrayList 已经满载时，它会创建另一个大小大于先前大小的数组。然后将元素从先前的数组复制到新数组，并且要添加的元素也放置在指定的索引处。

`许多人忘记的一件事是 ArrayList 在内存中是紧凑的，这意味着它比 LinkedList 对缓存更友好。 LinkedList 可以分布在整个 RAM 中，而 ArrayList 总是紧贴在一起以利用空间局部性。这对现实世界有重要的影响。`

`@AminM 只有对象引用是紧凑的。对象本身可以分散......直到我们得到值类型。`

`@swpalmer 当然。但是，在 LinkedList 中只是为了找到您正在寻找的项目，您正在浏览您的 RAM 布局。而使用 ArrayList，您可以扫描它而几乎没有缓存未命中。缓存未命中对性能来说很重要。`

`@AminM我的意思是，要找到您要查找的内容，您可能仍需要遵循该参考并可能遭受缓存未命中。除非您只关心参考身份。我知道在链接的情况下，您可能会遭受缓存未命中，只是获取引用本身。我只是说 Java 数组也以另一种方式遭受缓存未命中...直到 Valhalla。`

`@swpalmer 我的观点是它的缓存未命中率要低得多。在极端。其他人在这里发布了性能比较。您可以肯定，使用 LinkedList 几乎总是会获得更差的性能。`

## 答2: ##

> 与HuntsBot一起，探索全球自由职业机会–huntsbot.com

到目前为止，除了 LinkedList 比 ArrayList “多得多”这一普遍共识之外，似乎没有人解决每个列表的内存占用问题，所以我做了一些数字运算来准确证明两个列表占用了多少对于 N 个空引用。

由于引用在其相关系统上是 32 位或 64 位（即使为空），因此我为 32 位和 64 位 LinkedLists 和 ArrayLists 包含了 4 组数据。

注意： ArrayList 行显示的大小适用于修剪后的列表 - 实际上，ArrayList 中的后备数组的容量通常大于其当前的容量元素计数。

注意 2：（感谢 BeeOnRope）由于 CompressedOops 现在是 JDK6 中期及更高版本的默认值，因此以下 64 位机器的值将基本匹配它们的 32 位对应物，当然除非您特别将其关闭。

https://i.imgur.com/f83xDyz.png

结果清楚地表明 LinkedList 比 ArrayList 多得多，尤其是在元素数量非常多的情况下。如果内存是一个因素，请避开 LinkedLists。

我使用的公式如下，如果我做错了什么，请告诉我，我会修复它。对于 32 位或 64 位系统，“b”是 4 或 8，“n”是元素的数量。注意 mods 的原因是因为 java 中的所有对象无论是否全部使用都会占用 8 字节空间的倍数。

数组列表：

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b \* n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b \* n) + MOD(12 + b \* n, 8) + MOD(8 + 4 + 4 + b + (12 + b \* n) + MOD(12 + b \* n, 8), 8)

链表：

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) \* n) + MOD(node object, 8) \* n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 \* b + (8 + 3 \* b) \* n + MOD(8 + 3 \* b, 8) \* n + MOD(8 + 4 + 4 + 2 \* b + (8 + 3 \* b) \* n + MOD(8 + 3 \* b, 8) \* n, 8)

> huntsbot.com – 程序员副业首选，一站式外包任务、远程工作、创意产品分享订阅平台。

`您的数学问题在于您的图表大大夸大了影响。您正在对每个仅包含一个 int 的对象进行建模，即 4 或 8 个字节的数据。在链表中，基本上有 4 个“词”的开销。因此，您的图表给人的印象是链表使用了“五倍”的数组列表存储空间。这是错误的。开销是每个对象 16 或 32 个字节，作为附加调整，而不是缩放因子。`

## 答3: ##

> huntsbot.com洞察每一个产品背后的需求与收益，从而捕获灵感

ArrayList 是您想要的。 LinkedList 几乎总是一个（性能）错误。

为什么 LinkedList 很烂：

它使用大量的小内存对象，因此会影响整个进程的性能。

许多小对象不利于缓存局部性。

任何索引操作都需要遍历，即具有 O(n) 性能。这在源代码中并不明显，导致算法 O(n) 比使用 ArrayList 慢。

获得良好的性能是棘手的。

即使 big-O 性能与 ArrayList 相同，它也可能会明显变慢。

在源代码中看到 LinkedList 令人震惊，因为它可能是错误的选择。

## 答4: ##

> huntsbot.com – 程序员副业首选，一站式外包任务、远程工作、创意产品分享订阅平台。

Algorithm           ArrayList   LinkedList
    seek front            O(1)         O(1)
    seek back             O(1)         O(1)
    seek to index         O(1)         O(N)
    insert at front       O(N)         O(1)
    insert at back        O(1)         O(1)
    insert after an item  O(N)         O(1)

Algorithms: Big-Oh Notation（存档）

ArrayLists 适用于一次写入多次读取或附加程序，但不适合从前面或中间添加/删除。

`如果不考虑常数因素，就无法直接比较大 O 值。对于小列表（并且大多数列表都很小），ArrayList 的 O(N) 比 LinkedList 的 O(1) 快。`

`我不关心小列表的性能，我的计算机也不关心，除非它以某种方式循环使用。`

`LinkedList 不能真正插入 O(1) 的中间。它必须遍历列表的一半才能找到插入点。`

`LinkedList：插入中间 O(1) - 是错误的！我发现即使插入到 LinkedList 大小的 1/10 位置也比将元素插入 ArrayList 的 1/10 位置要慢。更糟糕的是：收集结束。插入到 ArrayList 的最后一个位置（不是最后一个位置）比插入到 LinkedList 的最后一个位置（不是最后一个位置）更快`

`@kachanov 插入 LinkedList is O(1) 如果您有一个指向插入位置的迭代器，即 ListIterator.add 应该是 LinkedList 的 O(1) .`

## 答5: ##

> huntsbot.com聚合了超过10+全球外包任务平台的外包需求，寻找外包任务与机会变的简单与高效。

作为一个在超大规模 SOA Web 服务上进行操作性能工程大约十年的人，我更喜欢 LinkedList 的行为而不是 ArrayList。虽然 LinkedList 的稳态吞吐量更差，因此可能会导致购买更多硬件 - ArrayList 在压力下的行为可能会导致集群中的应用程序以近乎同步的方式扩展其阵列，并且对于大阵列大小可能会导致缺乏响应能力在应用程序和中断，而在压力下，这是灾难性的行为。

同样，您可以从默认吞吐量的终身垃圾收集器中获得更好的应用程序吞吐量，但是一旦您获得具有 10GB 堆的 Java 应用程序，您可能会在 Full GC 期间锁定应用程序 25 秒，这会导致 SOA 应用程序超时和失败如果它发生得太频繁，就会破坏你的 SLA。尽管 CMS 收集器占用更多资源并且无法达到相同的原始吞吐量，但它是一个更好的选择，因为它具有更高的可预测性和更小的延迟。

如果您所说的性能是吞吐量并且您可以忽略延迟，那么 ArrayList 只是性能更好的选择。根据我的工作经验，我不能忽视最坏情况下的延迟。

更新（2021 年 8 月 27 日——10 年后）：这个答案（我对 SO 历史上最受好评的答案）很可能是错误的（原因在下面的评论中列出）。我想补充一点，ArrayList 将优化内存的顺序读取并最大限度地减少缓存行和 TLB 未命中等。相比之下，当数组增长超过界限时的复制开销可能是无关紧要的（并且可以通过高效的 CPU 操作来完成）。考虑到硬件趋势，随着时间的推移，这个答案也可能变得更糟。 LinkedList 可能有意义的唯一情况是高度做作的事情，您有数千个列表，其中任何一个都可能增长到 GB 大小，但是在分配列表和设置它们时无法做出好的猜测所有到 GB 大小的都会炸毁堆。如果你发现了这样的问题，那么它确实需要重新设计你的解决方案（我不喜欢轻易建议重新设计旧代码，因为我自己维护成堆的旧代码，但那将是一个非常好的案例，原始设计只是跑出了跑道，确实需要被淘汰）。不过，我仍然会将我几十年前的糟糕观点留在那里供您阅读。简单，合乎逻辑而且非常错误。

`不是另一种解决方案是通过使用 ArrayList 的 ensureCapacity() 方法以编程方式管理列表的大小吗？我的问题是为什么这么多东西被存储在一堆脆弱的数据结构中，而它们可能更好地存储在缓存或数据库机制中？前几天我接受了一次采访，他们上下发誓 ArrayList 的邪恶，但我来到这里，我发现复杂性分析是全方位的更好！不过，讨论的重点。谢谢！`

`一旦你获得了具有 10GB 堆的 Java 应用程序，你可能会在 Full GC 期间锁定应用程序 25 秒，这会导致超时实际上使用 LinkedList 你会在 Full GC 期间谋杀垃圾收集器，它必须迭代过大的 LinkedList 并缓存未命中每个节点。`

`那是......一个可怕的解决方案。你基本上依赖于 GC 为你清理，这非常昂贵，当你可以在 arraylist 上调用 ensureCapacity() 时......`

`@Holger 一个超过其容量递增的数组列表会分配一个多出 50% 空间的新列表。对于该增量，您需要 2.5 倍的内存（之后您可能需要完整的 gc 循环）。我不关心日常响应时间，我担心当高峰时间比昨天稍微重一点时堆内存用完，几个大数组列表决定他们需要一秒钟的 2.5 倍计数的空间或两个。在高峰使用期间，这种行为的一个实例使我整个月的 sla 都受到打击。`

`@Andreas：LinkedList always 分配的内存是普通引用数组的五倍，因此即使内存没有回收，临时需要 2.5 倍的 ArrayList 仍然消耗更少的内存。由于大数组分配绕过了 Eden 空间，它们对 GC 行为没有任何影响，除非内存确实不够，在这种情况下，LinkedList 会更早地爆炸……`

## 答6: ##

> huntsbot.com洞察每一个产品背后的需求与收益，从而捕获灵感

是的，我知道，这是一个古老的问题，但我会投入两分钱：

LinkedList 在性能方面几乎总是错误的选择。有一些非常特殊的算法需要 LinkedList，但这些算法非常非常罕见，并且该算法通常特别依赖于 LinkedList 在列表中间相对快速地插入和删除元素的能力，一旦你导航到那里使用 ListIterator。

LinkedList 优于 ArrayList 的一个常见用例是：队列。但是，如果您的目标是性能，而不是 LinkedList，您还应该考虑使用 ArrayBlockingQueue（如果您可以提前确定队列大小的上限，并且可以负担预先分配所有内存），或者这个 \{1 \}。 （是的，它是从 2001 年开始的，因此您需要对其进行泛化，但我得到的性能比与刚刚在最近的 JVM 中引用的文章中的内容相当）

`从 Java 6 开始，您可以使用 ArrayDeque。 docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html`

`ArrayDeque 比 LinkedList 慢，除非所有操作都在同一端。用作堆栈时还可以，但它不能构成一个好的队列。`

`不真实 - 至少对于 Oracle 在 jdk1.7.0_60 和以下测试中的实现。我创建了一个测试，其中循环了 1000 万次，并且我有一个包含 1000 万个随机整数的 Deque。在循环内部，我从中轮询一个元素并提供一个常量元素。在我的计算机上，LinkedList 比 ArrayDeque 慢 10 倍以上，并且使用的内存更少）。原因是与 ArrayList 不同，ArrayDeque 保留了一个指向数组头部的指针，因此当头部被移除时它不必移动所有元素。`

`ArrayDeque 用作堆栈时可能比 Stack 快，而用作队列时可能比 LinkedList 快。`

`请注意，akhil_mittal 的评论是对 ArrayDeque 文档的引用。`

## 答7: ##

> huntsbot.com提供全网独家一站式外包任务、远程工作、创意产品分享与订阅服务!

LinkedList 的作者 Joshua Bloch：

有人真的使用 LinkedList 吗？我写了它，我从不使用它。

链接：https://twitter.com/joshbloch/status/583813919019573248

我很抱歉这个答案没有像其他答案那样信息丰富，但我认为如果不透露的话，这将是最不言自明的。

## 答8: ##

> 打造属于自己的副业，开启自由职业之旅，从huntsbot.com开始!

这是一个效率问题。 LinkedList 添加和删除元素的速度很快，但访问特定元素的速度很慢。 ArrayList 访问特定元素的速度很快，但添加到任一端可能会很慢，尤其是在中间删除很慢。

Array vs ArrayList vs LinkedList vs Vector 更深入，Linked List 也是如此。

`在这里值得一提的是，LinkedList 仅在第一个和最后一个位置添加/删除速度很快 - 那么复杂度将是 O(1)，但在中间添加仍然是 O(n)，因为我们需要运行LinkedList 的大约 n/2 个元素。`

`是吗？ Why is an ArrayList always faster than a LinkedList 发现将 10M 项添加到 ArrayList 比将 10M 项添加到 LinkedList 更快。 （即 ArrayList 在最后添加时更快，有时不得不重新分配。）`

## 答9: ##

> 与HuntsBot一起，探索全球自由职业机会–huntsbot.com

正确或错误：请在本地执行测试并自行决定！

LinkedList 中的编辑/删除比 ArrayList 快。

ArrayList，以Array为后盾，需要加倍大小，在大容量应用中效果更差。

下面是每个操作的单元测试结果。时间以纳秒为单位。

Operation                       ArrayList                      LinkedList  
    
    AddAll   (Insert)               101,16719                      2623,29291 
    
    Add      (Insert-Sequentially)  152,46840                      966,62216
    
    Add      (insert-randomly)      36527                          29193
    
    remove   (Delete)               20,56,9095                     20,45,4904
    
    contains (Search)               186,15,704                     189,64,981

这是代码：

import org.junit.Assert;
    import org.junit.Test;
    
    import java.util.*;
    
    public class ArrayListVsLinkedList {
        
        private static final int MAX = 500000;
        String[] strings = maxArray();
    
        // ADD ALL 
        @Test
        public void arrayListAddAll() {
        
            Watch watch = new Watch();
            List stringList = Arrays.asList(strings);
            List arrayList = new ArrayList(MAX);
    
            watch.start();
            arrayList.addAll(stringList);
            watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
        }
    
        @Test
        public void linkedListAddAll() throws Exception {
        
            Watch watch = new Watch();
            List stringList = Arrays.asList(strings);
    
            watch.start();
            List linkedList = new LinkedList();
            linkedList.addAll(stringList);
            watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
        }
    
        //Note: ArrayList is 26 time faster here than LinkedList for addAll()
    
        / INSERT /
        @Test
        public void arrayListAdd() {
        
            Watch watch = new Watch();
            List arrayList = new ArrayList(MAX);
    
            watch.start();
            for (String string : strings)
                arrayList.add(string);
            watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
        }
    
        @Test
        public void linkedListAdd() {
        
            Watch watch = new Watch();
    
            List linkedList = new LinkedList();
            watch.start();
            for (String string : strings)
                linkedList.add(string);
            watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
        }
    
        //Note: ArrayList is 9 times faster than LinkedList for add sequentially
    
        /// INSERT IN BETWEEN ///
    
        @Test
        public void arrayListInsertOne() {
        
            Watch watch = new Watch();
            List stringList = Arrays.asList(strings);
            List arrayList = new ArrayList(MAX + MAX / 10);
            arrayList.addAll(stringList);
    
            String insertString0 = getString(true, MAX / 2 + 10);
            String insertString1 = getString(true, MAX / 2 + 20);
            String insertString2 = getString(true, MAX / 2 + 30);
            String insertString3 = getString(true, MAX / 2 + 40);
    
            watch.start();
    
            arrayList.add(insertString0);
            arrayList.add(insertString1);
            arrayList.add(insertString2);
            arrayList.add(insertString3);
    
            watch.totalTime("Array List add() = ");//36527
        }
    
        @Test
        public void linkedListInsertOne() {
        
            Watch watch = new Watch();
            List stringList = Arrays.asList(strings);
            List linkedList = new LinkedList();
            linkedList.addAll(stringList);
    
            String insertString0 = getString(true, MAX / 2 + 10);
            String insertString1 = getString(true, MAX / 2 + 20);
            String insertString2 = getString(true, MAX / 2 + 30);
            String insertString3 = getString(true, MAX / 2 + 40);
    
            watch.start();
    
            linkedList.add(insertString0);
            linkedList.add(insertString1);
            linkedList.add(insertString2);
            linkedList.add(insertString3);
    
            watch.totalTime("Linked List add = ");//29193
        }
    
    
        //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.
    
        // DELETE //
        @Test
        public void arrayListRemove() throws Exception {
        
            Watch watch = new Watch();
            List stringList = Arrays.asList(strings);
            List arrayList = new ArrayList(MAX);
    
            arrayList.addAll(stringList);
            String searchString0 = getString(true, MAX / 2 + 10);
            String searchString1 = getString(true, MAX / 2 + 20);
    
            watch.start();
            arrayList.remove(searchString0);
            arrayList.remove(searchString1);
            watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
        }
    
        @Test
        public void linkedListRemove() throws Exception {
        
            Watch watch = new Watch();
            List linkedList = new LinkedList();
            linkedList.addAll(Arrays.asList(strings));
    
            String searchString0 = getString(true, MAX / 2 + 10);
            String searchString1 = getString(true, MAX / 2 + 20);
    
            watch.start();
            linkedList.remove(searchString0);
            linkedList.remove(searchString1);
            watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
        }
    
        //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.
    
        / SEARCH ///
        @Test
        public void arrayListSearch() throws Exception {
        
            Watch watch = new Watch();
            List stringList = Arrays.asList(strings);
            List arrayList = new ArrayList(MAX);
    
            arrayList.addAll(stringList);
            String searchString0 = getString(true, MAX / 2 + 10);
            String searchString1 = getString(true, MAX / 2 + 20);
    
            watch.start();
            arrayList.contains(searchString0);
            arrayList.contains(searchString1);
            watch.totalTime("Array List addAll() time = ");//186,15,704
        }
    
        @Test
        public void linkedListSearch() throws Exception {
        
            Watch watch = new Watch();
            List linkedList = new LinkedList();
            linkedList.addAll(Arrays.asList(strings));
    
            String searchString0 = getString(true, MAX / 2 + 10);
            String searchString1 = getString(true, MAX / 2 + 20);
    
            watch.start();
            linkedList.contains(searchString0);
            linkedList.contains(searchString1);
            watch.totalTime("Linked List addAll() time = ");//189,64,981
        }
    
        //Note: Linked List is 500 Milliseconds faster than ArrayList
    
        class Watch {
        
            private long startTime;
            private long endTime;
    
            public void start() {
        
                startTime = System.nanoTime();
            }
    
            private void stop() {
        
                endTime = System.nanoTime();
            }
    
            public void totalTime(String s) {
        
                stop();
                System.out.println(s + (endTime - startTime));
            }
        }
    
    
        private String[] maxArray() {
        
            String[] strings = new String[MAX];
            Boolean result = Boolean.TRUE;
            for (int i = 0; i < MAX; i++) {
        
                strings[i] = getString(result, i);
                result = !result;
            }
            return strings;
        }
    
        private String getString(Boolean result, int i) {
        
            return String.valueOf(result) + i + String.valueOf(!result);
        }
    }

`准确地说，ArrayList 不需要加倍。请先检查来源。`

`应该注意的是，您的示例有缺陷......您正在从以下字符串中删除：18 + [2, 12] 字节（“true0false”，“true500000false”），平均 25 个字节，这是元素的大小在中间。众所周知，随着元素字节大小的增加，链表性能更好，随着列表大小的增加，连续数组（列表）会做得更好。最重要的是，您正在对字符串执行 .equals() - 这不是一个便宜的操作。如果您改为使用整数，我认为会有区别。`

`“...在大容量应用中更糟”：这是一种误解。 LinkedList 的内存开销要大得多，因为每个元素都有一个具有五个字段的节点对象。在许多产生 20 字节开销的系统上。 ArrayList 的每个元素的平均内存开销为一个半字，即 6 个字节，最坏情况下为 8 个字节。`

`我已经完成了您的基准测试 here, with results 的更好版本 - 数组列表的追加性能对您来说是人为地低，因为 addAll 提供了一个完全初始大小的存储数组，所以第一个插入总是触发一个数组复制.此外，这包括预热周期，以允许在收集数据之前进行 JIT 编译。`

`@BillK 从 Java 8 开始，您可以在适合的地方使用 removeIf(element -> condition)，与通过迭代器循环和删除相比，ArrayList 可以明显更快，因为不需要为每个单独的元素移动整个余数。这是否比 LinkedList 表现更好或更差取决于特定场景，因为理论上 LinkedList 是 O(1)，但仅删除单个节点需要多次内存访问，这很容易超过 { 2} 删除大量元素时。`

## 答10: ##

> huntsbot.com洞察每一个产品背后的需求与收益，从而捕获灵感

ArrayList 本质上是一个数组。 LinkedList 实现为双链表。

get 非常清楚。 ArrayList 的 O(1)，因为 ArrayList 允许使用索引进行随机访问。 LinkedList 的 O(n)，因为它需要先找到索引。注意：add 和 remove 有不同的版本。

LinkedList 的添加和删除速度更快，但获取速度较慢。简而言之，如果出现以下情况，应该首选 LinkedList：

没有大量的元素随机访问 有大量的添加/删除操作

=== 数组列表 ===

add(E e) 在 ArrayList 末尾添加需要内存调整成本。 O(n) 最差，O(1) 摊销

在 ArrayList 末尾添加

需要调整内存大小的成本。

O(n) 最差，O(1) 摊销

add(int index, E element) 添加到特定索引位置需要移位和可能的内存调整成本 O(n)

添加到特定的索引位置

需要转移和可能的内存调整成本

上）

remove(int index) 删除指定元素需要移位和可能的内存调整成本 O(n)

移除指定元素

需要转移和可能的内存调整成本

上）

remove(Object o) 从此列表中删除第一次出现的指定元素需要先搜索元素，然后移位和可能的内存调整成本 O(n)

从此列表中删除第一次出现的指定元素

需要先搜索元素，然后转移和可能的内存调整成本

上）

=== 链表 ===

add(E e) 添加到列表的末尾 O(1)

添加到列表的末尾

O(1)

add(int index, E element) 在指定位置插入需要先找到位置 O(n)

在指定位置插入

需要先找到位置

上）

remove() 删除列表的第一个元素 O(1)

删除列表的第一个元素

O(1)

remove(int index) 删除指定索引的元素 需要先找到元素 O(n)

移除指定索引的元素

需要先找到元素

上）

remove(Object o) 删除第一次出现的指定元素 需要先找到该元素 O(n)

删除指定元素的第一次出现

需要先找到元素

上）

这是programcreek.com中的一个图（add和remove是第一种，即在列表末尾添加一个元素并在列表中删除指定位置的元素。）：

https://i.stack.imgur.com/pdKaZ.png

> huntsbot.com – 程序员副业首选，一站式外包任务、远程工作、创意产品分享订阅平台。

`“LinkedList 比添加/删除更快”。错了，检查上面的答案stackoverflow.com/a/7507740/638670`

## 答11: ##

> huntsbot.com提供全网独家一站式外包任务、远程工作、创意产品分享与订阅服务!

TL;DR 由于现代计算机体系结构，ArrayList 对于几乎所有可能的用例都会显着提高效率 - 因此除了一些非常独特和极端的情况外，应避免使用 LinkedList。

理论上，LinkedList 对于 add(E element) 有一个 O(1)

此外，在列表中间添加一个元素应该非常有效。

实践非常不同，因为 LinkedList 是一个 Cache Hostile 数据结构。从性能 POV 来看 - 在极少数情况下，LinkedList 可能比 缓存友好 ArrayList 的性能更好。

以下是在随机位置插入元素的基准测试结果。如您所见 - 数组列表效率更高，尽管理论上列表中间的每个插入都需要“移动”数组的 n 个后面的元素（较低的值更好）：

https://i.stack.imgur.com/edAd8.png

在下一代硬件上工作（更大、更高效的缓存）——结果更具决定性：

https://i.stack.imgur.com/XtdBP.png

LinkedList 需要更多的时间来完成同样的工作。 source Source Code

这有两个主要原因：

主要是 - LinkedList 的节点随机分散在内存中。 RAM（“随机存取存储器”）并不是真正随机的，需要提取内存块进行缓存。这个操作需要时间，而且当这种抓取频繁发生时——缓存中的内存页需要一直被替换->缓存未命中->缓存效率不高。 ArrayList 元素存储在连续内存上——这正是现代 CPU 架构正在优化的目标。二级 LinkedList 需要保留后向/前向指针，这意味着与 ArrayList 相比，存储的每个值的内存消耗是 3 倍。

顺便说一句，DynamicIntArray 是一个自定义 ArrayList 实现，它包含 Int（原始类型）而不是对象 - 因此所有数据实际上都是相邻存储的 - 因此效率更高。

要记住的一个关键因素是，获取内存块的成本比访问单个内存单元的成本更重要。这就是为什么读取器 1MB 的顺序内存比从不同的内存块读取这么多的数据快 400 倍：

Latency Comparison Numbers (~2012)
    ----------------------------------
    L1 cache reference                           0.5 ns
    Branch mispredict                            5   ns
    L2 cache reference                           7   ns                      14x L1 cache
    Mutex lock/unlock                           25   ns
    Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
    Compress 1K bytes with Zippy             3,000   ns        3 us
    Send 1K bytes over 1 Gbps network       10,000   ns       10 us
    Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
    Read 1 MB sequentially from memory     250,000   ns      250 us
    Round trip within same datacenter      500,000   ns      500 us
    Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
    Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
    Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
    Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

来源：Latency Numbers Every Programmer Should Know

为了更清楚地说明这一点，请检查将元素添加到列表开头的基准。这是一个用例，从理论上讲，LinkedList 应该真正发挥作用，而 ArrayList 应该呈现较差甚至更坏的结果：

https://i.stack.imgur.com/2EygL.png

注意：这是 C++ 标准库的基准测试，但我之前的经验表明 C++ 和 Java 的结果非常相似。 Source Code

复制连续的大量内存是现代 CPU 优化的操作 - 改变理论并实际上再次使 ArrayList/Vector 更加高效

致谢：此处发布的所有基准均由 Kjell Hedström 创建。在 his blog 上可以找到更多数据

`我不会称队列为独特或极端！在 LinkedList 而不是 ArrayList 上实现 fifo 队列要容易得多。这实际上是 ArrayList 的一场噩梦，因为您必须跟踪自己的开始、停止和自己的重新分配，您不妨使用数组，但链表是先进先出。我不确定 Java 的实现，但 LinkedList 可以为队列和出队操作执行 O(1) .)`

`插入 ArrayList 数组的中间使用本地方法 java.lang.System.arraycopy()，该方法是在 OpenJDK 中用 C++ 编写的。因此，虽然理论上 LinkedList 在实践中要做的工作较少，但有很多语言外的机制使得“大 O”在很大程度上无关紧要。根据这个出色的答案，特别是缓存友好的东西。`

`谢谢，但最后一个基准测试有问题。 1）为什么“列表”持续时间甚至会增长？如果元素总是在开始处插入（0 索引），则它不依赖于大小。如果你的意思是在开始时插入，那么这个“周围”的接近程度起着重要作用 - 在 Java 中，将第 1000 个元素插入到预建的 100_000 数组中（多次）对于 LinkedList 来说仍然更快，并且只有在你接近时才会变得更慢结尾。 2）所以现在Java中的环绕开始插入对于LinkedList来说仍然更快。不过，我建议在这里使用技巧 - 在使用它之前反转列表。`

原文链接：[https://www.huntsbot.com/qa/2V10/when-to-use-linkedlist-over-arraylist-in-java?lang=zh\_CN&from=csdn][https_www.huntsbot.com_qa_2V10_when-to-use-linkedlist-over-arraylist-in-java_lang_zh_CN_from_csdn]

> huntsbot.com – 高效赚钱，自由工作

[https_www.huntsbot.com_qa_2V10_when-to-use-linkedlist-over-arraylist-in-java_lang_zh_CN_from_csdn]: https://www.huntsbot.com/qa/2V10/when-to-use-linkedlist-over-arraylist-in-java?lang=zh_CN&from=csdn