Почему AddAfter () имеет постоянное время?

Question

В операциях со связанным списком Addbefore (узел, ключ) имеет линейное время, т. Е. O (n), а AddAfter (узел, ключ) имеет постоянное время, т. Е. O (1).Кто-нибудь может сказать причину?

Answer 1

Представьте, как организован односвязный список:

A->B->C->D

Теперь представьте, что вы хотите добавить узел после B. Вы можете напрямую получить доступ к узлу и получить доступ к его указателю next для ссылки вновый узел.Поэтому, если вы создаете новый узел, называете его X, с помощью переданного ключа, вы можете сделать это:

Copy B's next pointer to X  // B and X both point to C
Set B's next pointer to X   // B points to X and X points to C

AddAfter(node,key)
{
    newNode = CreateNewNode(key);
    newNode.next = node.next;
    node.next = newNode;
}

Но если вы хотите добавить ранее, вы не знаете, какой узел придет до B. Таким образом, вы должны отсканировать список, чтобы выяснить:

AddBefore(node, key)
{
    parent = head;
    // find the node that points to the passed node
    while (parent.next != node)
    {
        parent = parent.next;
    }
    // Then add the new node after parent
    AddAfter(parent, key);
}

Это необязательно для двусвязного списка, поскольку каждый узел имеет указатель как на своего предшественника, так и на егопреемник.

Джим