展開的鏈表如何工作

任何人都可以解釋我展開的鏈接列表是什麼。據我所知，它是一個鏈表，其中每個節點都有元素數組。當然，這使搜索更快。展開的鏈表如何工作

在該圖中，加在該圖象數據1,2,3是清楚的，無併發症...但他們爲什麼在第二節點加入4-？爲什麼不在第一個節點的第四個元素？那有什麼好處？他們在那裏用來分裂的戰略是什麼？

來源

2013-05-09 Prabhakaran

好處是，他們可以插入數據，而無需移動列表中的每個項目。不管你是否想要分片，它都取決於你。您可以使添加功能檢查最後一個節點是否已滿3/4，並在這種情況下創建新節點。或者他們可能做了什麼：

如果數組已滿，我們首先在當前節點之前或之後插入一個新節點，並將當前節點中的一半元素移入其中。（http://en.wikipedia.org/wiki/Unrolled_linked_list）

來源

2013-05-09 10:37:33 Philip

非常感謝你....但它是如何在高速緩存中有用的???我們將使用緩存來快速檢索權利！ den如何快速插入將有所幫助？ – Prabhakaran 2013-05-24 12:36:14

理論上，展開的鏈接列表比「正常」鏈接列表快，因爲後者的節點可能在內存中更加分散，導致處理器加載更多的內存頁面。而且，展開的鏈接列表更小，因爲它們不需要爲每個節點存儲指針。實際上，當你只想在列表中存儲小對象或指針/引用時，考慮使用動態數組（向量），因爲它是迄今爲止最有效的容器，請參閱：http://stackoverflow.com/questions/9764452/comprehensive-vector-vs-linked-list-benchmark-for-randomized-insertions-deletion – Philip 2013-05-25 07:50:43

非常感謝:) :)真的很有幫助:) – Prabhakaran 2013-05-28 17:33:00

將數字4添加到第一個節點的第四個元素。當添加5時，它將分割該節點，其中1，2，3在節點1中，4，在節點2中5。

來源

2013-05-09 10:39:10 SpacedMonkey

但是朋友，爲什麼左空的空間？什麼是目標...好吧，根據philip dahen，插入數據時會更快。但它如何在緩存中有用。 – Prabhakaran 2013-05-24 12:42:22

假設你現在的元素不超過'n'（當然你可以在以後添加元素）並且你想創建一個鏈表，在緩存性能方面最好的辦法是選擇Unrolled linked名單。您在n上創建一個大小爲ceil平方根的塊，然後在塊的大小小於n的平方根的ceil時開始在塊中添加元素。因此，你終於有n塊的平方根。這在搜索鏈表中的第k個節點時很有用，因爲它的複雜性現在已經從n減少到n的平方根。

當塊滿了，意味着如果該塊包含等於n個元素的平方根，則必須進行移位操作，使該塊中的尾部變爲下一個塊的頭部，並且該下一個尾部塊成爲其下一個的頭，依此類推，直到你點擊NULL

在每個塊中，循環鏈表被維護而不是簡單鏈表。

希望這有助於.. :)

來源

2014-09-11 12:43:02 phaigeim

展開的鏈表如何工作

回答

相關問題