數組和鏈表

Question

我想知道數組和鏈表。如果您嘗試對數組和鏈接列表中的元素進行排序，速度會更快。哪個列表索引是更快的數組或鏈表？如果我們試圖從數組和鏈表中找到一個元素，這將花費更少的時間來查找相應的元素，最後一件事情是什麼？ 我對數組和鏈表有所瞭解。糾正我，如果我錯了。數組是固定大小和連續的內存數據結構。而鏈表不是固定的大小。

Answer 1

從SCJP認證書：

的ArrayList：

可以把它看作一個可增長的數組。它給你快速的迭代和快速的隨機訪問。要說明這一點：它是一個有序集合（按索引），但不是 排序。你可能想知道，從版本1.4開始，ArrayList現在實現了 新的RandomAccess接口 - 一個標記接口（意思是它沒有方法）， 表示「這個列表支持快速（通常是恆定時間）的隨機訪問。」 選擇 這在一個LinkedList，當你需要快速迭代，但不作爲可能是做了很多 插入和刪除的

的LinkedList：

一個LinkedList被索引位置排序的，如ArrayList，除了 這些元素是彼此雙重鏈接的。這種聯繫爲您提供了新的 方法（超出了您從列表界面獲得的內容），用於從開始或結束添加和刪除 ，這使得它成爲實現堆棧 或隊列的簡單選擇。請記住，LinkedList的迭代速度可能比ArrayList慢，但當您需要快速插入和刪除時，它是一個不錯的選擇。從Java 5開始， LinkedList類已被增強以實現java.util.Queue接口。作爲 這樣，它現在支持公共隊列方法： 偷看（），輪詢（），並提供（）

Answer 2

ArrayList表示爲一個數組，但ArrayList類正在做所有事情，包括調整數組大小，所以你不必關心大小。

Add to end : constant time 
Add to else : linear time (average is n/2 = O(n)) 
Get : constant 
Delete : same as add 

LinkedList的表示爲鏈表。這意味着鏈表的每個部分都可以訪問下一部分和之前的部分。

Add to anywhere : constant time 
Delete from anywhere : constant time 
Get : linear time (average is n/2 = O(n)) 

但是，兩者都是列表，這意味着它們不是固定的。唯一的區別是當你使用它們時，有些方法比另一個List實現更快/更慢。

Answer 3

對於所有這些操作，數組的速度更快。鏈接列表更快的唯一時間是當你需要刪除或添加一個元素。但是對於固定的項目集合，數組總是更快。