指針和對象的實現

Question

這是雙鏈表的多數組表示形式的圖像。具有鍵4的對象在原始鏈接列表中跟隨具有鍵16的對象。這裏4出現在鍵[2]中，16出現在鍵[5]中。這裏的概念是使用無指針和對象的數組實現雙鏈表。有人能解釋這些元素是如何相互關聯的嗎？

Answer 1

第一個密鑰爲9，存儲在索引[7]。您知道這是因爲L包含列表頭部的索引（7）。果然，你可以看到它沒有「先行」價值。

從這裏，列表中的下一項存儲在索引[5]。 （這就是它告訴我們在「下一個」陣列中的索引[7]，該細胞具有的16的關鍵。

從這裏我們去到[2]，其關鍵4和[3]具有關鍵1，這是因爲它沒有「next」，因此它沒有「next」

如果你想要倒退，你也可以看一下「prev」值，重要的是要注意「next」和「prev」包含與「key」完全不同的類型的數字Next和Prev指的是數組索引，在本實現中基本上取代了指針的地方，Key包含一個數字值，表示該節點在t時刻的實際內容他列出。

Answer 2

您的數據結構將正常工作。如果你編碼C++，你應該定義next和prev。類型size_t。但是，我沒有看到任何價值。

1. 需要額外的數學運算才能進入下一個元素。通過指針鏈接的傳統列表，您只需訪問存儲在pNext字段中的地址。用你的鏈表，計算下一個元素的地址需要一個乘法和一個加法。

2. 如果您的目標是優化內存佈局以實現緩存友好性 - 它已在某些列表實現中完成。例如，微軟在ATL中的實現就是這樣做的。 CAtlList類不是用新操作符分配元素，而是分批分配它們，這就是爲什麼標準STL列表通常比基於微軟版本的基準測試慢兩倍的原因。