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

Question

本文指出LinkedList中存在"无随机访问".任何人都可以向我解释一下吗？

特定

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

然后我可以用,

l.get(n);

鉴于此,为什么文章说"没有随机访问"？

Answer 1

这里的随机访问意味着,您无法直接访问链接列表中与数组类似的任何元素.在链接列表中,您必须traverse从头部开始每个元素(链接),然后您可以访问该元素.

l.get(n);

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

Answer 2

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

\n\n

使用链接列表

\n\n

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

\n\n

使用数组

\n\n

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

\n