Linked Lists - 2 (Insertion)
Insertion
Insertion to Head of List
List-Insert-Head(L,node)
node.next = head
node.prev = NIL
if head =/= NIL then
head.prev = node
else // list was empty
tail = node
head = node
Insertion to Tail of List
List-Insert-Tail(L,node)
node.next = NIL
node.prev = tail
if tail =/= NIL then
tail.next = node
else // list was empty
head = node
tail = node
Insertion in Middle
Suppose we want to insert a node after a node pointed to by curr.
# assume that curr is pointing to a node
List-Insert(L,curr,node)
node.next = curr.next
node.prev = curr
curr.next.prev = node # points to new position from old next
curr.next = node # point to new position from prev
This will not work if curr is at any end.
Time Complexity
The time complexity of:
- inserting to the head/tail of doubly linked list is $O(1)$.
- inserting to the head of singly linked list is $O(1)$.
- inserting to the tail of singly linked list is $O(n)$.
- You may have to traverse the list if you don’t have an extra pointer for the last element in the list. If you do then it is $O(1)$
- inserting in a sorted doubly linked list is $O(n)$.
- You have to search through the entire list in the worst case. The insertion is only $O(1)$.