散列表解决冲突使用双链表与单链表有何区别？

Question

老师，我是边读算法导论然后一边看您的视频，然后，关于散列表这块，算法导论上说，如果解决冲突时候，用双链表来解决冲突，那么删除的时间就会是O(1),而单链表就是o(m)[就是每条链的平均长度]，我很疑惑，这是为什么啊？双链表不也是从头开始查的吗？为什么双链表删除元素就是o(1)了

Answer 1

liuyubobobo 2019-06-15 23:09:31

注意这里的函数定义，对于delete，传入的是x，不是k。k是键值，x是节点。所以，删除操作传入的是要删除的节点。所以，这个过程不需要查找。对于双链表，直接可以获得待删除节点的前驱，之后就可以直接删除该节点：）

继续加油！：）