提问



我一直只是一个人使用:


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


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


应该LinkedList何时使用ArrayList,反之亦然?[174] [175]

最佳参考


摘要 ArrayListArrayDeque在多更多用例中优于LinkedList。不确定 —刚开始ArrayList





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


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


对于LinkedList<E> [176]



  • get(int index)是 O(n)(平均 n/4 步骤)

  • add(E element)是 O(1)

  • add(int index, E element)是 O(n)(平均 n/4 步),
    但是当index = 0< --- LinkedList<E>
  • 的主要好处时, O(1)
  • remove(int index)是 O(n)(平均 n/4 步骤)

  • Iterator.remove()是 O(1)。 < --- LinkedList<E>
  • 的主要好处
  • ListIterator.add(E element) O(1)这是LinkedList<E>
  • 的主要好处之一


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


对于ArrayList<E> [177]



  • get(int index)是 O(1)< --- 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) for ArrayList。注意ArrayDeque可能是LinkedList的一个很好的替代,用于添加和删除头部,但它不是List


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


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

其它参考1


到目前为止,除了LinkedListArrayList更多的普遍共识之外,没有人似乎已经解决了这些列表中每个列表的内存占用,所以我做了一些数字运算以准确地证明了多少两个列表都占用N个空引用。


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


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


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











结果清楚地表明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)

其它参考2


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


为什么LinkedList糟透了:



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

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

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

  • 获得良好的表现很棘手。

  • 即使大O的表现与ArrayList相同,但无论如何它可能会明显变慢。

  • 在源代码中看到LinkedList很不利,因为它可能是错误的选择。


其它参考3


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


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


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

其它参考4


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表示法[178]


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

其它参考5


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


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


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

其它参考6


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


Array vs ArrayList vs LinkedList vs Vector更深入,也是如此
关联名单。[180] [181]

其它参考7


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


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);
    }
}

其它参考8


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


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


LinkedList添加和删除速度更快,但获取速度更慢。简而言之,如果符合以下条件,LinkedList应该是首选:



  1. 没有大量随机访问元素

  2. 有大量的添加/删除操作



=== ArrayList ===



  • 添加(E e)


    • 在ArrayList的末尾添加

    • 需要调整内存大小。

    • O(n)最差,O(1)摊销


  • add(int index,E element)


    • 添加到特定索引位置

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

    • O(n)的


  • 删除(int索引)


    • 删除指定的元素

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

    • O(n)的


  • 删除(对象o)


    • 从此列表中删除指定元素的第一个匹配项

    • 首先需要搜索元素,然后移动&可能的内存调整成本

    • 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是第一种类型,即在列表的末尾添加一个元素并删除列表中指定位置的元素。): [182]




其它参考9


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


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

其它参考10


1)搜索:与LinkedList搜索操作相比,ArrayList搜索操作非常快。 ArrayList中的get(int index)给出O(1)的性能,而LinkedList性能为O(n)。


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


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


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


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


3)插入性能: LinkedList add方法提供O(1)性能,而ArrayList在最坏情况下给出O(n)。原因与删除时解释的相同。


4)内存开销: ArrayList维护索引和元素数据,而LinkedList维护元素数据和相邻节点的两个指针,因此LinkedList中的内存消耗相对较高。


这些类之间存在几个相似之处,如下所示:


ArrayList和LinkedList都是List接口的实现。
它们都维护元素的插入顺序,这意味着在显示ArrayList和LinkedList元素时,结果集将具有将元素插入List的相同顺序。
这两个类都是非同步的,可以使用Collections.synchronizedList方法显式同步。
这些类返回的iterator和listIterator是快速失​​败的(如果在创建迭代器之后的任何时候对列表进行结构修改,除了通过迭代器自己的remove或add方法之外,迭代器将抛出ConcurrentModificationException)。


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


1)如上所述,与ArrayList(O(n))相比,insertList和remove操作在LinkedList中提供了良好的性能(O(1))。因此,如果在应用程序中需要频繁添加和删除,则LinkedList是最佳选择。


2)搜索(get方法)操作在ArrayList(O(1))中快速但在LinkedList(O(n))中没有,因此如果添加和删除操作较少且搜索操作要求较多,则ArrayList将是您最好的选择。

其它参考11


LinkedList的作者Joshua Bloch:



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



链接:https://twitter.com/joshbloch/status/583813919019573248 [183]​​]]


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

其它参考12


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

其它参考13


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


当然,番石榴的ImmutableList是你最好的朋友。[184] [185]

其它参考14


这是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)


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

其它参考15


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


1。实施




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

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






2。性能




  • get(int index)或搜索操作




       ArrayList get(int index)操作在恒定时间内运行,即O(1)while

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



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


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

  • insert()或add(Object)operation




      与ArrayList相比, LinkedList 中的插入通常很快。在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()while反向迭代

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






4。初始容量




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

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






5。内存开销




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

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




[186]

其它参考16


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


因此,他们以某种方式解决了稍微不同的问题,效率和行为的差异(参见他们的方法列表)。

其它参考17


请参阅Java教程 - 列表实现。[187]

其它参考18


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

其它参考19

)。它意味着从一个项目到下一个项目的进展。


链表指定从一个项目到下一个项目的进度(项目a - >项目b)。您可以使用数组列表获得相同的效果,但链接列表绝对说明应该跟随前一个项目。

其它参考20


这取决于您将在列表上执行哪些操作。


ArrayList访问索引值的速度更快。插入或删除对象时要糟糕得多。


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

其它参考21


我已经阅读了回复,但有一种情况我总是在ArrayList上使用LinkedList,我想分享以听取意见:


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


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


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

其它参考22


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


重要:对于Java来说LinkedList这不是真的!请参阅Java中的链表有快速连接方法吗?

其它参考23


ArrayList中的操作get(i)比LinkedList快,因为:

ArrayList: List接口的可调整大小的数组实现

LinkedList: List和Deque接口的双链表实现


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

其它参考24


ArrayListLinkedList都实现List interface,它们的方法和结果几乎相同。然而,它们之间几乎没有差别,这取决于要求,使一个优于另一个。


ArrayList与LinkedList



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


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


2)Deletion: LinkedList删除操作给出O(1)性能,而ArrayList给出可变性能:O(n)在最坏的情况下(同时删除第一个元素)和O(1)]]在最好的情况下(删除最后一个元素)。



  结论:与之相比,LinkedList元素删除更快
  数组列表。



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


3)Inserts Performance: LinkedList add方法给出O(1)性能,而ArrayList给出O(n)在最坏的情况下。原因与删除时解释的相同。


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



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



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




  • ArrayList和LinkedList都是List接口的实现。

  • 它们都维护元素的插入顺序,这意味着在显示ArrayList和LinkedList元素时,结果集将具有将元素插入List中的相同顺序。

  • 这两个类都是非同步的,可以使用Collections.synchronizedList方法显式同步。

  • 这些类返回的iteratorlistIteratorfail-fast(如果在创建迭代器之后的任何时候对列表进行结构修改,除了通过iterator’s之外的任何方式)]]拥有删除或添加方法,迭代器将throw a ConcurrentModificationException。。



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




  • 如上所述,与LinkedList相比,插入和移除操作在LinkedList中表现出良好的性能(O(1))


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


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


      因此,如果添加和删除操作较少以及搜索操作要求较多,则ArrayList将是您最好的选择。



其它参考25


ArrayList和LinkedList各有利弊。


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


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


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

其它参考26


1)基础数据结构


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


2)LinkedList实现了Deque


ArrayList和LinkedList之间的另一个区别是,除了List接口之外,LinkedList还实现了Deque接口,它为add()和poll()以及其他几个Deque函数提供先进先出操作。 3)在ArrayList中添加元素ArrayList中的添加元素是O(1)操作,如果它不触发数组的重新大小,在这种情况下它变为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。

其它参考27


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


LinkedList类扩展了AbstractSequentialList并实现了List,Deque和Queue接口。
结果性能结果
arraylist.get()是O(1)而linkedlist.get()是O(n)

arraylist.add()是O(1),linkedlist.add()是0(1)

arraylist.contains()是O(n),linkedlist.contains()是O(n)

arraylist.next()是O(1),linkedlist.next()是O(1)

arraylist.remove()是O(n)而linkedlist.remove()是O(1)

在arraylist中,iterator.remove()是O(n)
而在链表中,iterator.remove()是O(1)

其它参考28


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


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


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


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


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

其它参考29


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

其它参考30


我应该什么时候使用LinkedList?大多数使用堆栈时,或使用缓冲区时。
我什么时候应该ArrayList?只有在使用索引时,否则您可以将HashTable与链表一起使用,然后您将获得:


哈希表+链表




  • 按键 O(1),
  • 进行访问
  • 按键 O(1),
  • 插入
  • 按键 O(1)
  • 删除
  • 使用版本控制时有一个用O(1)实现RemoveAll/SetAll的技巧



这似乎是一个很好的解决方案,在大多数情况下,它应该知道:
HashTable占用了大量的磁盘空间,因此当您需要管理1,000,000个元素列表时,它可能会变得非常重要。这可能发生在服务器实现中,在客户端很少发生这种情况。


另外看看红黑树[189]



  • 随机访问日志(n),

  • 插入日志(n),

  • 删除日志(n)