题 何时使用LinkedList而不是ArrayList?


我一直只是一个人使用:

List<String> names = new ArrayList<>();

我使用接口作为类型名称 可移植性,所以当我问这些问题时,我可以修改我的代码。

什么时候应该 LinkedList 被用完了 ArrayList 反之亦然?


2568
2017-11-27 01:36


起源


也可以看看: 数组与链表 - Hawkeye Parker
只需看看LinkedList作者的引用 stackoverflow.com/a/42529652/2032701 你会对这个问题有实际的认识。 - Ruslan


答案:


概要  ArrayList 同 ArrayDeque 是优选的 许多 更多的用例比 LinkedList。不确定 - 刚开始 ArrayList


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

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

对于 LinkedList<E>

  • get(int index) 是 上) (与 N / 4 平均步数)
  • add(E element) 是 O(1)
  • add(int index, E element) 是 上) (与 N / 4 平均步数), 但 O(1) 什么时候 index = 0  <---主要的好处 LinkedList<E>
  • remove(int index) 是 上) (与 N / 4 平均步数)
  • Iterator.remove() 是 O(1)。 <---主要的好处 LinkedList<E>
  • ListIterator.add(E element) 是 O(1)  这是主要的好处之一 LinkedList<E>

注意:许多操作都需要 N / 4 平均步数, 不变 最佳情况下的步数(例如,索引= 0),和 n / 2个 最糟糕的情况下的步骤(列表中间)

对于 ArrayList<E>

  • get(int index) 是 O(1)  <---主要的好处 ArrayList<E>
  • add(E element) 是 O(1) 摊销但是 上) 最糟糕的情况,因为数组必须调整大小并复制
  • add(int index, E element) 是 上) (与 n / 2个 平均步数)
  • remove(int index) 是 上) (与 n / 2个 平均步数)
  • Iterator.remove() 是 上) (与 n / 2个 平均步数)
  • ListIterator.add(E element) 是 上) (与 n / 2个 平均步数)

注意:许多操作都需要 n / 2个 平均步数, 不变 最佳案例中的步骤数(列表末尾), ñ 最糟糕的情况下的步骤(列表的开头)

LinkedList<E> 允许恒定插入或移除 使用迭代器,但只能顺序访问元素。换句话说,您可以向前或向后遍历列表,但在列表中查找位置需要的时间与列表的大小成比例。 Javadoc说 “索引到列表中的操作将从开头或结尾遍历列表,以较近者为准”,那些方法是 上) (N / 4 但是,平均而言 O(1) 对于 index = 0

ArrayList<E>另一方面,允许快速随机读取访问,因此您可以在恒定时间内获取任何元素。但是,除了末端之外的任何地方添加或移除都需要将所有后面的元素移位,以便打开或填补空白。此外,如果添加的元素多于底层数组的容量,则会分配一个新数组(大小的1.5倍),并将旧数组复制到新数组,因此添加到 ArrayList 是 上) 在最坏的情况下,但平均不变。

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

使用a的主要好处 LinkedList 当您重复使用现有迭代器来插入和删除元素时出现。然后可以在这些操作中完成 O(1) 通过仅在本地更改列表。在数组列表中,数组的其余部分必须是 移动 (即复制)。另一方面,寻求一个 LinkedList 意味着跟随链接 上) (n / 2个 步骤)对于最坏的情况,而在一个 ArrayList 可以数学计算所需位置并访问 O(1)

使用a的另一个好处 LinkedList 当您从列表的头部添加或删除时,会出现这些操作 O(1)虽然他们是 上) 对于 ArrayList。注意 ArrayDeque 可能是一个很好的选择 LinkedList 用于添加和删除头部,但它不是一个 List

此外,如果您有大型列表,请记住内存使用情况也不同。 a的每个元素 LinkedList 由于还存储了指向下一个和前一个元素的指针,因此开销更大。 ArrayLists 没有这个开销。然而, ArrayLists 占用与容量分配的内存,无论是否实际添加了元素。

一个默认的初始容量 ArrayList 非常小(来自Java 1.4 - 1.8的10)。但由于底层实现是一个数组,因此如果添加大量元素,则必须调整数组大小。为了避免在你知道要添加大量元素时调整大小的高成本,构建 ArrayList 具有更高的初始容量。


2847
2017-10-06 06:46



忘了提到插入费用。在LinkedList中,一旦你有正确的位置,插入成本为O(1),而在ArrayList中它会上升到O(n) - 必须移动经过插入点的所有元素。 - David Rodríguez - dribeas
关于Vector的使用:确实没有必要回到Vector。执行此操作的方法是使用首选的List实现和对synchronizedList的调用,以便为其提供同步包装。看到: java.sun.com/docs/books/tutorial/collections/implementations/... - Ryan Cox
不,对于LinkedList,即使您知道位置,get仍然是O(n),因为为了到达该位置,底层实现必须遍历链表的“下一个”指针以获得该位置的值。没有随机访问这样的东西。对于位置2,步行指针可能便宜,但对于位置100万,不是那么便宜。关键是,它与位置成正比,这意味着它是O(n)。 - Jonathan Tran
@Kevin记忆“紧密相连”可能很重要。硬件会将连续的内存块(动态RAM)缓存到L1或L2缓存中更快的静态RAM中。理论上和大多数时候实际上,内存可以被视为随机访问。但实际上,顺序读取内存的速度会比随机顺序快一些。对于性能关键的循环,这可能很重要。他们称之为“空间位置”或 参考地点。 - Jonathan Tran
没有这样的事情 O(n/2) 要么 O(n/4)。大O符号告诉你如何操作 秤 更大 ñ。和需要的操作 n/2 步骤与完成需要的操作完全相同 n 步骤,这就是为什么删除常量加数或因子的原因。 O(n/2) 和 O(n/4) 都是 O(n)。 LinkedList 和 ArrayList 无论如何都有不同的常数因素,所以不能比较a O(n/2) 一个人的 O(n/4) 另一方面,两者都表示线性缩放操作。 - Holger


到目前为止,除了a的普遍共识之外,似乎没有人解决这些列表中每个列表的内存占用问题 LinkedList 是“更多”而不是 ArrayList 所以我做了一些数字处理来准确地证明两个列表占用了多少N个空引用。

由于在它们的相关系统上引用是32位或64位(即使为空),我已经为32位和64位包含了4组数据 LinkedLists 和 ArrayLists

注意: 显示的尺寸为 ArrayList 线是为 修剪过的清单  - 实际上,支持阵列的容量 ArrayList 通常大于其当前元素数。

笔记2:  (感谢BeeOnRope) 由于CompressedOops现在默认从JDK6中间开始,因此64位机器的下面的值基本上与它们的32位机器相匹配,除非您特别关闭它。


Graph of LinkedList and ArrayList No. of Elements x Bytes


结果清楚地表明了这一点 LinkedList 是一个不仅仅是 ArrayList,特别是元素数量非常多。如果记忆是一个因素,请避开 LinkedLists

我使用的公式如下,让我知道如果我做错了什么我会解决它。对于32位或64位系统,'b'为4或8,'n'是元素的数量。注意mods的原因是因为java中的所有对象将占用8个字节空间的倍数,无论它是否全部使用。

ArrayList

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

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)

535
2017-11-27 14:20



非常有趣的是,LinkedList需要与ArrayList一样多的内存来存储单个元素。多么不直观!如果使用-XX运行示例会发生什么:+ UseCompressedOops? - jontejj
你的数学问题是你的图表极大地夸大了影响。您正在建模每个只包含一个对象的对象 int,所以4或8个字节的数据。在链表中,基本上有4个“单词”的开销。因此,您的图表给出了链接列表使用“五次”存储数组列表的印象。这是错的。开销是每个对象16或32个字节,作为附加调整,而不是缩放因子。 - Heath Hunnicutt
没有ArrayList / LinkedList / Node对象只包含一个int,所以我不知道你在那里说什么。我已经将“对象开销”重写为'对象标题'到clarfy - 无论系统如何,每个对象都有一个8字节的标头,是的,它包含了LinkedList中的所有Node对象,这些都是我能够正确计算的。告诉。顺便说一下,再次看一下,我确实在LinkedList中发现了我的数学问题,这实际上是将它除以它和ArrayList 更差。我很乐意不断更新它,所以请不要犹豫,澄清并精心制作。 - Numeron
应当指出的是 CompressedOops 现在在所有最近的JDK中都是默认的(7,8和几年的6更新),因此64位不会产生影响 ArrayList 要么 LinkedList 大小,除非您出于某种原因明确关闭了压缩的oops。 - BeeOnRope
图表的图像是否可用于商业用途?我想用它。 - Ogen


ArrayList 是你想要的。 LinkedList 几乎总是一个(性能)错误。

为什么 LinkedList 吮吸:

  • 它使用大量小内存对象,因此会影响整个过程的性能。
  • 很多小对象都不利于缓存局部性。
  • 任何索引操作都需要遍历,即具有O(n)性能。这在源代码中并不明显,导致算法O(n)比if慢 ArrayList被使用了。
  • 获得良好的表现很棘手。
  • 即使大O的表现与之相同 ArrayList,无论如何,它可能会明显变慢。
  • 很难看 LinkedList 在源头,因为它可能是错误的选择。

190
2018-01-01 20:23



抱歉。标记了你。 LinkedList不太糟糕。在某些情况下,LinkedList是要使用的正确类。我同意没有很多情况下它比arraylist更好,但它们确实存在。教育做傻事的人! - David Turner
很抱歉看到你为此获得了很多的选票。确实没有理由使用Java的LinkedList。除了糟糕的性能之外,它还使用了比其他具体List类更多的内存(每个节点都有两个额外的指针,每个节点都是一个单独的包装器对象,带有额外的开销字节)。 - Kevin Brock
这是这里最有用的答案之一。令人遗憾的是,许多程序员都无法理解(a)抽象数据类型和具体实现之间的区别,以及(b)在确定性能时常数因素和内存开销的现实重要性。 - Porculus
-1:这是一个相当模糊的观点。是的,ArrayList确实是一个非常通用的工具。但是,它有其局限性。有些情况会导致您遇到麻烦,您将不得不使用LinkedList。当然,它是一种非常专业的解决方案,并且,作为任何专用工具,在大多数情况下,它的性能优于多功能工具。但这并不意味着它“糟透了”或类似的东西,你只需要知道何时使用它。 - Malcolm
@DavidTurner:他们确实存在,但我认为汤姆的观点是,如果你不得不问,你可能想要ArrayList。 - Mehrdad


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

类似地,您可以从默认吞吐量终身垃圾收集器中获得更好的应用程序吞吐量,但是一旦获得具有10GB堆的Java应用程序,您可以在完整GC期间锁定应用程序25秒,这会导致SOA应用程序超时和失败并且如果太频繁发生,则会破坏您的SLA。即使CMS收集器占用更多资源并且无法实现相同的原始吞吐量,但它是一个更好的选择,因为它具有更可预测和更小的延迟。

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


125
2018-04-08 20:33



另一种解决方案是不是通过使用ArrayList的ensureCapacity()方法以编程方式管理列表的大小?我的问题是,当它们最好存储在缓存或数据库机制中时,为什么这么多东西存储在一堆脆弱的数据结构中呢?前几天我接受了采访,他们就ArrayList的邪恶起伏不定,但我来到这里,我发现复杂性分析更好!很重要的讨论点。谢谢! - ingyhere
一旦你获得了10GB堆的java应用程序,你可以在完整的GC中锁定应用程序25秒,这会导致超时 实际上,使用LinkedList,您在完整的GC期间谋杀垃圾收集器,它必须迭代过大的LinkedList,每个节点上都有缓存未命中。 - bestsss
那是......一个可怕的解决方案。当你只需要在arraylist上调用ensureCapacity()时,你基本上依赖于GC为你清理,这是非常昂贵的...... - Philip Devine
@Andreas:A LinkedList  总是 分配内存的五倍比简单的引用数组,所以 ArrayList 暂时需要2.5次仍然消耗更少的内存,即使内存没有回收。由于大型数组分配绕过Eden空间,它们对GC行为没有任何影响,除非实际上没有足够的内存,在这种情况下, LinkedList 早点爆炸...... - Holger
@Andreas另一个问题是如何分配内存。 LinkedList只需要一小段可用内存来分配下一个元素。 ArrayList 将需要一个大的 连续 空闲的空间块来分配调整大小的数组。如果堆碎片化,那么GC可能最终重新排序整个堆,只是为了释放合适的单个内存块。 - Piotr Kusmierczyk


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)

算法:Big-Oh表示法

ArrayLists适合一次写入多次读取或appender,但在前面或中间添加/删除时效果不佳。


111
2018-05-19 11:21



如果不考虑常数因素,就无法直接比较big-O值。对于小列表(并且大多数列表很小),ArrayList的O(N)比LinkedList的O(1)快。 - Porculus
我不关心小清单的性能,也不关心我的电脑 除非 它以某种方式在循环中使用。 - Maarten Bodewes
LinkedList无法真正插入到中间 O(1)。它必须遍历列表的一半才能找到插入点。 - Thomas Ahle
LinkedList:插入中间O(1) - 错误!我发现即使插入LinkedList大小的1/10位置也比将元素插入ArrayList的1/10位置要慢。更糟糕的是:收集的结束。插入到ArrayList的最后位置(不是最后一个位置)比在LinkedList的最后位置(不是最后位置)更快 - kachanov
@kachanov插入一个 LinkedList  是  O(1)  如果你有一个插入位置的迭代器,即 ListIterator.add 据说是 O(1) 为一个 LinkedList。 - Anony-Mousse


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

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

有一个常见的用例,其中LinkedList优于ArrayList:队列的那个。但是,如果您的目标是性能,而不是LinkedList,您还应该考虑使用ArrayBlockingQueue(如果您可以提前确定队列大小的上限,并且可以预先分配所有内存),或者这样做 CircularArrayList实现。 (是的,它是从2001年开始的,所以你需要对它进行一般化,但我的性能比率与刚刚在最近的JVM中引用的内容相当)


92
2017-11-27 01:39



从Java 6你可以使用 ArrayDeque。 docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html - Thomas Ahle
ArrayDeque 比...慢 LinkedList 除非所有操作都在同一端。当用作堆栈时它没有问题,但它没有成为一个好的队列。 - Jeremy List
不真实 - 至少对于Oracle在jdk1.7.0_60和以下测试中的实现。我创建了一个测试,我循环了1000万次,我有一个1000万随机整数的Deque。在循环内部,我从中调出一个元素并提供一个常量元素。在我的计算机上,LinkedList比ArrayDeque慢10倍以上并且占用的内存更少。原因是,与ArrayList不同,ArrayDeque保留了一个指向数组头部的指针,这样在移除头部时不必移动所有元素。 - Henno Vermeulen
ArrayDeque 可能会快于 Stack 当用作堆栈时,速度比 LinkedList 当用作队列时。 - i_am_zero
请注意,akhil_mittal的评论是来自的引用 ArrayDeque 文档。 - Stuart Marks


这是一个效率问题。 LinkedList 添加和删​​除元素很快,但访问特定元素的速度很慢。 ArrayList 访问特定元素的速度很快,但添加到任何一端都很慢,特别是在中间删除速度很慢。

Array vs ArrayList vs LinkedList vs Vector更深入,也是如此 链接列表


50
2017-09-21 22:59





正确或不正确:请在本地执行测试并自行决定!

编辑/删除速度更快 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<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(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<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        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<String> arrayList = new ArrayList<String>(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<String> linkedList = new LinkedList<String>();
        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<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(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<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        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<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(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<String> linkedList = new LinkedList<String>();
        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<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(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<String> linkedList = new LinkedList<String>();
        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);
    }
}

49
2018-04-21 00:03



确切地说,ArrayList不需要加倍。请先检查来源。 - Danubian Sailor
应该注意的是你的例子是有缺陷的...你要从以下字符串中删除:18 + [2,12]字节(“true0false”,“true500000false”),平均25个字节,这是元素的大小在中间。众所周知,随着元素字节大小的增加,链表的表现会更好,随着列表大小的增加,连续的数组(列表)会做得更好。最重要的是,你在字符串上执行.equals() - 这不是一个廉价的操作。如果你改用整数,我认为会有所不同。 - Centril
- 这也可能也是为什么删除/包含的差别很小的原因。 - Centril
” ... 在大批量应用中更糟糕“:这是一种误解。 LinkedList 具有更多的内存开销,因为每个元素都有一个包含五个字段的节点对象。在许多系统上,产生20个字节的开销。每个元素的平均内存开销 ArrayList 是一个半字,它产生6个字节,在最坏的情况下是8个字节。 - Lii
我已经做了更好的基准版本 在这里,结果  - arraylist的追加性能对你来说是人为的低,因为addAll给出了一个初始大小的存储数组,所以第一个插入总是触发arraycopy。此外,这还包括预热周期,以便在收集数据之前进行JIT编译。 - BobMcGee


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

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

LinkedList 添加和删​​除速度更快,但获取速度更慢。简单来说, LinkedList 应优先考虑:

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

=== 数组列表 ===

  • 添加(E e)
    • 在ArrayList的末尾添加
    • 需要内存调整成本。
    • O(n)最差,O(1)摊销
  • add(int index,E element)
    • 添加到特定的索引位置
    • 需要转移和可能的内存调整成本
    • 上)
  • remove(int index)
    • 删除指定的元素
    • 需要转移和可能的内存调整成本
    • 上)
  • 删除(对象o)
    • 从此列表中删除指定元素的第一个匹配项
    • 需要首先搜索元素,然后转移和可能的内存调整大小成本
    • 上)

=== 链表 ===

  • 添加(E e)

    • 添加到列表的末尾
    • O(1)
  • add(int index,E element)

    • 插入指定位置
    • 需要先找到位置
    • 上)
  • 去掉()
    • 删除列表的第一个元素
    • O(1)
  • remove(int index)
    • 删除具有指定索引的元素
    • 需要先找到元素
    • 上)
  • 删除(对象o)
    • 删除指定元素的第一个匹配项
    • 需要先找到元素
    • 上)

这是一个图 programcreek.com (add 和 remove 是第一种类型,即在列表的末尾添加一个元素,并删除列表中指定位置的元素。):

enter image description here


38
2017-11-27 01:41



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


ArrayList 随机可访问,而 LinkedList 是非常便宜的扩展和删除元素。对于大多数情况, ArrayList 很好。

除非您创建了大型列表并测量了瓶颈,否则您可能永远不必担心差异。


30
2017-07-07 09:22



LinkedList对于添加元素并不便宜。向ArrayList添加一百万个元素几乎总是比将它们添加到LinkedList更快。实际代码中的大多数列表甚至都不是一百万个元素。 - Porculus
在任何给定的点上,您都知道将项目添加到LinkedList的成本。你没有的ArrayList(一般来说)。将单个项添加到包含一百万个项的ArrayList 可以 需要很长时间 - 这是一个O(n)操作加上存储的两倍,除非你预先分配空间。将项添加到LinkedList是O(1)。我最后的发言是。 - Dustin
将单个项添加到ArrayList是O(1),无论它是100万还是10亿。将项添加到LinkedList也是O(1)。 “添加”意味着添加到最后。 - kachanov
你必须以不同于我的方式阅读实现。根据我的经验,复制10亿个元素数组比复制100万个元素数组需要更长的时间。 - Dustin
@kachanov你必须误解达斯汀。除非你已经声明了一个包含10亿个项目的数组,否则你最终需要调整数组的大小,在这种情况下你需要将所有元素复制到一个新的更大的数组中,因此有时你会得到O(N),但是有了链表,你将永远得到O(1) - Stan R.