我正在阅读《算法简介》一书，我遇到了这个问题：
如果列表是双向链接的，我们可以在 O(1) 时间内删除一个元素。（注意，CHAINED-HASH-DELETE 将元素 x 而不是它的键 k 作为输入，这样我们就不必先搜索 x。如果哈希表支持删除，那么它的链表应该是双向链接的，这样我们可以快速删除一个项目。如果列表只是单链接的，那么要删除元素 x，我们首先必须在列表 T[h(x.key)] 中找到 x，以便我们可以更新 x 的下一个属性前辈。使用单链表，删除和搜索都将具有相同的渐近运行时间。）
如果列表是双链接的，我们如何在 O(1) 时间内删除一个元素？首先我们需要找到元素，然后我们可以在 O(1) 中删除它。但是要找到它，我们需要 O（列表长度）时间。也许在双向链表中删除更快（因为我们可以同时从列表的两端进行搜索，但这只是不断的改进），但我不知道如何在 O(1) 中完成时间。
先感谢您。
答案在文中；
请注意，CHAINED-HASH-DELETE 将元素 x 而非其键 k 作为输入，因此我们不必先搜索 x。
您已经拥有该项目，因此您只需将其从链中删除并进行删除。
要删除项目 X，您需要获取列表中的上一个和下一个节点并将它们链接在一起，然后再删除 X，以便列表保持完整。在双向链表中，您已经有一个指向上一个和下一个的链接，所以这是不变的。在单个链接列表中，您将只有一个指向下一个的链接，因此您需要扫描列表以找到上一个节点。
我认为这里的混乱是因为 CLRS 中的隐含假设。在本书中，对象通常被视为可以在运行时添加所需属性的属性包——很像 JavaScript，但与 Java/C# 世界不同。所以如果要将x放入链表中，不一定要先创建Node对象，然后再添加Previous、Next和Value的属性。相反，您只需将这些属性添加到 x 本身。我们中的许多从小使用静态类型语言长大的人都会对这种设计感到震惊，但对于使用伪代码的算法设计，它消除了不必要的混乱。我认为作者应该澄清这一点。在任何情况下，如果不能动态地将上一个、下一个属性添加到对象，是的，即使使用双向链表，它也不会是 O(1)。