LinkedList如何在Java內部工作？

據我所知，鏈表的概念是通過擁有'next'和'有時''previous'屬性來遍歷對象而彼此連接的一堆對象。LinkedList如何在Java內部工作？

我在Java中注意到，您可以創建一個LinkedList對象......但如。新增（），獲得（）等

用同樣的方法把它當作一個數組/列表/序列

因此，LinkedList內部是一個類似數組的序列嗎？

2011-11-23 sqram

如果您想查看實現，請查找您可以在JDK安裝目錄的文件「src.zip」中找到的'java.util.LinkedList'的源代碼。 – Jesper

或者查看源代碼：http：//www.docjar.com/html/api/java/util/LinkedList.java.html –

您可能會對我的[LinkedList in Java內部生命]感興趣（http：// volodial.blogspot.com/2013/05/internal-life-of-linkedlist-in-java.html）教程。 –

那麼，LinkedList內部是一個類似數組的序列嗎？

號這是一個系列的私人嵌套類Entry，其中有next，previous和element引用的實例。請注意，您可以通過查看JDK附帶的源代碼來發現這一點。

該內部結構沒有暴露的原因是它防止了結構被破壞，例如包含一個循環。通過List和Deque接口的統一訪問允許多態使用。

2011-11-23 08:54:03

+1：內部是一個類似數組序列的列表被稱爲ArrayList。 ;） –

-1：這取決於你的編程技巧，我猜。從維基百科有關鏈接列表的文章中：「它也可能很慢，並且使用一個天真的分配器浪費，爲每個新元素分配內存，這個問題通常是使用內存池解決的。」 - 僅供參考，內存池是專業人員用於內部存儲鏈接列表的陣列。它們也被稱爲板分配器。 –

@Anthony：復仇downvote，呃？克服它。熟練的專業人員不會進入互聯網 - 在應該回答問題的層次上進行髮卡。 –

可以使用鏈表實現一個像數組一樣工作的對象。與數組相比，一些操作會更快，有些操作會更慢。例如，對於接近結尾的元素，調用get()可能會比使用數組慢得多。但是，這仍然是可能的。

另一方面，從鏈接列表中間刪除元素將比使用數組完成的相應操作更快。

2011-11-23 08:51:08

LinkedList是一個實體鏈，其中每個實體都知道下一個實體，因此get（index）操作需要使用計數器迭代該鏈。但是這個列表優化爲按位置添加和刪除（如果我需要將元素放入列表中或從中間鏈接列表中刪除元素性能更好）

2011-11-23 08:51:38

不是真的。鏈接列表由集合提供，通過良好的設計可以創建雙鏈表。現在它不像數組，因爲這些對象不會有索引，也不是容器內的元素，即列表中的元素。因此，你需要通過定義下一步和前一步並決定下一步是什麼。他們都有相同的方法，因爲他們又像我說的那樣是集合。

2011-11-23 08:52:09

-8

在內部它將使用所謂的「板分配器」 - 這基本上是一個小陣列的鏈表。每次添加對象時，都會檢查板塊中是否有空間，如果是，則將對象放在那裏。否則，它會分配一個新的平板並將該對象放置在平板的第一個元素中。

該技術最大限度地減少內存分配開銷 - 如果你添加了很多項目，以一個鏈表，那將是一個很大的，其需要大量的時間小內存分配，和板坯分配器儘量減少

2011-11-23 08:52:19

這根本就是錯的。 Java不是C++。小分配速度很快。因此，API實現不使用任何技巧來避免它。 –

@MichaelBorgwardt你認爲JVM如何獲得它分配的每個對象的內存？你認爲JVM每次都調用malloc（）嗎？垃圾收集器在平板中使用內存。請解釋您如何認爲Java爲鏈表分配內存而沒有內存塊。 –

@MichaelBorgwardt從有關IBM的JVM的文檔：「這些部分通常實現爲由Java內存管理器（包括垃圾收集器）控制的本地內存的連續平板。」 –

因爲我知道鏈表就像你在第一段所說的。每個對象都有兩個引用，稱之爲上一個，下一個。不同於數組，按順序工作（在C中它完全按順序存儲，我認爲java只是做同樣的事情，這就是爲什麼我們不能重新調整數組大小），列表通過引用工作。因此邏輯上它比數組運行速度慢。

2011-11-23 08:59:09 simaremare

Java中的LinkedList正如您所期望的那樣工作。如果您使用官方收藏集LinkedList那麼它確實會是一個通過「下一個」，有時是「前一個」相互連接的一組對象。

是的，它有一個get(int index)方法，這是令人驚訝的，因爲它不會很有效，因爲您需要從頭開始，並在列表中計數以找到index th條目，這不是LinkedLists擅長。它存在的原因是因爲LinkedList實現了接口List。這是你可以用ALL列表的東西。

但是，當您的大多數訪問權限通過get(int index)方法時，您可能會嘗試避免使用LinkedList，因爲這顯然是效率最低的。你可能會更好地使用ArrayList。

2011-11-23 09:08:16 OldCurmudgeon

回答