One of the main advantage of using linked list data structure is that the list can be extended easily without re-allocating or moving any of the existing nodes. In this article we will go through different scenarios for extending a linked list by inserting a new node into the list.
For all the scenarios discussed in this article, linked list node is represented with the below structure:
And this is how the linked list is created before the insertion operation:
Insertion at the Beginning
Adding a new node at the beginning of a linked list involves creating a new node, setting its next pointer to the current head of the list, and then updating the head to point to the new node. Here’s the code snippet to add a new node at the beginning of the linked list:
If the list is initially empty, we also update the tail since both head and tail point to the newly created node.
Insertion at the End
Adding a new node at the beginning of a linked list involves creating a new node, setting the next pointer of the current tail node to the newly created node, and then updating the tail to point to the new node. Here’s the code snippet to add a new node at the end of the linked list:
If the list is empty, we just need to update both head and tail to point to the new node. Otherwise we append new node to the end of existing linked lists tail pointer.
Insertion after Specific Node
Inserting a new node after a specific node in a linked list involves updating pointers to place the new node between the given node and its next node. Here is the code snippet:
Insertion at a Specific Position
In order to insert a new node at a specific position position, we need to traverse the linked list to identify the node after which we need to add the new node. And then insert the new node similar to how we did in the previous scenario. Here’s the code snippet:
If the position is 0, we consider it similar to adding a new node at the beginning of linked list. Similarly if the position is greater than the total nodes in linked list, we consider it similar to adding a new node at the end of linked list. For all other cases, we need to insert the new node after the node at position-1.