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

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

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

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


当前回答

我知道这是一篇老帖子,但我真的不敢相信没有人提到LinkedList实现了Deque。只需查看Deque(和Queue)中的方法;如果您希望进行公平的比较,请尝试对ArrayDeque运行LinkedList,并进行功能比较。

其他回答

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

LinkedList在性能方面几乎总是错误的选择。有一些非常具体的算法需要LinkedList,但这些算法非常非常罕见,并且该算法通常具体取决于LinkedLists在使用ListIterator导航到列表中间后相对快速地插入和删除元素的能力。

有一个常见的用例LinkedList优于ArrayList:队列。但是,如果您的目标是性能,那么您也应该考虑使用ArrayBlockingQueue(如果您可以提前确定队列大小的上限,并且能够提前分配所有内存),而不是LinkedList,或者使用CircularArray实现。(是的,它来自2001年,因此您需要对其进行一般化,但我得到的性能比与最近一篇JVM文章中引用的性能比相当)

ArrayList和LinkedList都实现了List接口,它们的方法和结果几乎相同。然而,它们之间几乎没有区别,这取决于需求,使一个优于另一个。

阵列列表与链接列表

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

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

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

结论:LinkedList元素删除速度比阵列列表。

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

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

4) 内存开销:ArrayList维护索引和元素数据,而LinkedList维护相邻节点的元素数据和两个指针

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

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

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

何时使用LinkedList,何时使用ArrayList?

如上所述,与ArrayList(O(n))相比,插入和删除操作在LinkedList中提供了良好的性能(O(1))。因此,若应用程序中需要频繁添加和删除,则LinkedList是最佳选择。搜索(get方法)操作在Arraylist(O(1))中很快,但在LinkedList(O(n))中不快因此,如果添加和删除操作更少,搜索操作需求更多,ArrayList将是您的最佳选择。

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

LinkedList中的编辑/删除速度比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实现了RandomAccess接口,而LinkedList实现了Queue。

因此,他们解决的问题略有不同,效率和行为有所不同(见他们的方法列表)。

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

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

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

插入和删除这两项中的哪一项更快取决于发生的位置。如果我们更接近开始,LinkedList将更快,因为我们必须经过相对较少的元素。如果我们接近末尾,ArrayList将更快,因为我们在恒定的时间内到达那里,只需更改紧随其后的几个剩余元素。如果正好在中间完成,LinkedList将更快速,因为遍历n个元素比移动n个值更快。

好处:虽然无法为ArrayList创建这两个方法O(1),但实际上在LinkedList中有一种方法可以做到这一点。假设我们想在整个列表中删除和插入元素。通常,您可以使用LinkedList从头开始每个元素,我们也可以使用迭代器“保存”当前正在处理的元素。在迭代器的帮助下,当在LinkedList中工作时,remove()和insert()的效率为O(1)。使其成为我所知的唯一性能优势,LinkedList总是优于ArrayList。