March 30, 2008: Linked Lists: Inserting
Inserting a Node into a Linked List
As with delete, inserting nodes involves a special traversal. The two pointer method is also doable for this operation to keep track of the current node (marking where the insertion will take place) and the previous node we were at (to adjust its next node pointer and keep the linked list valid).
Since we’re searching for the spot to insert (perhaps specified by an existing node or an index), we start at head. For this example, we’ll insert a node before the tail.
Like before, we use a loop to search for the node. Updating of the pointers is done by first setting last_node to point to cur_node and then copying the value of cur_node’s next to cur_node.
Assuming we found the spot for the insertion, cur_node is looking at the node where we want to make the insertion while last is pointing to the previous one (the new node will
be added in between the two). Create the new node to add (pointed to by t here).
Now, adjust last’s next to point to the new node.
And set the new node’s next to point to cur_node.
We’re done. Again, care should be taken to correctly adjust the list’s pointers on special insertions.
