31 题: 何时在Java中使用LinkedList而不是ArrayList?

在...创建的问题 Tue, Sep 11, 2018 12:00 AM

我一直只是一个人使用:

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

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

何时应使用 LinkedList ArrayList ,反之亦然?

    
2863
  1. 另请参阅:数组与链接列表
    2016-10-12 03:58:29Z
  2. 只需看看LinkedList作者的引用 stackoverflow.com/a/42529652/2032701 ,您将对问题有实际意义。
    2017-12-26 19:17:59Z
  3. 醇>
    30答案                              30 跨度>                         

    摘要 ArrayListArrayDeque许多更多用例中优于LinkedList。如果您不确定 - 只需从ArrayList开始。


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

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

    LinkedList<E>

    •  get(int index) O(n)(平均 n /4 步骤)
    •  add(E element) O(1)
    •  add(int index, E element) O(n)(平均 n /4 步), 但 O(1)时为index = 0&lt; --- LinkedList<E>的主要好处
    •  remove(int index) O(n)(平均 n /4 步骤)
    •  Iterator.remove() O(1)。 &lt; --- LinkedList<E>的主要好处
    •  ListIterator.add(E element) O(1)这是LinkedList<E>的主要优点之一

    注意:许多操作平均需要 n /4 步骤,最佳情况下常量步数(例如index = 0),以及最坏情况下的 n /2 步骤(列表中间)

    ArrayList<E>

    •  get(int index) O(1)&lt; --- ArrayList<E>的主要好处
    •  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<E>允许使用迭代器进行常量时间插入或删除,但只允许顺序访问元素。换句话说,您可以向前或向后遍历列表,但在列表中查找位置需要的时间与列表的大小成比例。 Javadoc说“索引到列表中的操作将从开头或结尾遍历列表,以较近者为准”,因此这些方法是 O(n) n /4 步骤,但index = 0 O(1)

    另一方面,

    ArrayList<E>允许快速随机读取访问,因此您可以在恒定时间内获取任何元素。但是,除了末端之外的任何地方添加或删除都需要将所有后面的元素移位,以便打开或填补空白。此外,如果添加的元素多于底层数组的容量,则会分配一个新数组(大小的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中的10 - 1.8)。但由于底层实现是一个数组,因此如果添加大量元素,则必须调整数组大小。为了避免在您知道要添加大量元素时调整大小的高成本,请构建具有更高初始容量的ArrayList

        
    3135
    2019-05-03 00:36:52Z
    1. 忘记提及插入费用。在LinkedList中,一旦你有正确的位置,插入成本为O(1),而在ArrayList中它会上升到O(n) - 必须移动经过插入点的所有元素。
      2008-11-27 07:20:28Z
    2. 关于Vector的使用:确实没有必要回退到Vector。执行此操作的方法是使用首选的List实现并调用synchronizedList以为其提供同步包装。请参阅: java.sun.com/docs/books/tutorial/集合/实现方式/...
      2008-11-27 12:19:18Z
    3. 不,对于LinkedList,即使你知道位置,get仍然是O(n),因为为了到达那个位置,底层实现必须走链接列表的“下一个”指针,以获得该位置的值。没有随机访问这样的东西。对于位置2,步行指针可能很便宜,但对于位置100万,不是那么便宜。关键是,它与位置成正比,这意味着它是O(n)。
      2011-03-11 19:03:11Z
    4. @ Kevin内存“紧密相连”可能很重要。硬件会将连续的内存块(动态RAM)缓存到L1或L2缓存中更快的静态RAM中。理论上和大多数时候实际上,内存可以被视为随机访问。但实际上,顺序读取内存的速度会比随机顺序快一些。对于性能关键的循环,这可能很重要。他们称之为“空间位置”或参考地点
      2011-05-05 20:25:10Z
    5. 没有O(n/2)O(n/4)这样的东西。大O符号告诉您如何使用较大的 n 进行缩放。并且需要n/2步的操作与需要n步的操作完全相同,这就是为什么删除常数加法或因子的原因。 O(n/2)O(n/4)都只是O(n)LinkedListArrayList无论如何都有不同的常数因子,所以它不会比较aO(n/2)的另一个O(n/4),只是表示线性缩放操作。
      2016-07-04 09:57:35Z
    6. 醇>

    到目前为止,似乎没有人能够解决每个列表的内存占用情况,除了普遍的共识是LinkedListArrayList“更多”所以我做了一些数字处理来准确地证明两个列表占用了多少N个空引用。

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

    注意: ArrayList行显示的大小适用于修剪列表 - 实际上,ArrayList中支持阵列的容量通常大于其当前元素计数。

    注意2: (感谢BeeOnRope)由于CompressedOops现在默认从JDK6中部开始,因此64位机器的以下值基本上与32位相匹配同行,除非你特意把它关掉。



    结果清楚地表明,LinkedListArrayList多得多,特别是元素数量非常多。如果记忆是一个因素,请避开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 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)

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

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

    为什么LinkedList很糟糕:

    • 它使用大量小内存对象,因此影响整个过程的性能。
    • 许多小对象对缓存局部性不利。
    • 任何索引操作都需要遍历,即具有O(n)性能。这在源代码中并不明显,导致算法O(n)比使用ArrayList时慢。
    • 获得良好的表现很棘手。
    • 即使大O的表现与ArrayList相同,但无论如何它可能会明显变慢。
    • 在源代码中看到LinkedList是很不和谐的,因为它可能是错误的选择。
    223
    2017-10-09 13:27:37Z
    1. 抱歉。标记了你。 LinkedList不太糟糕。在某些情况下,LinkedList是要使用的正确类。我同意没有很多情况下它比arraylist更好,但它们确实存在。教育做傻事的人!
      2008-11-27 17:50:43Z
    2. 很抱歉看到你为此获得了大量的选票。确实没有理由使用Java的LinkedList。除了糟糕的性能之外,它还使用了比其他具体List类更多的内存(每个节点都有两个额外的指针,每个节点都是一个单独的包装器对象,带有额外的开销字节)。
      2010-03-23 00:46:34Z
    3. 这是这里最有用的答案之一。令人遗憾的是,许多程序员都无法理解(a)抽象数据类型与具体实现之间的区别,以及(b)在确定性能时常数因素和内存开销的现实重要性。
      2010-09-10 17:25:59Z
    4. - 1:这是一个相当模糊的视图。是的,ArrayList确实是一个非常通用的工具。但是,它有其局限性。有些情况会导致您遇到麻烦,您将不得不使用LinkedList。当然,它是一种非常专业的解决方案,并且,作为任何专用工具,在大多数情况下,它的性能优于多功能工具。但这并不意味着它“糟透了”或类似的东西,你只需要知道何时使用它。
      2011-08-08 13:43:14Z
    5. @ DavidTurner:他们确实存在,但我认为汤姆的观点是,如果你不得不问,你可能想要ArrayList。
      2013-01-18 05:07:51Z
    6. 醇>

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

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

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

        
    134
    2011-01-01 20:23:52Z
    1. 使用ArrayList的ensureCapacity()方法不会以编程方式管理列表大小吗?我的问题是为什么当这么多东西被存储在一堆脆弱的数据结构中时他们可能最好存储在一个缓存或数据库机制中吗?我前几天接受了一次采访,他们就ArrayList的邪恶起伏不定,但是我来到这里,我发现复杂性分析是全方位的更好!伟大的要点讨论,那么。谢谢!
      2012-10-30 05:33:47Z
    2. 一旦你获得了10GB堆的java应用程序,你可以在一个导致超时的Full GCs中锁定应用程序25秒实际上LinkedList你在完整的GC期间谋杀了垃圾收集器,它必须在每个节点上迭代过大的LinkedList并且缓存未命中。
      2014-12-17 20:15:47Z
    3. 那是......一个可怕的解决方案。当你只需要在arraylist上调用ensureCapacity()时,你基本上依赖于GC为你清理,这是非常昂贵的......
      2015-06-19 14:03:14Z
    4. @ Andreas:LinkedList 总是分配的内存是普通数组引用的五倍,因此暂时需要2.5次的ArrayList仍然消耗很多即使内存未被回收,内存也会减少。由于大数组分配绕过了Eden空间,它们对GC行为没有任何影响,除非内存确实不足,在这种情况下,LinkedList更早爆炸......
      2016-07-05 09:04:52Z
    5. @ Andreas另一个问题是如何分配内存。 LinkedList只需要一小段可用内存来分配下一个元素。 ArrayList将需要一个大的连续空闲空间块来分配调整大小的数组。如果堆碎片化,那么GC最终可能会重新排序整个堆,以释放合适的单个内存块。
      2016-11-01 23:12:45Z
    6. 醇>
     
    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适用于一次性多次写入或多次写入,但在前面或中间添加/删除时效果不佳。

        
    119
    2016-07-28 08:46:18Z
    1. 如果不考虑常数因素,就无法直接比较big-O值。对于小列表(并且大多数列表很小),ArrayList的O(N)比LinkedList的O(1)快。
      2010-09-10 17:23:15Z
    2. 我不关心小列表的性能,我的计算机除非它在循环中以某种方式使用。
      2011-08-18 16:35:34Z
    3. LinkedList无法真正插入到O(1)的中间。它必须遍历列表的一半才能找到插入点。
      2011-12-30 15:02:56Z
    4. LinkedList:插入中间O(1) - 错误!我发现即使插入LinkedList大小的1/10位置也比将元素插入ArrayList的1/10位置慢。更糟糕的是:收集的结束。插入到ArrayList的最后位置(不是最后一个位置)比在LinkedList
      的最后位置(不是最后一个位置)更快
      2012-05-13 14:29:12Z
    5. @ kachanov如果您有插入位置的迭代器,则插入LinkedList O(1) ,即ListIterator.add是据说O(1)LinkedList
      2013-08-18 08:13:07Z
    6. 醇>

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

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

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

        
    101
    2009-05-19 11:21:20Z
    1. 从Java 6开始,您可以使用ArrayDeque docs.oracle.com/javase/6/docs/API /JAVA /util的/ArrayDeque.html
      2011-12-30 15:01:32Z
    2. ArrayDequeLinkedList慢,除非所有操作都在同一端。当用作堆栈时它没关系,但是它没有成为一个好的队列。
      2015-04-30 02:12:27Z
    3. Untrue - 至少对于Oracle在jdk1.7.0_60和以下测试中的实现。我创建了一个测试,我循环了1000万次,我有一个1000万随机整数的Deque。在循环内部,我从中调出一个元素并提供一个常量元素。在我的计算机上,LinkedList比ArrayDeque慢10倍以上并且占用的内存更少。原因是,与ArrayList不同,ArrayDeque保留了一个指向数组头部的指针,这样在移除头部时就不必移动所有元素。
      2015-05-22 10:18:58Z
    4. 当用作堆栈时,ArrayDeque可能比Stack快,而当用作队列时,快于LinkedList
      2015-06-17 15:44:47Z
    5. 请注意,akhil_mittal的评论是ArrayDeque文档中的引用。
      2015-11-28 22:47:55Z
    6. 醇>

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

    Array vs ArrayList vs LinkedList vs Vector 更深入, 链接列表

        
    59
    2018-04-20 06:12:45Z

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

    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);
        }
    }
    
        
    52
    2018-04-20 06:23:23Z
    1. 确切地说,ArrayList不需要加倍。请先检查来源。
      2013-05-06 14:40:49Z
    2. 应该注意的是你的例子是有缺陷的...你要从以下字符串中删除:18 + [2,12]字节(“true0false”,“true500000false “),平均25个字节,这是中间元素的大小。众所周知,随着元素字节大小的增加,链表的表现会更好,随着列表大小的增加,连续的数组(列表)会做得更好。最重要的是,你在字符串上执行.equals() - 这不是一个廉价的操作。如果您改为使用整数,我认为会有所不同。
      2014-08-21 09:40:10Z
    3. - 这也可能就是为什么删除/包含的差别很小。
      2014-08-21 09:46:05Z
    4. “... 在大量应用程序中更糟糕”:这是一个误解。 LinkedList具有更多的内存开销,因为每个元素都有一个包含五个字段的节点对象。在许多系统上产生20个字节的开销。 ArrayList每个元素的平均内存开销是一个半字,这个字节为6个字节,最差情况下为8个字节。
      2015-09-15 09:53:40Z
    5. 我做了更好的基准测试这里有结果 - arraylist的追加端性能对你来说是人为的低,因为addAll给出了一个初始大小完全正确的存储阵列,所以第一个插入总是触发arraycopy。此外,这还包括预热周期,以便在收集数据之前进行JIT编译。
      2016-03-10 18:48:54Z
    6. 醇>

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

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

    LinkedList在添加和删除方面更快,但在获取方面更慢。简而言之,如果出现以下情况,应优先考虑LinkedList

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

      === ArrayList ===

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

    === LinkedList ===

    • 添加(E e)

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

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

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

        
    46
    2018-05-27 10:29:49Z
    1. “LinkedList比添加/删除更快”。错了,请查看上面的答案 stackoverflow.com/a/7507740/638670
      2013-11-05 10:00:00Z
    2. 醇>

    LinkedList的作者Joshua Bloch:

      

    有没有人真正使用LinkedList?我写了它,我从不使用它。

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

    我很抱歉答案不像其他答案那样提供信息,但我认为这将是最有趣和不言自明的。

        
    34
    2017-04-25 10:23:06Z
    1. 我来到这个帖子只是为了检查Joshua的推文是否被提及。它是:)
      2018-01-15 15:54:30Z
    2. 醇>

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

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

        
    33
    2018-04-20 06:14:16Z
    1. LinkedList对于添加元素并不便宜。向ArrayList添加一百万个元素几乎总是比将它们添加到LinkedList更快。实际代码中的大多数列表甚至都不是一百万个元素。
      2010-09-10 17:21:52Z
    2. 在任何给定的点上,您都知道将项目添加到LinkedList的成本。你没有的ArrayList(一般来说)。将单个项添加到包含一百万个项的ArrayList可能需要很长时间 - 这是一个O(n)操作加上存储的两倍,除非你预先分配空间。将项添加到LinkedList是O(1)。我的最后一句话就是。
      2010-09-10 23:03:04Z
    3. 将单个项目添加到ArrayList是O(1),无论它是100万还是10亿。将项添加到LinkedList也是O(1)。 “添加”意味着添加到结尾。
      2012-05-13 14:36:09Z
    4. 你必须以不同于我的方式阅读实现。根据我的经验,复制10亿个元素数组需要比复制100万个元素数组更长的时间。
      2012-05-14 05:57:35Z
    5. @ kachanov你必须误解达斯汀。除非你已经声明了一个包含10亿个项目的数组,否则你最终需要调整数组的大小,在这种情况下你需要将所有元素复制到一个新的更大的数组中,因此有时候你会得到O(N),但是有了链接列表,你将永远得到O(1)
      2013-03-18 21:51:39Z
    6. 醇>

    如果您的代码有add(0)remove(0),请使用LinkedList并使用更漂亮的addFirst()removeFirst()方法。否则,请使用ArrayList

    当然,番石榴 ImmutableList 是你最好的朋友。

        
    22
    2018-04-20 06:16:46Z
    1. 对于小型列表,ArrayList.add(0)仍然总是比LinkedList.addFirst()快。
      2010-09-10 17:20:32Z
    2. - 1。 ArrayDeque对于这种情况更好。
      2014-08-22 13:19:16Z
    3. @ Porculus我不断听到这个说法,对于小列表ArrayList.add(0)会更快,这个小的多少小? 10个元素,1000万,?
      2016-09-20 12:07:08Z
    4. @ garg10may small小于10.
      2016-09-21 14:53:12Z
    5. 醇>

    我知道这是一个老帖子,但我老实说不敢相信没人提到LinkedList实现了Deque。看看Deque(和Queue)中的方法;如果你想要公平的比较,尝试运行LinkedListArrayDeque并进行功能比较。

        
    21
    2018-04-20 06:29:50Z

    以下是ArrayListLinkedList以及CopyOnWrite-ArrayList中的Big-O表示法:

    的ArrayList 强>

     
    get                 O(1)
    add                 O(1)
    contains            O(n)
    next                O(1)
    remove              O(n)
    iterator.remove     O(n)
    

    链表强>

     
    get                 O(n)
    add                 O(1)
    contains            O(n)
    next                O(1)
    remove              O(1)
    iterator.remove     O(1)
    

    写入时复制-ArrayList的强>

     
    get                 O(1)
    add                 O(n)
    contains            O(n)
    next                O(1)
    remove              O(n)
    iterator.remove     O(n)
    

    基于这些,你必须决定选择什么。 :)

        
    19
    2018-04-20 06:29:10Z
    1. &gt;&gt;&gt;&gt; ArrayList add - &gt; O(1)&lt; - 不是真的。在某些情况下,ArrayList必须增长以添加一个元素
      2013-02-08 00:54:05Z
    2. LinkedList remove不是O(1),它需要搜索要删除的元素,因此最坏情况为O(n)和平均O(n /2) )
      2016-09-20 12:05:51Z
    3. 醇>

    让我们比较LinkedList和ArrayList w.r.t.以下参数:

    1。实施

      

    ArrayList 是列表界面的可调整大小的数组实现,而

         

    LinkedList 是列表界面的双向链表实现。


    2。性能

    • get(int index)或搜索操作

        

      ArrayList get(int index)操作以恒定时间运行,即O(1),而

           

      LinkedList get(int index)操作运行时间为O(n)。

      ArrayList 比LinkedList更快的原因是ArrayList使用基于索引的系统作为其元素,因为它在内部使用数组数据结构,

      LinkedList 不为其元素提供基于索引的访问,因为它从开头或结尾(以较近者为准)进行迭代,以检索指定元素索引处的节点。

    • insert()或add(Object)操作

        

      与Ar相比, LinkedList 中的插入速度通常很快rayList。在LinkedList中添加或插入是O(1)操作。

           

      ArrayList 中,如果数组是完整的,即最坏的情况,则需要额外调整数组大小和将元素复制到新数组的成本,这使得在ArrayList O中添加运算的运行时间( n),否则为O(1)。

    • remove(int)operation

      LinkedList中的删除操作通常与ArrayList相同,即O(n)。

        

      LinkedList 中,有两个重载的删除方法。一个是remove(),没有任何参数删除列表的头部并在恒定时间O(1)中运行。 LinkedList中另一个重载的remove方法是remove(int)或remove(Object),它删除作为参数传递的Object或int。此方法遍历LinkedList,直到找到Object并将其与原始列表取消链接。因此,此方法运行时为O(n)。

           

      ArrayList 中,remove(int)方法涉及将元素从旧数组复制到新更新的数组,因此其运行时为O(n)。


    3。反向迭代器

      

    LinkedList 可以使用descendingIterator()反向迭代,而

         

    ArrayList 中没有descendingIterator(),所以我们需要编写自己的代码来反向迭代ArrayList。


    4。初始容量

      

    如果构造函数没有重载,那么 ArrayList 会创建一个初始容量为10的空列表,而

         

    LinkedList 只构造没有任何初始容量的空列表。


    5。内存开销

      

    LinkedList 中的内存开销与ArrayList相比更多,因为LinkedList中的节点需要维护下一个节点和上一个节点的地址。而

         

    ArrayList 中,每个索引只保存实际对象(数据)。


    来源一>

        
    15
    2018-07-24 15:49:31Z
    由于采用了现代计算机架构,ArrayList对于几乎任何可能的用例都会显着提高效率,因此应该避免使用LinkedList,除非是一些非常独特和极端的情况,否则应该避免使用add(E element). TL; DR >

    理论上,LinkedList对于LinkedList具有O(1)

    在列表中间添加元素应该非常有效。

    实践是非常不同的,因为LinkedList是缓存敌对数据结构。从性能POV - 很少有ArrayList表现比 Cache-friendly LinkedList更好的表现。

    以下是在随机位置插入元素的基准测试结果。正如您所看到的 - 数组列表更高效,尽管理论上列表中间的每个插入都需要“移动” n 后面的数组元素(值越低越好):

    使用更新一代的硬件(更大,更高效的缓存) - 结果更具决定性:

    LinkedList需要更多时间来完成相同的工作。 source 源代码

    这有两个主要原因:

    1. 主要 - ArrayList的节点随机分散在内存中。 RAM(“随机存取存储器”)并不是真正随机的,需要将存储器块提取到缓存。这种操作需要时间,并且当这种提取经常发生时 - 高速缓存中的存储页面需要一直被替换 - &gt;缓存未命中 - &gt;缓存效率不高。  LinkedList个元素存储在连续内存中 - 这正是现代CPU架构所优化的内容。

    2. 辅助 ArrayList需要保持后退/前进指针,这意味着每个内存消耗的3倍与Int比较存储。

    3. 醇>

      DynamicIntArray ,顺便说一句,是一个自定义的ArrayList实现,持有

      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
      
      (原始类型)而不是对象 - 因此所有数据都是相邻存储的 - 因此效率更高。

      要记住的关键要素是获取内存块的成本比访问单个内存单元的成本更重要。这就是为什么读取器1MB的顺序存储器比从不同存储器块读取这些数据量快x400倍的原因:

       LinkedList

      来源:每个程序员都应该知道的延迟数字

      为了更清楚地说明这一点,请检查在列表开头添加元素的基准。这是一个用例,在理论上,ArrayList应该真正发光,而ArrayList应该会出现糟糕甚至更糟糕的结果:

      注意:这是C ++ Std lib的基准测试,但我之前的经验表明C ++和Java结果非常相似。 源代码

      复制顺序大量内存是现代CPU优化的操作 - 改变理论并实际制作Vector/ArrayList更高效


      致谢:此处发布的所有基准均由KjellHedström创建。可以在他的博客上找到更多数据

          
    15
    2018-10-19 03:06:19Z
    1. 我不会将队列称为唯一或极端!在LinkedList而不是ArrayList上实现fifo队列要容易得多。它实际上是ArrayList上的一个噩梦,因为你必须跟踪自己的开始,停止并自己重新分配,你不妨使用数组,但链接列表是一个fifo。我不确定Java的实现,但LinkedList可以为队列和出队操作做O(1)(需要一个特殊的指向remove元素的指针,我假设java有,但我没有仔细检查过。)
      2018-12-28 18:26:46Z
    2. 醇>

    除了上面的其他好的参数之外,你应该注意到RandomAccess实现了LinkedList接口,而Queue实现了ArrayList

    所以,不知何故,他们解决了稍微不同的问题,效率和行为的差异(参见他们的方法列表)。

        
    13
    2018-04-20 06:15:53Z

    请参阅 Java教程 - 列表实现

        
    9
    2011-09-05 06:33:52Z
    1. 你好@chharvey,Link只有答案得到6个Upvotes?请添加一些可以支持链接的点。如果oracle更改了链接,那该怎么办?
      2017-11-14 06:08:22Z
    2. 醇>

    数组列表本质上是一个数组,其中包含添加项等的方法(您应该使用通用列表)。它是可以通过索引器访问的项目集合(例如[0])。它意味着从一个项目到下一个项目的进展。

    链接列表指定从一个项目到下一个项目的进展(项目a - &gt;项目b)。您可以使用数组列表获得相同的效果,但链接列表绝对说什么项目应该遵循前一个项目。

        
    8
    2010-04-20 15:32:01Z

    这取决于你将在列表上做些什么操作。

    |---------------------|---------------------|--------------------|------------|
    |      Operation      |     ArrayList       |     LinkedList     |   Winner   |
    |---------------------|---------------------|--------------------|------------|
    |     get(index)      |       O(1)          |         O(n)       | ArrayList  |
    |                     |                     |  n/4 steps in avg  |            |
    |---------------------|---------------------|--------------------|------------|
    |      add(E)         |       O(1)          |         O(1)       | LinkedList |
    |                     |---------------------|--------------------|            |
    |                     | O(n) in worst case  |                    |            |
    |---------------------|---------------------|--------------------|------------|
    |    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
    |                     |     n/2 steps       |      n/4 steps     |            |
    |                     |---------------------|--------------------|            |
    |                     |                     |  O(1) if index = 0 |            |
    |---------------------|---------------------|--------------------|------------|
    |  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
    |                     |---------------------|--------------------|            |
    |                     |     n/2 steps       |      n/4 steps     |            |
    |---------------------|---------------------|--------------------|------------|
    |  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
    |  ListIterator.add() |                     |                    |            |
    |---------------------|---------------------|--------------------|------------|
    
    
    |--------------------------------------|-----------------------------------|
    |              ArrayList               |            LinkedList             |
    |--------------------------------------|-----------------------------------|
    |     Allows fast read access          |   Retrieving element takes O(n)   |
    |--------------------------------------|-----------------------------------|
    |   Adding an element require shifting | o(1) [but traversing takes time]  |
    |       all the later elements         |                                   |
    |--------------------------------------|-----------------------------------|
    |   To add more elements than capacity |
    |    new array need to be allocated    |
    |--------------------------------------|
    
    访问索引值的速度更快。插入或删除对象时要糟糕得多。

    要了解更多信息,请阅读任何讨论数组和链接列表之间差异的文章。

        
    8
    2018-04-20 06:14:59Z
    1. 要了解更多不要阅读,只需编写代码即可。你会发现ArrayList实现比插入和删除中的LinkedList更快。
      2012-05-18 02:53:36Z
    2. 醇>

    基于我在特定列表上执行的操作的时间复杂性,我通常使用一个。

     LinkedList     
    8
    2019-02-18 07:08:01Z
    1. ArrayDeque向数组平衡了一些东西,因为插入/删除前/后都是O(1)链接列表仍然赢得的唯一东西是添加/删除遍历(迭代器操作)。
      2019-02-21 18:24:59Z
    2. 醇>

    链表的一个重要特征(我在另一个答案中没有读到)是两个列表的串联。对于数组,这是O(n)(一些重新分配的开销)和一个链表,这只是O(1)或O(2); - )

    重要:对于Java next,这不是真的!请参阅 Java中的链表是否有快速连接方法?

        
    7
    2017-05-23 12:02:46Z
    1. 那是怎么回事?对于链表数据结构而言,这可能是真的,但不是Java LinkList对象。您不能只将addAll()从一个列表指向第二个列表中的第一个节点。唯一的方法是使用add()顺序添加元素,尽管它比循环更好并为每个元素调用ArrayList。要在O(1)中快速完成此操作,您需要一个合成类(如org.apache.commons.collections.collection.CompositeCollection),但这适用于任何类型的List /Collection。
      2010-03-23 00:42:31Z
    2. 是的,是的。我相应地编辑了答案。但看到这个答案是如何用LinkedList做的: stackoverflow.com/questions/2494031 /...
      2010-03-23 12:47:46Z
    3. 醇>

    我已阅读过这些回复,但有一种情况是我总是在我想要分享的ArrayList上使用LinkedList来听取意见:

    每当我有一个返回从DB获取的数据列表的方法时,我总是使用LinkedList。

    我的理由是,因为我无法准确知道我得到了多少结果,所以不会浪费内存(如ArrayList中的差异)能力和实际的元素数量),并没有浪费时间来试图复制容量。

    就ArrayList而言,我同意至少你应该始终使用具有初始容量的构造函数,以尽可能减少数组的重复。

        
    6
    2011-10-03 23:23:00Z

    ArrayList和LinkedList各有利弊。

    与使用指向下一个节点的指针的LinkedList相比,ArrayList使用连续的内存地址。因此,当您想要查找ArrayList中的元素比使用LinkedList进行n次迭代更快。

    另一方面,LinkedList中的插入和删除更容易,因为您只需要更改指针,而ArrayList意味着使用shift操作进行任何插入或删除。

    如果您的应用中有频繁的检索操作,请使用ArrayList。如果频繁插入和删除,请使用LinkedList。

        
    6
    2017-10-21 01:58:43Z
    LinkedListList interface都实现了Search:,他们的方法和结果几乎完全相同。然而,它们之间的差异很小,这使得一个优于另一个,具体取决于要求。

    ArrayList与LinkedList

    1)与ArrayList搜索操作相比,LinkedList get(int index)搜索操作非常快。 ArrayList中的O(1)表示LinkedList,而O(n)表现为Reason:

    ArrayList LinkedList为其元素维护基于索引的系统,因为它隐式使用数组数据结构,这使得搜索列表中的元素更快。另一方面,Deletion:实现了双向链表,需要遍历所有元素来搜索元素。

    2)LinkedList O(1)删除操作提供ArrayList性能而O(n)提供可变性能:最坏情况下O(1)(删除第一个元素时)和最佳情况下Inserts Performance:(删除最后一个元素时)。

      

    结论:与之相比,LinkedList元素删除速度更快   ArrayList中。

    原因:LinkedList的每个元素都维护着两个指针(地址),这些指针指向列表中的两个邻居元素。因此,移除仅需要改变将要移除的节点的两个相邻节点(元素)中的指针位置。在In ArrayList中,需要移动所有元素以填充由删除元素创建的空间。

    3)LinkedList O(1) add方法给出ArrayList性能,而O(n)给出Memory Overhead:最坏情况。原因与删除说明相同。

    4)ArrayList LinkedList维护索引和元素数据,而iterator维护元素数据和两个邻居节点指针

      

    因此,LinkedList中的内存消耗相对较高。

    这些类之间几乎没有相似之处,如下所示:

    • ArrayList和LinkedList都是List接口的实现。
    • 它们都维护元素的插入顺序,这意味着在显示ArrayList和LinkedList元素时,结果集将具有将元素插入List的相同顺序。
    • 这两个类都是非同步的,可以使用Collections.synchronizedList方法显式同步。
    • 这些类返回的listIteratorfail-fastiterator’s(如果在创建迭代器之后的任何时候对列表进行结构修改,除了通过throw自己的删除或添加方法之外,迭代器将为ConcurrentModificationException a (O(1)))。 /LI>

    何时使用LinkedList以及何时使用ArrayList?

    • 如上所述,与LinkedList相比,插入和移除操作在ArrayList(O(n))中提供了良好的性能get method
        

      因此,如果在应用程序中需要频繁添加和删除,那么LinkedList是最佳选择。

    • 搜索(Arraylist (O(1)))操作在LinkedList (O(n))中快速但在arraylist.get()中没有
        

      所以如果添加和删除操作少,搜索操作要求更多,那么ArrayList将是您最好的选择。

    5
    2016-11-02 09:00:23Z

    ArrayList中的get(i)操作比LinkedList快,因为:
    ArrayList: List接口的可调整大小的数组实现
    LinkedList: Doubly List和Deque接口的链接列表实现

    索引到列表中的操作将从开头或结尾遍历列表,以较接近指定索引为准。

        
    5
    2016-11-09 10:48:34Z

    1)基础数据结构

    ArrayList和LinkedList之间的第一个区别在于ArrayList由Array支持,而LinkedList由LinkedList支持。这将导致性能进一步差异。

    2)LinkedList实现了Deque

    ArrayList和LinkedList之间的另一个区别是,除了List接口之外,LinkedList还实现了Deque接口,它为add()和poll()以及其他几个Deque函数提供先进先出操作。 3)在ArrayList中添加元素在ArrayList中添加元素是O(1)操作,如果它不触发Array的重新大小,在这种情况下它变为O(log(n)),另一方面,添加元素LinkedList是O(1)操作,因为它不需要任何导航。

    4)从某个位置删除元素

    为了从特定索引中删除元素,例如通过调用remove(index),ArrayList执行复制操作,使其接近O(n),而LinkedList需要遍历到该点,这也使其成为O(n /2),因为它可以基于接近度从任一方向遍历

    5)迭代ArrayList或LinkedList

    迭代是LinkedList和ArrayList的O(n)操作,其中n是元素的数量。

    6)从某个位置检索元素

    get(index)操作在ArrayList中为O(1),而在LinkedList中为O(n /2),因为它需要遍历该条目。虽然,在Big O表示法O(n /2)只是O(n),因为我们忽略那里的常量。

    7)内存

    LinkedList使用包装器对象Entry,它是一个静态嵌套类,用于存储数据和下一个和上一个节点,而ArrayList只是将数据存储在Array中。

    因此,在ArrayList的情况下,内存需求似乎少于LinkedList,除非Array在将内容从一个Array复制到另一个Array时执行重新大小操作。

    如果Array足够大,那么可能会占用大量内存并触发垃圾收集,这会缩短响应时间。

    从ArrayList与LinkedList之间的所有上述差异来看,几乎在所有情况下看起来ArrayList是比LinkedList更好的选择,除非你做一个频繁的add()操作而不是remove()或get()。

    修改链接列表比使用ArrayList更容易,特别是如果要从开始或结束添加或删除元素,因为链接列表在内部保留对这些位置的引用,并且可以在O(1)时间内访问它们。

    换句话说,您不需要遍历链表以到达要添加元素的位置,在这种情况下,添加变为O(n)操作。例如,在链接列表的中间插入或删除元素。

    在我看来,对于Java中的大多数实际用途,使用LinkedList而不是LinkedList。

        
    5
    2018-07-24 16:01:05Z
    1. 我认为这是整个小组最好的答案。它准确而且信息丰富。我建议改变最后一行 - 最后添加“除了队列”,这是一个非常重要的结构,对链接列表根本没有意义。
      2018-12-28 18:33:04Z
    2. 醇>

    对于ArrayLists和LinkedLists,remove()和insert()都具有O(n)的运行时效率。然而,线性处理时间背后的原因有两个非常不同的原因:

    在ArrayList中,您可以访问O(1)中的元素,但实际上删除或插入某些内容会使其成为O(n),因为需要更改以下所有元素。

    在LinkedList中,实际获取所需元素需要O(n),因为我们必须从最开始直到达到所需的索引。实际上删除或插入是不变的,因为我们只需要为remove()更改1个引用,为insert()更改2个引用。

    两者中哪一个更快插入和移除取决于它发生的位置。如果我们离开头更近,LinkedList会更快,因为我们必须经历相对较少的元素。如果我们更接近结束,ArrayList将更快,因为我们在恒定时间到达那里并且只需要更改其后的少数剩余元素。当精确地在中间完成时,LinkedList将更快,因为遍历n个元素比移动n个值更快。

    Bonus:虽然没有办法为ArrayList创建这两个方法O(1),但实际上有一种方法可以在LinkedLists中执行此操作。假设我们想要通过整个List删除和插入元素。通常,您将从一开始就使用LinkedList开始每个元素,我们也可以使用Iterator“保存”我们正在处理的当前元素。在Iterator的帮助下,当在LinkedList中工作时,我们获得了remove()和insert()的O(1)效率。使它成为唯一的性能优势我知道LinkedList总是比ArrayList更好。

        
    2
    2018-07-24 16:14:23Z

    ArrayList扩展了AbstractList并实现了List接口。 ArrayList是动态数组。
    可以说它基本上是为了克服数组的缺点而创建的

    LinkedList类扩展了AbstractSequentialList并实现了List,Deque和Queue接口。
    性能
    linkedlist.get()是O(1)而arraylist.add()是O(n)
    linkedlist.add()是O(1)而arraylist.contains()是0(1)
    linkedlist.contains()是O(n)而arraylist.next()是O( n)
    linkedlist.next()是O(1)而arraylist.remove()是O(1)
    linkedlist.remove()是O(n)而iterator.remove()是O(1)
    在arraylist
    iterator.remove()是O(n)
    而在链表中
    LinkedList是O(1)

        
    1
    2018-02-20 21:51:19Z

    我在这里看到的其中一项测试只进行了一次测试。但我注意到你需要多次运行这些测试,最终它们的时间会收敛。基本上JVM需要预热。对于我的特定用例,我需要添加/删除项目到最后增加到约500项。在我的测试中,LinkedList的出现速度更快,链接的ArrayList大约有50,000个NS,而

    public static void main(String[] args) {
        List<Long> times = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            times.add(doIt());
        }
        System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
    }
    
    static long doIt() {
        long start = System.nanoTime();
        List<Object> list = new LinkedList<>();
        //uncomment line below to test with ArrayList
        //list = new ArrayList<>();
        for (int i = 0; i < 500; i++) {
            list.add(i);
        }
    
        Iterator it = list.iterator();
        while (it.hasNext()) {
            it.next();
            it.remove();
        }
        long end = System.nanoTime();
        long diff = end - start;
        //uncomment to see the JVM warmup and get faster for the first few iterations
        //System.out.println(diff)
        return diff;
    }
    
    大约有90,000个NS ...给予或接受。请参阅下面的代码。       
    1
    2018-08-04 18:52:06Z
来源放置 这里