2

This article指出LinkedList中存在“无随机访问”。有人可以向我解释一下吗？

给定

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

然后我可以使用，

l.get(n);

鉴于此，为什么文章说“没有随机访问”？

4

6 回答 6

11

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

l.get(n);

此方法在后台也以相同的方式工作。它从头部遍历然后检索nth元素

于 2013-06-22T07:15:30.083 回答
4

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

使用链接列表

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

使用数组

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

于 2013-06-22T07:25:58.207 回答
1

您将从头开始并遍历到n，这不是随机访问！！！而这里是从head遍历到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;
    }
}
于 2013-06-22T07:15:21.263 回答
1

当我们说关于 java 集合时，这意味着它没有实现 RandomAccess 接口

您可以在此处进一步阅读 RandomAccess

于 2013-06-22T07:19:16.047 回答
1

javadoc写道：

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

所有操作都按照双向链表的预期执行。索引到列表中的操作将从开头或结尾遍历列表，以更接近指定索引的为准。

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

这可能就是您的教程所说的“无随机访问”。

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

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

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

长话短说：您可能会忘记LinkedList，而只需ArrayList在需要时使用 a List。

于 2013-06-22T07:21:51.823 回答
0

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

于 2013-06-22T07:19:14.177 回答