介紹 LinkedList 集合

一、歷史LinkedList

Java還有一個集合類Java繼承自C++語言。這是LinkedList實現“鍊錶”的類。

從表面上看，aLinkedList似乎與 an 相同ArrayList。該類LinkedList具有與該類相同的所有方法ArrayList。原則上，您始終可以使用 aLinkedList而不是 an ArrayList，一切都會正常進行。

那麼為什麼我們需要另一個列表類呢？

答案與類的內部結構息息相關LinkedList。它不使用數組，而是使用雙向鍊錶。我們稍後會解釋那是什麼。

該類LinkedList不同的內部結構使其在列表中間插入元素的速度最快。

在網上經常可以找到類ArrayList和LinkedList類的對比：

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

一切似乎都很清楚：如果您需要經常向列表中插入元素，請使用LinkedList; 如果很少，則使用 ArrayList。但現實有點不同。

2. 沒人用LinkedList

沒有人使用LinkedList。

就連該課程的作者LinkedList最近也在推特上寫道：“真的有人用嗎LinkedList？我寫的，我從來沒用過。”

那有什麼關係呢？

首先，該類ArrayList開始能夠非常快速地將元素插入到列表的中間。在列表中間插入一個元素時，必須將插入點之後的所有元素向列表末尾移動 1。這過去需要時間。

但現在一切都變了。數組的所有元素在同一塊內存中彼此靠近，因此移動元素的操作由一個非常快速的低級命令執行：。System.arraycopy()

此外，今天的處理器有一個大緩存，通常可以容納整個數組，這允許數組元素在緩存內而不是在內存中移動。一百萬個元素可以在一毫秒內輕鬆移動。

其次，如果您使用迭代器插入元素，該類可以快速插入元素。LinkedList如果使用迭代器遍歷 aLinkedList並不斷插入新元素（或刪除現有元素），操作速度非常快。

LinkedList如果您只是在循環內向對象添加元素，那麼每個快速插入操作都伴隨著一個緩慢的“獲取元素”操作。

現實更接近於此：

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

為什麼從如此緩慢的操作中獲取元素LinkedList？

你可以在稍微了解一下它的LinkedList結構後回答這個問題。

3.LinkedList結構如何

LinkedList與 . 具有不同的內部結構ArrayList。它沒有用於存儲元素的內部數組。相反，它使用一種稱為雙墨列表的數據結構。

雙向鍊錶的每個元素都存儲對前一個元素和下一個元素的引用。這有點像在商店排隊，每個人都記得站在他們前面的人以及站在他們後面的人。

這是這樣一個列表在內存中的樣子：

頭部和尾部（灰色背景的單元格）是first和last變量，它們存儲對Node對象的引用。

在中間，你有一個Node對象鏈（對象，不是變量）。它們每個都包含三個字段：

• prev— 存儲對前一個對象（黃色背景的單元格）的引用（鏈接）。Node
• value— 存儲列表中該元素的值（綠色背景的單元格）。
• next— 存儲對下一個對象（藍色背景的單元格）的引用（鏈接）Node

第二個對象（地址 F24）是next第一個對象的下一個 ( ) 和prev第三個對象的前一個 ( )。第三個對象的黃色字段包含地址 F24，第一個對象的藍色字段包含地址 F24。

第一個和第三個對象的箭頭指向同一個第二個對象。所以這樣畫箭頭會更正確。

4. 向鍊錶中插入一個元素

要像這樣添加某人，您只需要獲得併排站著的兩個人的許可即可。第一個人記得新人是“我身後的人”，第二個人記得他們是“我前面的人”。

您需要做的就是更改兩個相鄰對象的引用：

我們通過更改第二個和第三個對象的引用向我們的列表中添加了一個新項目。新對像是舊的第二個對象的下一個，舊的第三個對象的前一個。當然，新對象本身需要存儲正確的引用：它的前一個對像是舊的第二個對象，它的下一個對像是舊的第三個對象。

刪除一個元素更容易：如果我們想刪除，比方說，列表中的第 100 個對象，我們只需要更改第 99 個對象的字段，使其next指向第 101 個對象，並更改第prev101 個對象的字段對象，使其指向第 99 個。就是這樣。

但是獲得第 100 個對象並不是那麼容易。

5. 從列表中刪除一個元素

要獲取鍊錶的第 100 個元素，您需要：

獲取第一個對象：您使用對像first中的變量來執行此操作LinkedList。第一個對象的字段next存儲對第二個對象的引用。這就是我們獲得第二個對象的方式。第二個對象引用了第三個，依此類推。

如果我們需要獲取第 100 個對象的引用，我們需要依次遍歷從第 1 個到第 100 個的所有對象。如果我們需要列表中的第 100 萬個元素，我們需要一個接一個地迭代一百萬個對象！

並且如果這些對像在不同的時間被添加到列表中，它們將位於內存的不同部分並且不太可能同時在處理器的緩存中結束。這意味著迭代鍊錶的元素不僅慢，而且非常慢。

這就是我們正在處理的。

那麼我們為什麼要教你這個慢是如何LinkedList工作的呢？

那麼，在求職面試中，您將被問到與 . 有何LinkedList不同ArrayList。確實。