如何實現100萬個節點的鏈表？

我最近參加了Microsoft Interview。如何實現100萬個節點的鏈表？

我被要求實現100萬個節點的鏈接列表？你將如何訪問999999節點？

什麼是針對這樣一個問題的最優設計策略和實現？

來源

2015-12-14 user2565192

我不禁馬上想：「這要看，爲了什麼？」。不過，不要在面試時回答。無論如何，你正在尋求一個「最佳」解決方案，所以......這取決於。對於一次採訪來說，面試官對這個職位的期望值要高得多，而不是SO問題...... –

我可能會質疑一個100萬節點集合中鏈接列表的使用，因爲這是微軟我們正在談論。表示實施圖表時最鄰近列表的最壞情況是單個鏈表 – UmNyobe

鏈接列表幾乎沒有變化，因爲很多變化意味着它不是鏈接列表。

您可以通過單鏈接或雙鏈接來改變它。單鏈接是你有一個指向頭的指針（第一個節點，A說），指向B指向C等。要將它轉換爲雙鏈表，你還需要添加一個從C到B和B的鏈接到A.

如果你有一個雙鏈表，那麼保留一個指向列表尾部（最後一個節點）和頭的指針是有意義的，這意味着訪問最後一個元素是便宜的，並且接近結尾的元素是便宜的，因爲你可以向後或向前工作......但是......你需要知道你想要的是在列表的末尾......並且在一天結束時鏈表仍然是這樣，如果它會變得非常大，並且由於其用例的性質而成爲問題，則可能應該選擇除鏈接列表之外的存儲結構。你可以混雜你的鏈接列表當然，所以你可以索引它或某些東西，理論上沒有什麼錯，但是如果你索引所有的節點，那麼鏈表性質不再有太大的價值，如果你只索引一些節點，那麼索引節點之間的節點必須進行排序或者其他東西，這樣你可以找到一個關閉節點並且朝向一個目標節點工作......可能這永遠不會是最優的，並且更好的數據結構應該是選擇。

當你不想像做一個特定的節點那樣做事情，而是想迭代節點時，應該使用鏈表。

來源

2015-12-14 09:13:59 Michael

而且這種推理可能是面試者的期望，不僅僅是一個明確的解決方案 – Trompa

我同意，我採訪了很多人，我可以想到沒有其他類型的答案我可以期待候選人，我是否會問他們這樣的問題。 – Michael

如果您試圖按順序保存項目（排序順序，插入順序等），那麼對於跳過列表也是值得一提的，這對於非常大的數據集通常是這種情況。跳過列表就像鏈接列表一樣，但是相比於較低級別的鏈接列表，它們是多層次的，高層次跳過一半節點（平均而言）。 – Tuxdude

我不知道什麼，我要說的想法，但是，這裏有雲：

你可以conceptually分裂名單sqrt(1000000)塊，以這樣的方式，你將不得不「引用指針」每1000個元素。

把它想象成具有1000 linked lists每個1000 elements代表您的列表1000000 elements。

這是想到的！

來源

2015-12-14 09:10:26

推廣這個概念，你會得到一個[跳過列表]（https://en.wikipedia.org/wiki/Skip_list）。 –

酷！我不知道這個:) –

由於邁克爾說你應該首先介紹鏈表的兩個經典變體。接下來你應該做的是詢問插入，搜索和刪除模式。

這些模式將引導您更好地適應數據結構，因爲沒有人想要一個包含一百萬個節點的簡單或雙重鏈接列表。

來源

2015-12-14 10:02:43 UmNyobe

如何實現100萬個節點的鏈表？

回答

相關問題