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?
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.