c - 如何确定双向链表成为比简单链表更好的解决方案的点？

Question

据我了解，与简单链表相比，双向链表使用更多内存但 CPU 更少，并且通常提供更好的算法复杂度。

我想知道的是，与双向链表相比，简单链表何时提供更好的整体结果。是否有明确的点/情况，之后使用一个而不是另一个无疑是最好的解决方案？（就像普通 PC 上的 x 元素之后一样）

我的具体问题：

我正在实现一个一般用途的链表结构，并且正在考虑是否应该包含一个返回链接，因为它会大大降低元素删除的复杂性。

谢谢。

---

更新：

在一个简单的链表上，删除元素的成本在多大时会变得过于昂贵？

Answer 1

选择数据结构是关于权衡成本与收益，通常是工作与维护。

单链表提供了简单的遍历和简单的前端插入。可以以跟踪最后一个节点为代价进行简单的尾部插入。该成本意味着每当您添加/删除一个节点时，您都​​必须进行额外的检查（这是尾部吗？）并可能更新列表结构。

双向链表增加了更多的维护开销。现在每个节点都必须存储两个指针，并且必须对其进行管理和维护。

如果您从不需要在列表中向后走，那么单链表是理想的，但不能向后走意味着删除成本更高。

因此，您需要首先确定您将拥有哪种使用模式。如果您正在构建一次性列表，那么单链表可能是理想的选择。如果您正在构建一个具有高删除率的动态列表，那么双向链表将更适合。

确定数据结构提供的特定操作成本是“大 O 表示法”之类的主题。

Answer 2

我想知道的是，与双向链表相比，简单链表何时提供更好的整体结果。

当你不必倒退时。

如果您正在进行单向线性搜索，则没有动力从另一个方向遍历列表，并且您不需要这些指针。

更新：

在一个简单的链表上，删除元素的成本在多大时会变得过于昂贵？

这个问题与列表是单链接还是双链接无关。如果你必须删除列表中的某些东西，你需要寻找它，这就是时间复杂度O(n)。有一个指向前一个节点的额外指针在这里没有帮助。

Answer 3

链表是一种数据结构，大多数情况下可用于实现堆栈或队列。一般来说，如果您正在实现堆栈插入和删除，则发生在单端。如果使用 Q 通常我们在一端删除并在另一端添加。正如您所看到的，这两个抽象 ds 都不需要双重列表，并且添加和删除操作不依赖于项目的数量。正如 Kepani 上面提到的，唯一担心列表中元素数量的情况是当您以堆栈/Q 接口未描述的方式删除时（一种非线性方法）。这将是元素被排序的时候（当然也可以是其他的）并且需要维护顺序。由于每个节点都需要维护一个“额外”指针，因此使用双列表肯定很难满足内存需求，除非你试图维护一个你引用过去值的商店。Dlist 在这里会很方便（例如：cli 命令行解释器。）单个列表很难按时完成，因为到达当前节点的先前值所需的遍历将取决于列表中元素的数量。