二重リンクリストの要素削除の時間計算量は？質問する

Question

二重リンクリストの場合、要素を削除するのに一定の時間がかかります。一度それがどこにあるかがわかれば。

単方向リンクリストの場合、要素がどこにあるかがわかれば、要素を削除するのにかかる時間は一定です。そしてその前身はです。

あなたが指しているリンクは、単方向リンクリストの削除をとしてO(n)、二重リンクリストの削除をとして示しているのでO(1)、削除したい要素がどこにあるかがすでにわかっている場合はとなることは確かですが、ない他に何か。

その場合、二重リンクリストの場合は、prevとnextポインターを使用してそれを削除し、を得ることができますO(1)。先頭または末尾にいるエッジケースを無視すると、次のようになります。

corpse->prev->next = corpse->next
corpse->next->prev = corpse->prev
free (corpse)

しかし、削除したいノードしか知らない単連結リストでは、corpse->prevその前のノードを取得するために使用することはできません。はリンクはありませんprev。

代わりに探す前の項目を削除するには、先頭からリストをトラバースして、next削除する要素のを持つ項目を探します。これにはが必要でO(n)、その後、実際の削除のためにもう一度が実行されますO(1)(ここでも、簡単にするためにエッジケースは無視します)。

lefty = head
while lefty->next != corpse:
    lefty = lefty-> next
lefty->next = corpse->next
free (corpse)

それはその記事ではなぜ 2 つの複雑さが異なるのか。

余談ですが、単方向リンクリストには削除を可能にする最適化がありますO(n)(削除したい項目とその前の項目が見つかったら、削除は実質的に O(1) になります)。コードで言えば、次のようになります。

# Delete a node, returns true if found, otherwise false.

def deleteItem(key):
    # Special cases (empty list and deleting head).

    if head == null: return false
    if head.data == key:
        curr = head
        head = head.next
        free curr
        return true

    # Search non-head part of list (so prev always exists).

    prev = head
    curr = head.next
    while curr != null:
        if curr.data == key:
            # Found it so delete (using prev).

            prev.next = curr.next
            free curr
            return true

        # Advance to next item.

        prev = curr
        curr = curr.next

    # Not found, so fail.

    return false

Answer 1