data-structureslinked-list

Why AddAfter() has constant time?


In linked list operations, Addbefore(node,key) has linear time i.e., O(n) but AddAfter(node,key) has constant time i.e., O(1). Can anyone tell the reason?


Solution

  • Picture how a singly-linked list is organized:

    A->B->C->D
    

    Now, imagine you want to add a node after B. You can directly access the node and access its next pointer to link in a new node. So if you create a new node, call it X, with the passed key, you can do this:

    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;
    }
    

    But if you want to add before, you don't know which node comes before B. So you have to scan the list to find out:

    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);
    }
    

    That's not necessary with a doubly-linked list, because each node has a pointer to its predecessor as well as to its successor.