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

This article指出在LinkedList中有“没有随机存取”。有人可以向我解释这一点吗？从什么意义上说LinkedList可以说不支持随机访问？

鉴于

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

那么我可以用，

l.get(n);

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

来源

2013-06-22 JOHND

@Michael Petrotta：感谢编辑 – JOHND

随机存取的方法在这里是指，你不能直接访问的任何元件以类似于阵列的链表。在链表，你必须traverse每个元素（链接）从头部开始，然后您可以访问该元素。

l.get(n);

这种方法在后台也是一样的。它从头部遍历，然后检索nth元素

来源

2013-06-22 07:15:30 dejavu

然后这篇文章说Arraylist中的“随机访问可能”。这是否意味着它实际上直接访问第n个元素而没有从头开始遍历。 – JOHND

是的，数组的工作方式不同。数组是基于索引的数据结构，链表是基于链接的。在数组中，您可以直接访问O（1）时间中的第n个元素，而在链接列表中，它需要O（n）时间 – dejavu

@JOHND接受答案，如果它解决了您的问题。 – dejavu

你会从头和遍历到ñ它不是随机访问！这里是从头部遍历到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-22 07:15:21

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

来源

2013-06-22 07:19:14

当我们说一下Java集合这意味着它不会实现了RandomAccess接口

您可以进一步了解在这里 RandomAccess

来源

2013-06-22 07:19:16 Kalher

的Javadoc writes：

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

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

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

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

的ArrayList，在constrast，基于阵列，其中第i个元素可以直接访问，或作为其的Javadoc所说：

大小，的isEmpty，获取，设置迭代器，和listIterator操作在恒定时间内运行。 add操作以分摊的恒定时间运行，即添加n个元素需要O（n）个时间。所有其他操作都在线性时间内运行（粗略地说）。与LinkedList实现相比，常数因子较低。

一般来说，java.util.LinkedList很少被使用，因为ArrayList需要更少的内存，可以更快地迭代，并且支持索引的高效访问。这并不意味着链表（数据结构）是无用的，它只是它们的主要优点（能够保持对列表元素的引用，可能移除该元素或在其附近添加新元素）不被java.util.LinkedList，因为迭代器通过并发修改而失效。要长话短说：你可能会忘记LinkedList，只要你需要List就简单地使用ArrayList。

来源

2013-06-22 07:21:51 meriton

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

随着链表

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

随着阵列

您的阵列中的元素被存储在连续存储器。因此，如果您知道第一个元素的地址A，并且元素的大小分别为S，则直接知道第i个元素的地址：A + i*S。此操作对阵列中的任何元素都采用相同的时间，并且足以检索它。因此，数组是随机访问。

来源

2013-06-22 07:25:58 Boris

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

回答

相关问题