为什么使用双链表删除哈希表的元素为O（1）？

在CLRS的教科书“算法简介”中，pg上有这样一段。258。

如果列表是双向链接，则可以在O（1）时间删除一个元素。（请注意，CHAINED-HASH-

DELETE将元素x而不是其键k作为输入，因此我们不必首先搜索x。如果哈希表支持删除，则应将其链表加倍链接，以便我们可以快速删除一个项目，如果列表仅是单个链接，则要删除元素x，我们首先必须在列表中找到x，以便我们可以更新x的前

一个元素的 下一个 属性。和搜索将具有相同的渐近运行时间）。

这个大括号让我感到困惑，但我未能理解它的逻辑。对于双链表，仍然必须找到x才能删除它，这与单链表有何不同？请帮助我理解它！

这里出现的问题是：考虑到您正在查看哈希表的特定元素。删除它的代价是多少？

假设您有一个简单的链表：

v ----> w ----> x ----> y ----> z
                |
            you're here

现在，如果你删除x，你需要连接w到y让你列表链接。您需要访问w并告诉它指向y（您想要拥有w ---->

y）。但是您不能w从访问，x因为它只是链接！因此，您必须遍历所有列表才能w在O（n）操作中找到，然后告诉它链接到y。那很糟。

然后，假设您是双向链接：

v <---> w <---> x <---> y <---> z
                |
            you're here

不错，您可以从这里访问w和y，因此可以w <---> y在O（1）操作中连接两个（）！