何时在 Java 中通过 ArrayList 使用 LinkedList?

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

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

我将接口用作可移植性的类型名称,这样当我问诸如此类的问题时,便可以重新编写代码。

什么时候应该在ArrayList上使用LinkedList ,反之亦然?

答案

摘要 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步),但是当index = 0index = 0 O(1) -- LinkedList<E>主要优点
  • remove(int index)O(n) (平均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) ,但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) index = 0

另一方面, ArrayList<E>允许快速随机读取访问,因此您可以在恒定时间内获取任何元素。但是,从末端开始的任何地方添加或删除,都需要将后面的所有元素移开,以形成开口或填补空白。同样,如果添加的元素多于基础数组的容量,则会分配一个新数组(大小的 1.5 倍),并将旧数组复制到新数组,因此添加到ArrayListO(n)最坏的情况,但平均保持不变。

因此,根据您打算执行的操作,您应该相应地选择实现。遍历任何一种 List 实际上都是很便宜的。 (从技术上讲,遍历ArrayList的速度更快,但是除非您执行的是真正对性能敏感的操作,否则您不必担心这一点 - 它们都是常量。)

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

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

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

ArrayList的默认初始容量很小(Java 1.4-1.8 中为 10)。但是由于底层实现是一个数组,因此如果添加很多元素,则必须调整数组的大小。为了避免在确定要添加很多元素时调整大小的高成本,请使用较高的初始容量构造ArrayList

到目前为止,除了人们普遍认为LinkedListArrayList “更多” 外,似乎没有人解决这些列表的内存占用问题,因此我进行了一些数字运算来演示这两个列表占用了 N 个空引用的确切数量。 。

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

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

注意 2 :( 感谢 BeeOnRope)由于 CompressedOops 现在是 JDK6 或更高版本的默认值,因此下面的 64 位计算机的值将基本上与 32 位计算机匹配,除非您明确地将其关闭。


LinkedList和ArrayList的图元素数x字节


结果清楚地表明, LinkedListArrayList大得多,尤其是元素数量很高时。如果内存是一个因素,请避免使用LinkedLists

我遵循的公式如下,如果我做错了什么,请告诉我,我将对其进行修复。对于 32 或 64 位系统,“b” 为 4 或 8,而 “n” 为元素数。请注意,mod 的原因是因为 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)

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

为什么LinkedList很烂:

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

作为从事大型 SOA Web 服务的运营性能工程研究大约十年的人,我宁愿使用 LinkedList 而不是 ArrayList。尽管 LinkedList 的稳态吞吐量较差,因此可能导致购买更多硬件 - ArrayList 的行为在压力下可能导致集群中的应用程序几乎同步地扩展其阵列,而大型阵列可能导致缺乏响应能力在应用程序中,并且在压力下中断,这是灾难性的行为。

同样,您可以从默认吞吐量的持久性垃圾收集器中获得更好的应用程序吞吐量,但是一旦获得具有 10GB 堆的 Java 应用程序,您就可以在 Full GC 期间将应用程序锁定 25 秒,这会导致 SOA 应用程序超时和失败并在您的 SLA 频繁发生时将其删除。即使 CMS 收集器占用更多资源且未达到相同的原始吞吐量,它也是一个更好的选择,因为它具有更可预测的延迟和更小的延迟。

如果性能仅是吞吐量,而您可以忽略延迟,则 ArrayList 仅是性能的更好选择。根据我的工作经验,我不能忽略最坏情况下的延迟。

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)

算法:大哦符号

ArrayLists 对于一次写入多次读取或追加程序很有用,但不利于从前端或中间进行添加 / 删除。

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

从性能角度来看,LinkedList 几乎总是错误的选择。有一些非常特定的算法需要使用 LinkedList,但是这种算法非常非常少见,该算法通常具体取决于 LinkedList 在列表中导航后相对快速地在列表中间插入和删除元素的能力。与 ListIterator。

在一种常见的使用情况下,LinkedList 的性能优于 ArrayList:队列的性能。但是,如果您的目标是性能,那么您还应该考虑使用 ArrayBlockingQueue(如果可以提前确定队列大小的上限,并且可以负担所有内存的分配),而不是 LinkedList,或者使用CircularArrayList 实现 。 (是的,它是从 2001 年开始的,因此您需要对其进行泛化,但是我得到的性能比与最近的 JVM 中本文中引用的性能比相当)

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

Array vs ArrayList vs LinkedList vs Vector以及Linked List 的深度更深。

正确或不正确:请在本地执行测试,然后自己决定!

LinkedList Edit / Remove 比ArrayList更快。

Array支持的ArrayList需要大一倍,在大容量应用程序中更糟。

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


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

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

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

LinkedList添加和删除速度更快,但获取速度较慢。简而言之,如果满足以下条件,应首选LinkedList

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

=== ArrayList ===

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

=== LinkedList ===

  • 加(E e)

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

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

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

在此处输入图片说明

Joshua Bloch,LinkedList 的作者:

有人实际使用 LinkedList 吗?我写了它,但从未使用过。

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

对于该答案没有其他答案那么有用,我感到抱歉,但我认为这将是最有趣且最能说明问题的。