问题 何时使用LinkedList而不是ArrayList？

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

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

注意： 显示的尺寸为 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)

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

为什么 LinkedList 吮吸：

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

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

类似地，您可以从默认吞吐量终身垃圾收集器中获得更好的应用程序吞吐量，但是一旦获得具有10GB堆的Java应用程序，您可以在完整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)

算法：Big-Oh表示法

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

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

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

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

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

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

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

编辑/删除速度更快 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);
    }
}

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 是第一种类型，即在列表的末尾添加一个元素，并删除列表中指定位置的元素。）：

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

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