为什么使用双向链表删除哈希表的元素是O(1)？

Question

在CLRS的教科书"算法导论"中,有关于pg的这一段.258.

如果列表是双重链接,我们可以在O(1)时间内删除一个元素.(注意,CHAINED-HASH-DELETE将元素x作为输入而不是其键k,因此我们不必首先搜索x.如果哈希表支持删除,则其链表应该双重链接,以便我们可以快速删除一个项目.如果列表只是单链接,那么要删除元素x,我们首先必须在列表中找到x,以便我们可以更新x的前一个属性的下一个属性.使用单链表,两个都删除并且搜索将具有相同的渐近运行时间).

让我感到困惑的是这个大家伙,我无法理解它的逻辑.有了双链表,还是要找到x才能删除它,这与单链表有什么不同？请帮我理解一下!

Answer 1

这里提出的问题是:考虑到你正在查看哈希表的特定元素.删除它的成本有多高？

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

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)操作中连接两个()!