鏈接列表的使用

，儘管有這麼多有效的數據結構，爲什麼只掛在系統編程中使用如此巨資列表？是否因爲它允許最少使用堆/更少的錯誤代碼？鏈接列表的使用

問候， PWN

2010-05-31 Pwn

這不完全是一個重複，但它是非常相關的：[在什麼情況下內襯列表有用嗎？]（http://stackoverflow.com/questions/2429217/under-what-circumstances-are-linked-清單 - 有用） – 2010-05-31 19:23:27

有趣的問題。您的聲明對於系統編程的某些分支似乎非常有效。但是一旦你遇到了，你很可能會遇到樹形數據結構。文件系統。我想知道鏈表是否足以實現高效的操作系統內存管理內核。我猜不是。 – stakx 2010-05-31 19:26:17

鏈表是用於像隊列或堆棧要在末尾添加東西，或從一開始就刪除它一個非常高效的數據結構。系統編程與隊列和堆棧有很大關係。

2010-05-31 19:22:58

通常是因爲你需要一個東西列表 - 也就是說，你通常幾乎只需要一些東西，你可以很容易地在任一端添加/刪除，或者刪除/插入一個你已經擁有和重複使用的節點指針。

有足夠的，你不需要隨機訪問或搜索功能區域 - 或者你需要搜索的空間是如此之小，一個鏈表反正比「花哨」的數據結構更快。

雖然有時，它也是因爲鏈表是easiy實現。

2010-05-31 19:23:26 nos

我猜，因爲它只是非常簡單地理解和實施。它有一個非常小的開銷。內核可以訪問大量的內存（畢竟它負責它），並且主要控制事物的列表（而不是將一個事物與另一個連接起來的關聯結構）。

所以這只是一個很好的匹配。沒有（或者很少）需要進一步複雜化。

2010-05-31 19:23:55

（如果你看看這裏的鏈接列表相關問題的數量，我懷疑他們真的很容易讓你頭腦發熱.-)但是他們肯定比例如。紅色的黑色樹木。） – stakx 2010-05-31 19:29:22

你絕對可以用它們做一些奇怪的（令人困惑的）事情 - 但總的來說，遍歷它們並對它們進行基本操作（添加/刪除）非常簡單和快速。另外，我可能應該把這個放在我的答案中 - 但我認爲它們對於立即發現腐敗很有幫助。內核知道mem的有效區域。 Wonky指針=壞名單 – 2010-05-31 19:42:25

鏈接列表爲幾個重要的抽象數據結構（包括堆棧，隊列，散列表，符號表達式和跳過列表）提供了一個簡單的實現。

2010-05-31 19:23:58 pcent

其部分原因是因爲efficent數據結構往往有條目數量較少打交道時是比較大的開銷，部分原因是因爲很多OS數據結構是其中的FIFO鏈表是良好的。

2010-05-31 19:24:42 Remy

有沒有好的答案，因爲你作出錯誤的假設。這是不正確的，只有鏈表被大量使用。當有很多事情需要按順序遍歷時使用它 - 如空閒內存段列表，隊列狀結構等。

有很多地方你需要完全這樣的結構。還有其他地方你不需要它。

2010-05-31 19:25:45 viraptor

鏈表是非常有效的許多系統級任務：

移除一個元件0

在系統編程中很少有一個集合，您必須通過密鑰來查找事物，或者必須採用兩個集合。當然在文件系統中，你會發現使用更復雜的數據結構。

這是因爲它允許最少使用堆/較少的錯誤代碼？

號在很多情況下，一個鏈表是這項工作的最合適的數據結構。

2010-05-31 20:33:33

鏈接列表可以很容易地綁定到其他數據結構（例如哈希表）。而且它們可以很容易地轉換爲數組，並且有不同的實現方法，例如一個或兩個鏈接鏈表。

2010-05-31 21:13:04

回答