從什麼意義上說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可以說不支持隨機訪問？

回答

相關問題