为什么删除使用双向链表哈希表的元素是O（1）？ [英] Why deletion of elements of hash table using doubly-linked list is O(1)?

问题描述

在CLRS的教科书介绍算法，有对皮克这样的段落。 258。

On CLRS's textbook "Introduction to Algorithm", there's such paragraph on pg. 258.

我们可以删除在O（1）时间的元素，如果列表是双向链表。 （请注意，双链HASH-DELETE作为输入的元素x，而不是其密钥k，从而使我们不必寻找对于x首先，如果哈希表支持缺失，那么它的链表应当双链接，以便我们可以快速删除的项目。如果列表只单链表，然后删除元素x，我们首先必须求x在列表中，这样我们就可以更新的下一步的X的$ P属性$ pdecessor随着单向链表，无论是删除和搜索将具有相同的渐近运行时间）。

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 list 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 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).

什么困扰我的是这个大parenthses，我不明白它的逻辑。随着双向链表，人们还是要求x，以便将其删除，这是怎么从单向链表有什么不同？请帮我理解！

What puzzle me is this big parenthses, I failed to understand its logic. With doubly linked list, one still have to find x in order to delete it, how is this different from singly linked list? Please help me to understand it!

推荐答案

在这里psented的问题$ P $是：考虑你正在寻找一个哈希表中的某一元素。如何昂贵的是它删除吗？

The problem presented here is : consider you have are looking at a particular element of a hashtable. How costly is it to delete it?

假设你有一个简单的链接列表：

Suppose you have a simple linked list :

v ----> w ----> x ----> y ----> z
                |
            you're here

现在，如果你删除 X ，需要是W 连接到是来保持你的列表链接。您需要访问是W 并告诉它指向是（您想拥有W¯¯ ----＆GT; Y ）。但是你不能从访问是W X ，因为它只是挂！因此，你必须要经过你所有的列表中找到是W 在O（n）的操作，然后告诉它链接到是。这是不好的。

Now if you remove x, you need to connect w to y to keep your list linked. You need to access w and tell it to point to y (you want to have w ----> y). But you can't access w from x because it's simply linked! Thus you have to go through all your list to find w in O(n) operations, and then tell it to link to y. That's bad.

然后，假设你是双向链接：

Then, suppose you're doubly-linked :

v <---> w <---> x <---> y <---> z
                |
            you're here

酷，你可以访问W和Y从这里开始，这样你就可以连接两个（ W＆LT; - ＆GT; Y ）的O（1）操作！

Cool, you can access w and y from here, so you can connect the two (w <---> y) in O(1) operation!

这篇关于为什么删除使用双向链表哈希表的元素是O（1）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！