Data Structures — Various insertions scenarios in a Linked List
The previous article Linked List, shows how to implement a basic linked list that has a head pointer. We also implemented the insertion of nodes at the head of the list with a constant-time complexity of O(1).
Since we had access to the front of the list, we can immediately insert any new node into the list using its head pointer. Imagine if you have to do the insertion in the following scenario.
- Insert at a specific position.
- Insert after a specific node.
- Insert at the end of the list.
These are possible scenarios that you may need to implement into your basic linked list. Let's look at each of these scenarios and their implementations.
Insert at a specific position.
In an array, we can insert at a specific index. However, in a linked list, we only have access to the head pointer and the only way we can access a specific position in the list is by traversing the list from the head and keeping a count of how many nodes have we visited. Once we reached the position desired, then we can stop and implement insertion at that position.
Given this requirement, let's create a new method to implement insertion at a specific position. as shown in the code below, it accepts a parameter position, a zero-based index similar to an array, and the new node to insert.
Let's imagine some scenarios of what should happen when we call this function with specific position values and at different states of the linked list. Two states to consider are when the list is empty and when it's not empty.
InsertAtPosition(0, new Node(42))
InsertAtPosition(1, new Node(88))
On an empty list, since head is NULL, we should just use the existing Insert function that inserts the node at the head.
On a list that is not empty, we should traverse the list to find the position specified. Keep in mind that we also need to check at every visit during the traversal that the next node is not NULL. This check is important to make sure we don’t reach the go beyond the last node in the list.
In a real-world scenario, we cannot assume the position value given by the user is within the correct range for our list. So we would also need to make sure the value of the position parameter is valid.
To make this check we can add two validations in the method.
- position value should NOT be less than 0
- position should not be more than the size of the list
The first is easy, at the beginning of the function, if the position value is less than zero then do nothing.
The second validation is tricky. Since we don’t know the total size of the list, we need to check on each visit during the traversal to make sure the visiting pointer is not NULL before the insertion of the node.
Here is how the method looks after adding both validations discussed above.
Another way would be to keep track of the total size of the linked list by using a local variable in the class, called size. Increment and decrement that value on every insertion and removal of a node. This is not implemented in this tutorial.
Insert after a specific node.
This is similar to inserting at a specific position, but instead of searching for the position to insert, we have to traverse the list to find a specific node. Once we found the node, we can insert the new node at that position.
There is also a situation where you already have the reference to the node we are searching for. Let's implement insertion for this case first as this same method would be reused later. This is possible because the insertion code is the same, the only difference is either we have to search for the reference node or not.
The implementation to insert a new node after another node would be as follows. It looks similar to how we implemented the method to insert at the head. The difference is instead of using the head as the reference node, we are using the referenceNode provided.
Now that we have implemented the insertion after a reference node, let's look at how can we insert by searching for a node that has a reference value provided.
Using the same traversal routine as before, we start with the head and check if each visited node has the same value/content as the referenceValue provided. Once the node found, we can reuse the InsertAfter method we created above to insert the new node after the node we have found.
Insert at the end of the list.
Inserting at the end of the list needs the same traversal of each node from the head node up until the last node in the list. To determine the last node, remember that the last node of the list has its next pointer that does not point to anything so its value is NULL.
Another point to note is when the list is empty, no traversal would be needed, since the head = NULL. So we could reuse the Insert method we created previously in the Linked List article. When adding nodes to an empty list, add to the head or tail makes no difference.
The final implementation of inserting at the end of the list is as follows.
Traversal to the end of the list takes O(n) time but there is an efficient way yo reduce this to a constant O(1). When inserting a node at the head, we don’t have to do any traversal since we have the reference pointer to the first node. Similarly if we add pointer that always point to the last node in the list, we could also achive the insertion at tail without a traversal to the end of the list.
This tail pointer starts off to point to NULL, just like the head pointer when the list is empty. When the first node inserted into the list, both the head and the tail pointer would point to this first node. Things start to change when more nodes are added, the tail pointer maintains its pointer on the last node, while the head pointer on the first node.
So the insertion at the tail can be done similar to how you would insert after finding the last node in a traversal. But now, we don’t have to traverse since we already have a tail pointer always pointing to the last node in the list.
The full implementation of the linked list can be found in this Github repo:
