algorithm - 哈希表中的删除

Question

我在读《算法导论》这本书时遇到了这个:

We can delete an element in O(1) time if the lists are doubly linked. (Note that CHAINED-HASH-DELETE takes as input an element x and not its key k, so that we don’t have to search for x first. If the hash table supports deletion, then its linked lists should be doubly linked so that we can delete an item quickly. If the lists were only singly linked, then to delete element x, we would first have to find x in the list T[h(x.key)] so that we could update the next attribute of x’s predecessor. With singly linked lists, both deletion and searching would have the same asymptotic running times.)

如果列表是双向链接的，我们如何在 O(1) 时间内删除一个元素？首先我们需要找到元素，然后我们可以在 O(1) 中删除它。但是要找到它，我们需要 O(列表长度)时间。也许在双向链表中删除更快(因为我们可以同时从列表的两端进行搜索，但这只是不断的改进)，但我看不出如何在 O(1) 中完成时间。

提前致谢。

Answer 1

答案在文中；

Note that CHAINED-HASH-DELETE takes as input an element x and not its key k, so that we don’t have to search for x first.

您已经拥有该项目，因此您只需将其从链中删除并进行删除。

要删除项目 X，您需要在删除 X 之前获取列表中的上一个和下一个节点并将它们链接在一起，以便列表保持完整。在双向链表中，您已经拥有指向上一个和下一个的链接，因此这是不变的。在单个链表中，您只有指向下一个节点的链接，因此您需要扫描整个列表以找到前一个节点。