栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

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

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

为什么使用双链表删除哈希表的元素为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)操作中连接两个()!



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/573625.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号