在CLRS的教科书"算法导论"中,有关于pg的这一段.258.
如果列表是双重链接,我们可以在O(1)时间内删除一个元素.(注意,CHAINED-HASH-DELETE将元素x作为输入而不是其键k,因此我们不必首先搜索x.如果哈希表支持删除,则其链表应该双重链接,以便我们可以快速删除一个项目.如果列表只是单链接,那么要删除元素x,我们首先必须在列表中找到x,以便我们可以更新x的前一个属性的下一个属性.使用单链表,两个都删除并且搜索将具有相同的渐近运行时间).
让我感到困惑的是这个大家伙,我无法理解它的逻辑.有了双链表,还是要找到x才能删除它,这与单链表有什么不同？请帮我理解一下!