链接列表的使用

，尽管有这么多有效的数据结构，为什么只挂在系统编程中使用如此巨资列表？是否因为它允许最少使用堆/更少的错误代码？链接列表的使用

问候， 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

回答