微軟要求：單列表還是雙列表？使用每種方法有哪些優缺點？

我被問到這樣的問題，我有自己的說法，但我不確定應該對利弊做什麼評論？微軟向其中一位候選人提出了這個問題。微軟要求：單列表還是雙列表？使用每種方法有哪些優缺點？

單鏈表允許你去一個方向。而雙向鏈表則有下一個和前一個雙向的方向。

這是繪製單曲和雙曲列表的好圖片。

enter image description here

但是，你怎麼解釋在更有序的方式，這些項目的利弊？

來源

2012-05-22 Tarik

一個更靈活，另一個需要更多的開銷。此外，你的鏈表是真正的循環鏈表。 – robert

我使用這些圖片來實際擡頭。 – Tarik

您可能想查看[plain-linked-and-double-linked-lists-when-and-why]（http://stackoverflow.com/questions/712429/plain-linked-and-double-linked-lists-何時和爲什麼） – nawfal

我被問到這樣的問題，我有自己的說法，但我不確定應該對利弊做什麼評論？

這一切歸結爲使用。這裏有一個交易。

單鏈表在實現方面更簡單，並且通常具有較小的內存需求，因爲它只需保持前向成員引用就位。

雙鏈表具有更高效的迭代，特別是如果您需要反向迭代（對於單個鏈表而言效率非常低下），並且可以更有效地刪除特定節點。

這就是說 - 因爲你有這個標記的.NET，雙鏈表也有直接在框架中的LinkedList<T>類的形式的優勢。這提供了巨大的優勢，因爲您不必實施，測試和維護自己的集合類。

來源

2012-05-22 19:31:38

我不認爲單邊鏈表是在FCL中預定義的嗎？ – Tarik

優勢雙向鏈表的：在兩個方向可以遍歷

優勢單鏈表的：少做家務要在更新/插入/刪除，使用更少的內存來完成。

來源

2012-05-22 19:32:16 Porco

那麼，這取決於情況。如果您需要能夠快速獲取給定元素的前一個元素和下一個元素，那麼雙向鏈接列表是最好的。

如果您只需要從給定元素獲取下一個元素，那麼單個鏈接列表就足夠了。

來源

2012-05-22 19:32:28 Peladao

雖然單鏈表使用較少的內存節點（一個指針與兩個指針），但它的刪除操作是O(N)，如果您擁有的是指向要刪除的節點的指針，而雙向鏈接的刪除是O(1)。有一個鮮爲人知的技巧，可以讓您從O(1)中的單向鏈接列表中刪除，但該列表必須循環才能正常工作（將next的內容移動到當前，並刪除next）。

雙鏈表可用於單鏈表無法工作的地方（雙端隊列），但它們需要稍微多一些「內務」，並且插入效率稍低一些。

來源

2012-05-22 19:33:04 dasblinkenlight

雖然這個問題已經回答了，我有點不滿意的答覆（沒有冒犯的意思），所以這裏是我會怎麼回答它：

什麼用 - 單或雙鏈表取決於你打算實現什麼和系統限制，如果有的話。

單鏈表：

優點：實現簡單，需要的存儲相對較小的內存，假設你需要刪除/插入（在）下一個節點 - 插入/缺失更快。

缺點：無法反向迭代，需要維護一個到其他列表頭節點的句柄，否則該列表將丟失在內存中。如果您要刪除前一個節點或在前一個節點上插入，則需要遍歷從頭到前一個節點的列表，以便能夠執行這些操作 - O（N）時間。

- 所以，當你的內存較小，而你的主要目標是插入/刪除而不是搜索元素時，應該使用它。

雙向鏈表：

優點：可以在未來的同時也反方向進行迭代。如果需要刪除前一個節點，則不需要從頭節點開始遍歷，因爲要從「.previous」指針中找到要刪除的節點。

缺點：實現起來相對複雜，需要更多的內存來存儲（每個節點1'.previous'指針）。插入和刪除相對更耗時（爲鄰居節點分配/重新分配「.previous」指針）

- 當您對內存沒有或有最小限制時，應使用此選項，您的主要目標是搜索元素。

如果還有其他一些優點和缺點，請隨時添加，並在評論中回覆。謝謝！

來源

2012-09-12 12:02:24 coder0h1t

微軟要求：單列表還是雙列表？使用每種方法有哪些優缺點？

回答

相關問題