Linked List Insertion
Insertion is one of the operations where linked lists shine compared to arrays, because no elements need to be shifted. However, the exact cost and procedu...
Adding Nodes at the Head, Tail, and Middle of a Linked List
Insertion is one of the operations where linked lists shine compared to arrays, because no elements need to be shifted. However, the exact cost and procedure differ depending on where in the list the new node is inserted, and whether the list implementation maintains certain pointers like a tail pointer.
Inserting at the head is always O(1). Create a new node, set new_node.next to the current head, and update head to new_node. If the list is doubly linked, also set the old head's prev to new_node. If the list was empty, tail (if maintained) also becomes new_node.
Inserting at the tail is O(1) only if a tail pointer is maintained. With a tail pointer: create new_node, set tail.next to new_node, update tail to new_node. Without a tail pointer, you must traverse from head to the last node (the one whose next is null) in O(n), then append.
Inserting at a specific position k requires traversing to the (k-1)-th node in O(k) time, then performing three pointer changes: new_node.next equals current.next, current.next equals new_node, and if doubly linked, new_node.next.prev equals new_node and new_node.prev equals current. This is O(n) in the worst case.
Inserting in sorted order maintains the list in ascending order of values. Start from the head, traverse until finding the first node whose value exceeds the new value, and insert the new node before it. This requires O(n) traversal but only O(1) pointer adjustments once the position is found.
Edge cases to handle carefully: inserting into an empty list (head and tail both null), inserting before the head, inserting after the tail, and inserting at a position beyond the current length (should either append to the tail or raise an error).
Insertion using the dummy head technique eliminates special casing. A permanent dummy node before the actual first element means every insertion, including at position zero, uses the same code: traverse to the node before the insertion point (starting from dummy), then link in the new node.
Worked example: insert the value 42 into a singly linked list that is sorted in ascending order and currently contains [10, 25, 60, 80]. Traverse: 10 is less than 42, 25 is less than 42, 60 is greater than 42. Insert the new node between 25 and 60 by setting new_node.next to the node holding 60 and the node holding 25's next to new_node. Result: [10, 25, 42, 60, 80].
Interview tip: always draw the pointer diagram when explaining linked list insertion. Verbal descriptions of pointer adjustments are easy to misunderstand; a small diagram makes the algorithm unambiguous.