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

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

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

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


当前回答

让我们将LinkedList和ArrayList与以下参数进行比较:

1.实施

ArrayList是列表接口的可调整大小的数组实现,而LinkedList是列表接口的双重链接列表实现。


2.性能

get(int索引)或搜索操作ArrayList get(int索引)操作在恒定时间内运行,即O(1)而LinkedList get(int索引)操作运行时间为O(n)。ArrayList比LinkedList更快的原因是ArrayList对其元素使用基于索引的系统,LinkedList不为其元素提供基于索引的访问,因为它从开始或结束(以较近者为准)迭代以检索指定元素索引处的节点。insert()或add(Object)操作与ArrayList相比,LinkedList中的插入通常很快。在LinkedList中,添加或插入是O(1)操作。在ArrayList中,如果数组已满(即最坏情况),则调整数组大小并将元素复制到新数组会产生额外的成本,这使得ArrayList的加法运算运行时为O(n),否则为O(1)。删除(int)操作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.内存开销

与ArrayList相比,LinkedList中的内存开销更大,因为LinkedList的节点需要维护下一个和上一个节点的地址。虽然在ArrayList中,每个索引仅保存实际对象(数据)。


来源

其他回答

我已经阅读了答案,但有一种情况是,我总是使用LinkedList而不是ArrayList,我想分享它来听取意见:

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

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

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

Joshua Bloch,LinkedList的作者:

有人真的使用LinkedList吗?我写的,我从来没有用过。

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

很抱歉,我的答案没有其他答案那样信息丰富,但我认为这是最不言自明的答案。

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

与LinkedList相比,Summary ArrayList和ArrayDeque在更多的用例中更可取。如果您不确定,请从ArrayList开始。


TLDR,在ArrayList中,访问元素需要恒定的时间[O(1)],添加元素需要O(n)时间[最坏情况]。在LinkedList中,插入元素需要O(n)时间,访问也需要O(n)时间,但LinkedList比ArrayList使用更多内存。

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

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

对于LinkedList<E>

get(int index)为O(n)(平均步数为n/4),但当index=0或index=list.size()-1时为O(1)(在这种情况下,还可以使用getFirst()和getLast())。LinkedList的主要优点之一add(int index,E元素)为O(n)(平均步数为n/4),但当index=0或index=list.size()-1时为O(1)(在这种情况下,还可以使用addFirst()和addLast()/add())。LinkedList的主要优点之一remove(int index)为O(n)(平均步数为n/4),但当index=0或index=list.size()-1时为O(1)(在这种情况下,还可以使用removeFirst()和removeLast())。LinkedList的主要优点之一Iterator.remove()为O(1)。LinkedList的主要优点之一ListIterator.add(E元素)为O(1)。LinkedList的主要优点之一

注:许多操作平均需要n/4步,在最佳情况下(例如索引=0)需要恒定的步数,在最坏情况下(列表中间)需要n/2步

对于ArrayList<E>

get(int索引)为O(1)。ArrayList的主要优势<E>add(E元素)是O(1)摊销,但O(n)最坏情况,因为数组必须调整大小并复制add(int索引,E元素)为O(n)(平均n/2步)remove(int索引)为O(n)(平均n/2步)Iterator.remove()为O(n)(平均为n/2步)ListIterator.add(E元素)为O(n)(平均n/2步)

注:许多操作平均需要n/2步,在最佳情况下(列表末尾)需要恒定的步数,在最坏情况下(开始列表)需要n步

LinkedList<E>允许使用迭代器进行恒定时间的插入或删除,但只能对元素进行顺序访问。换句话说,您可以向前或向后遍历列表,但在列表中找到位置所需的时间与列表的大小成正比。Javadoc表示“索引到列表中的操作将从开始或结束遍历列表,以较近者为准”,因此这些方法平均为O(n)(n/4步),尽管索引=0时为O(1)。

另一方面,ArrayList<E>允许快速随机读取访问,因此您可以在恒定时间内获取任何元素。但是,除了末端之外,任何地方的添加或删除都需要将后面的所有元素转换过来,要么打开,要么填补空白。此外,如果添加的元素超过了基础数组的容量,则会分配一个新数组(大小的1.5倍),并将旧数组复制到新数组,因此在最坏的情况下,添加到ArrayList是O(n),但平均来说是常量。

因此,根据您打算执行的操作,您应该相应地选择实现。对这两种列表进行迭代实际上都是同样便宜的。(在ArrayList上迭代在技术上更快,但除非您正在做一些对性能非常敏感的事情,否则不必担心这一点——它们都是常量。)

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

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

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

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

如果使用数据结构透视图来理解这两个结构,LinkedList基本上是一个包含头节点的顺序数据结构。Node是两个组件的包装器:一个类型为T的值[通过泛型接受],另一个对链接到它的Node的引用。因此,我们可以断言它是一个递归数据结构(一个Node包含另一个节点,该节点具有另一个Node等等…)。如上所述,在LinkedList中添加元素需要线性时间。

ArrayList是一个可增长的数组。它就像一个常规数组。在后台,当添加了一个元素,并且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);
    }
}