Insertion in Linked List

Modify a Linked List by inserting a new node at the front, after a specified node, and at the end. These operations offer flexibility in updating the structure based on specific needs, enabling dynamic adjustments to the Linked List.

Insertion at the Beginning of the Linked List

Insertion at the Beginning of the Linked List is also known as Insertion at Head. In this insertion type, the new node is inserted before the head of the Linked List and this new node that is inserted becomes the head of the Linked List. Consider a Linked List,

and we have to insert a node at the beginning with value 5, thus the updated Linked List will look like this,

Now let's follow the steps we discussed in the introduction section,

• We have drawn the Linked List before and after the insertion of the node.
• If we compare both the Linked List before and after the insertion we will find out that the next variable of node 5 has changed and the head is also changed from node 1 to node 5.

Since we are connecting node 5 and node 1, we have to ensure that we have the address of both nodes. We have the address of node 5 as we will create this node, but can you guess what is the address of node 1? Yes, you guessed it right the address of node 1 is stored in the variable head.

Steps to Insert a node at the Beginning of the Linked List are,

1. Create a new node.
2. Initialize the data of this new node.
3. Update the next variable of the new node as head.
4. Update the head as the new node.

Insertion at the End of the Linked List

Insertion at the End of the Linked List is also known as Insertion at Tail. In this insertion type, the new node is inserted after the tail of the Linked List and this new node becomes the tail of the Linked List. Consider a Linked List,

and we have to insert a node at the end with value 5, thus the updated Linked List will look like this,

Let's follow the common steps we discussed above,

• We have drawn the Linked List before and after the insertion of the node.
• If we compare both the Linked List before and after the insertion we will find out that the next variable of node 4 has changed.

Since we are connecting node 4 and node 5 we have to ensure that we have the address of both the nodes. We have the address of node 5 as we will create this node. But we don't have the address of node 4. For this let's see how we can identify node 4. Node 4 is the tail of the Linked List (Before Insertion), so the next variable of node 4 must be NULL. Now we can take a temp variable that will start from the head and will iterate over the Linked List. And when the next variable of temp is NULL we will stop iteration as the temp will be at the tail of Linked List. Steps to Insert a node at the End of the Linked List are,

1. Create a new node and initialize the data of this new node.
2. Create another node, temp with the value head.
3. Iterate over the Linked List while temp's next variable is not equal to NULL.
4. Now temp is at the tail of the Linked List and we have to just update the next variable of temp to the new node.
5. Also make sure to update the next variable of the new node as NULL.

Since we are iterating the linked list to take the temp node to tail of the linked list, therefore time complexity is O(N).

However, if we have the address of tail as temp then we can perform steps 4,5,6. Through this the time complexity will be O(1).

Adding a Node After a Given Node in the Linked List

This is the third and last type of insertion in the Linked List. We are given a node say x, and we have to insert a new node after x. Consider a Linked List,

And we have to insert a node with value 5, after node 2. So the updated Linked List will look like this,

Let's follow the common steps we discussed above,

• We have drawn the Linked List before and after the insertion of the node.
• If we compare both the Linked List before and after the insertion we will find out that the next variable of node 2 and node 5 has changed.

Since we are connecting node 2 with node 5 and node 5 with node 3 we need the address of node 2, node 5, and node 3. We have the address of node 5 as we will create this node. We also have the address of node 2 as x. But what is the address of node 3? The address of node 3 is stored in the next variable of x. Now we have the required addresses and we can move to the insertion process. Let's call node 2 as x and node 3 as y. So we have to insert node 5 between x and y.

Steps to Insert a node after a given node x in the Linked List are,

1. Create a new node.
2. Initialize the data of this new node.
3. Create another node, y with the value of x's next variable.
4. Update the next variable of x as the new node.
5. Update the next variable of the new node as y.

Example Program

Insertion at the Beginning of the Linked List

C++

Java

Python

Output:

Insertion at the End of the Linked List

C++

Java

Python

Output:

Adding a Node after a Given Node in the Linked List

Here x is the position of a node. Consider the linked list,

1st node is 1. So if x=1, the node 1 will be returned by generateX function. Similarly, if x = 3, the node 3 will be returned. C++

Java

Python

Output:

Using Constructor Call

In the above codes, you can observe that we are creating the node and then we are initializing the data to the node as,

But we can eliminate this using Constructor Call. We can declare a constructor in the Node class and this constructor will initialize the data and the next variable of the node. Let's see how we can initialize data and next variable to a node using a constructor call.

Now, all we have to do is pass the val and address to the Node() method and the constructor will initialize them to the node. Also, the default value of the address is NULL, so if we don't pass the address then the next variable of the node will be set as NULL.

Node With Value and NULL as Address of Next Node

Now the newNode has data as 5 and next as NULL. The time complexity of above operation is O(1).

Node With Value and Node x as Address of Next Node

Now the newNode has data as 5 and the next variable of newNode is x. The time complexity of above operations is O(1).