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

为什么使用双链表删除哈希表的元素为O（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） *** 作中连接两个（）！