在java中使用數組實現鏈接列表？

我已經在robbert laffore中讀過它，我們可以使用數組實現鏈表。但問題是如何？在java中使用數組實現鏈接列表？

我有下面的方法在我的腦海：

1）而不是一個鏈接對象的使用大小的陣列，2一保持到下一個項目和其他參考。但我不是這樣做的好方法。

有人可以建議一個更好的方法來實現鏈接列表使用數組？

來源

2014-02-22 Sahil Gupta

鏈接列表的目的是獲得不使用數組的好處，所以試圖實現這樣的事情毫無意義。 – Whoppa

「而不是鏈接對象使用大小爲2的數組，其中一個保存項目和其他引用到下一個。」 - 這是以某種方式迫使數組進入解決方案的一種方式。不要這樣做！ – RaviH

b/w JAVA和C有**主要差異。首先閱讀JAVA書。 – Astrobleme

一個典型的陣列支持的鏈接列表存儲在一個單一陣列的完整列表，如：

class ABLL<T> { 
    Node[] theList; 
    class Node { 
     T item; 
     int next; // You store the index of the next node 
        // instead of a reference 
    } 
    ... 
}

你會初始化數組的一些能力，它不會增長超出能力（除非你添加該功能，這將涉及分配一個新的數組並將內容複製到它）。您可以搜索「Array-backed Linked List」以查找有關此數據結構的更多討論。

這使得在Java中意義不大比C.

來源

2014-02-22 07:23:17 trutheality

這就是所謂的的ArrayList

相反的是@trutheality說，他們並不需要一個固定的容量，節點不存儲下一個項目的索引。爲了避開典型數組的大小限制，ArrayLists被設計爲當它們達到預定義的最小/最大邊界時自動調整大小。

調整內部陣列的尺寸很昂貴。它包括創建一個新陣列並將數據從舊陣列移動到新陣列。因此，限制所需的調整大小操作的數量是有益的。

一種方法是在列表達到最大容量時將陣列大小加倍，當列表達到1/4容量時將其縮小一半。

陣列沒有收縮到一半容量的原因是爲了避免抖動。抖動是指在容量邊界的邊界上數組增大/減小時，導致大量調整大小操作而對內部數據進行少量更改。

儘管調整大小的成本 - 因爲它只發生在數據集加倍時 - 實際性能成本只有O（log n）。因此，插入成本是線性O（N log N），而檢索是恆定的O（N）。

ArrayLists有一個主要弱點。如果添加/刪除列表中的任意項目，則必須移動數組內容以適應更改。耗費線性O（N）時間的操作。儘管在傳統LinkedList中更改任意項目的成本很便宜（即恆定的O（1）時間），但該操作需要查找來查找耗時線性O（N）時間的鏈中的位置。除非你創建了一個隊列，並且列表的兩端都經常發生變化，否則使用ArrayList作爲列表基礎可能是更好的選擇。

來源：目前正在參加一門算法課程，剛剛完成從頭開始實現ArrayList和LinkedList。

來源

2014-02-24 10:57:36

在java中使用數組實現鏈接列表？

回答

相關問題