在什么意义上，LinkedList可以说不支持随机访问

Question

本文指出LinkedList中存在"无随机访问"。有人能向我解释一下吗？

给定

LinkedList<String> l = new LinkedList<>();

然后我可以使用

l.get(n);

既然如此，为什么文章说"禁止随机访问"？

Answer 1

这里的随机访问意味着，您不能直接访问类似于数组的链表中的任何元素。在链表中，您必须从头部开始traverse每个元素（链接），然后才能访问该元素。

l.get(n);

这种方法在后台也以同样的方式工作。它从头开始遍历，然后检索nth元素

Answer 2

随机访问意味着您可以在恒定时间中找到第i个元素。更具体地说，它不取决于列表的大小，也不取决于您是否正在访问第一个元素、最后一个元素或在中间的一个元素。

使用链接列表

你必须遍历所有元素，从第一个到第i个，才能找到第i个。因此，获取最后一个元素要比获取第一个元素花费更多的时间。因此，这不是随机接入。

使用阵列

数组中的元素连续存储在内存中。因此，如果您知道第一个元素的地址A，并且每个元素的大小都为S，那么您就直接知道第i个元素的名称：A + i*S。此操作对数组中的任何元素花费相同的时间，并且足以检索它。因此，数组是随机访问的。

Answer 3

您将从head开始，遍历到n，这不是随机访问！！！这是从磁头到N 的遍历方法

Node<E> node(int index) {
    // assert isElementIndex(index);
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

Answer 4

当我们谈到java集合时，意味着它没有实现RandomAccess接口

你可以在这里进一步了解随机存取

javadoc写入：

列表和Deque接口的双链表实现。实现所有可选的列表操作，并允许所有元素（包括null）。

所有操作的执行都与双链表所预期的一样。索引到列表中的操作将从开始或结束遍历列表，以更接近指定索引的为准。

也就是说，即使LinkedList提供了一个访问第i个元素的方法，该方法也会在内部沿着列表遍历，直到到达该元素，因此效率很低。

这可能就是你的教程所说的"；无随机接入"；。

相比之下，ArrayList是基于数组的，其中第i个元素可以直接访问，或者正如其javadoc所说：

size、isEmpty、get、set、迭代器和listIterator操作以恒定时间运行。加法运算在摊余常数时间内进行，即添加n个元素需要O（n）时间。所有其他操作都在线性时间内运行（粗略地说）。与LinkedList实现相比，常量因子较低。

一般来说，java.util.LinkedList很少使用，因为ArrayList需要更少的内存，可以更快地迭代，并且支持通过索引进行高效访问。这并不意味着链表（数据结构）是无用的，只是java.util.LinkedList不允许它们的主要优势（保留对列表元素的引用，可能删除该元素或在其附近添加新元素的能力），因为迭代器会因并发修改而无效。

长话短说：你可能会忘记LinkedList，只要你需要List，就可以简单地使用ArrayList。

如果使用get（n），它会跳过列表中的前n-1个元素。如果index＝n/2，则搜索从列表的末尾开始。