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 node5 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 the 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++

#include <bits/stdc++.h>
using namespace std;
class Node 
{ 
    public:
    int data; 
    Node *next; 
}; 
void print(Node *head){
    while(head){
        cout<<head->data<<" ";
        head = head->next;
    }
    return;
}
void insertAtBeginning(int val, Node *&head){
    if(head==NULL){
        //Inserting First Node in the Linked List
        head = new Node();
        head->data = val;
    }else{
        //Creating New Node
        Node *newNode = new Node();    
        //Updating data of newNode
        newNode->data = val;
        //Updating the next variable of newNode as head
        newNode->next = head;
        //Updating newNode as head
        head = newNode;
    }
    return;
}
int main() {
    Node *head = NULL;
    insertAtBeginning(4,head);
    insertAtBeginning(3,head);
    insertAtBeginning(2,head);
    insertAtBeginning(1,head);

    //Inserting 5 at the Beginning of the Linked List
    insertAtBeginning(5,head);

    //Printing the Linked List
    print(head);
    return 0;
}

Java

class LinkedList {
    //Head of the Linked List
    Node head;    
    static class Node {
        int data;
        Node next;
    }
    public static void print(LinkedList list){
        Node temp = list.head;
        while(temp != null){
            System.out.print(temp.data+" ");
            temp = temp.next;
        }
        return;    
    }
    public void insertAtBeginning(int val){
        if(head==null){
            //Inserting First Node in the Linked List
            head = new Node();
            head.data = val;
        }else{
            //Creating New Node
            Node newNode = new Node();    
            //Updating data of newNode
            newNode.data = val;
            //Updating the next variable of newNode as head
            newNode.next = head;
            //Updating newNode as head
            head = newNode;   
        }
        return;
    }
}

class Main{
    public static void main(String args[]) {
        LinkedList list = new LinkedList();
        list.insertAtBeginning(4);
        list.insertAtBeginning(3);
        list.insertAtBeginning(2);
        list.insertAtBeginning(1);

        //Inserting 5 at the beginning of the Linked List
        list.insertAtBeginning(5);

        //Printing the Linked List
        list.print(list);    
    }
}

Python

class Node:
    # Constructor
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self): 
        self.head = None

    def print(self):
        temp = self.head
        while temp is not None:
            print(temp.data,end = " ")
            temp = temp.next

    def insertAtBeginning(self, val):
        if self.head == None:
            # Inserting First Node in the Linked List
            self.head = Node(val)
        else:
            # Creating New Node
            newNode = Node(val)
            # Updating the next variable of newNode as head
            newNode.next = self.head
            # Updating newNode as head
            self.head = newNode

list = LinkedList()
list.insertAtBeginning(4)
list.insertAtBeginning(3)
list.insertAtBeginning(2)
list.insertAtBeginning(1)

# Inserting 5 at the beginning of the Linked List
list.insertAtBeginning(5)

# Printing the Linked List
list.print()

Output:

5 1 2 3 4 

Insertion at the End of the Linked List

C++

#include <bits/stdc++.h>
using namespace std;
class Node 
{ 
    public:
    int data; 
    Node *next; 
}; 
void print(Node *head){
    while(head){
        cout<<head->data<<" ";
        head = head->next;
    }
    return;
}
void insertAtEnd(int val, Node *&head){
    if(head==NULL){
        //Inserting First Node in the Linked List
        head = new Node();
        head->data = val;
    }else{
        //Creating New Node
        Node *newNode = new Node();    
        //Updating data of newNode
        newNode->data = val;
        //Creating a temp node to iterate over Linked List so that head is not changed
        Node *temp = head;
        //Iterating till the `next` variable of temp is not equal to NULL
        while(temp->next!=NULL){
            temp = temp->next;
        }
        //Temp is at tail of the Linked List
        temp->next = newNode;
        //Updating `next` variable of newNode as NULL
        newNode->next = NULL;        

    }
    return;
}
int main() {
    Node *head = NULL;
    insertAtEnd(1,head);
    insertAtEnd(2,head);
    insertAtEnd(3,head);
    insertAtEnd(4,head);

    //Inserting 5 at the End of the Linked List
    insertAtEnd(5,head);

    //Printing the Linked List
    print(head);
    return 0;
}

Java

class LinkedList {
    //Head of the Linked List
    Node head;    
    static class Node {
        int data;
        Node next;
    }
    public static void print(LinkedList list){
        Node temp = list.head;
        while(temp != null){
            System.out.print(temp.data+" ");
            temp = temp.next;
        }
        return;    
    }
    public void insertAtEnd(int val){
        if(head==null){
            //Inserting First Node in the Linked List
            head = new Node();
            head.data = val;
        }else{
            //Creating New Node
            Node newNode = new Node();    
            //Updating data of newNode
            newNode.data = val;
            //Creating a temp node to iterate over Linked List so that head is not changed
            Node temp = head;
            //Iterating till the `next` variable of temp is not equal to NULL
            while(temp.next!=null){
                temp = temp.next;
            }
            //Temp is at tail of the Linked List
            temp.next = newNode;
            //Updating `next` variable of newNode as NULL
            newNode.next = null;  
        }
        return;
    }
}

public class Main{
    public static void main(String args[]) {
        LinkedList list = new LinkedList();
        list.insertAtEnd(1);
        list.insertAtEnd(2);
        list.insertAtEnd(3);
        list.insertAtEnd(4);

        //Inserting 5 at the End of the Linked List
        list.insertAtEnd(5);

        //Printing the Linked List
        list.print(list);    
    }
}

Python

class Node:
    # Constructor
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self): 
        self.head = None

    def print(self):
        temp = self.head
        while temp is not None:
            print(temp.data,end = " ")
            temp = temp.next

    def insertAtEnd(self, val):
        if self.head == None:
            # Inserting First Node in the Linked List
            self.head = Node(val)
        else:
            # Creating New Node
            newNode = Node(val)
            # Updating the `next` variable of newNode as head
            newNode.next = self.head
            # Creating a temp node to iterate over Linked List so that head is not changed
            temp = self.head
            # Iterating till the `next` variable of temp is not equal to None
            while temp.next is not None:
                temp = temp.next
            # Temp is at tail of the Linked List
            temp.next = newNode;
            # Updating `next` variable of newNode as None
            newNode.next = None;

list = LinkedList()
list.insertAtEnd(1)
list.insertAtEnd(2)
list.insertAtEnd(3)
list.insertAtEnd(4)

# Inserting 5 at the End of the Linked List
list.insertAtEnd(5)

# Printing the Linked List
list.print()

Output:

1 2 3 4 5 

Adding a Node after a Given Node in the Linked List

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

1->2->3->4->NULL

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++

#include <bits/stdc++.h>
using namespace std;
class Node 
{ 
    public:
    int data; 
    Node *next; 
}; 
void print(Node *head){
    while(head){
        cout<<head->data<<" ";
        head = head->next;
    }
    return;
}
void insertAtEnd(int val, Node *&head){
    if(head==NULL){
        //Inserting First Node in the Linked List
        head = new Node();
        head->data = val;
    }else{
        //Creating New Node
        Node *newNode = new Node();    
        //Updating data of newNode
        newNode->data = val;
        //Creating a temp node to iterate over Linked List
        Node *temp = head;
        //Iterating till the `next` variable of temp is not equal to NULL
        while(temp->next!=NULL){
            temp = temp->next;
        }
        //Temp is at tail of the Linked List
        temp->next = newNode;
        //Updating `next` variable of newNode as NULL
        newNode->next = NULL;        

    }
    return;
}
//Function to return the address of x'th Node
Node *generateX(Node *head,int pos){
    //If the Linked List is empty return NULL
    if(head==NULL) return head;

    int cnt = 1;
    Node *x = NULL;
    while(head!=NULL){
        if(cnt==pos){
            //If the count is equal to pos store the address of head and break the iteration 
            x = head;
            break;
        }
        cnt++;
        head = head->next;
    }
    return x;

}
int main() {
    Node *head = NULL;
    insertAtEnd(1,head);
    insertAtEnd(2,head);
    insertAtEnd(3,head);
    insertAtEnd(4,head);

    //Creating New Node
    Node *newNode = new Node();    
    //Updating data of newNode
    newNode->data = 5;
    //Generating the Address of x'th Node
    Node *x = generateX(head,2);
    //Storing the Address of y'th Node
    Node *y = x->next;

    //Updating the `next` variable of x as newNode
    x->next = newNode;
    //Updating the `next` variable of newNode as y
    newNode->next = y;

    //Printing the Linked List
    print(head);
    return 0;
}

Java

class Node {
    int data;
    Node next;
}

class LinkedList {
    //Head of the Linked List
    Node head;    
    public static void print(LinkedList list){
        Node temp = list.head;
        while(temp != null){
            System.out.print(temp.data+" ");
            temp = temp.next;
        }
        return;    
    }
    public void insertAtEnd(int val){
        if(head==null){
            //Inserting First Node in the Linked List
            head = new Node();
            head.data = val;
        }else{
            //Creating New Node
            Node newNode = new Node();    
            //Updating data of newNode
            newNode.data = val;
            //Creating a temp node to iterate over Linked List
            Node temp = head;
            //Iterating till the `next` variable of temp is not equal to NULL
            while(temp.next!=null){
                temp = temp.next;
            }
            //Temp is at the tail of the Linked List
            temp.next = newNode;
            //Updating the` next` variable of newNode as NULL
            newNode.next = null;  
        }
        return;
    }
    public Node generateX(int pos){
        //If the Linked List is empty return NULL
        if(head==null) return head;

        int cnt = 1;
        Node x = null, temp = head;
        while(temp!=null){
            if(cnt==pos){
                //If the count is equal to pos store the address of the head and break the iteration
                x = temp;
                break;
            }
            cnt++;
            temp = temp.next;
        }
        return x;
    }
}

class Main{
    public static void main(String args[]) {
        LinkedList list = new LinkedList();
        list.insertAtEnd(1);
        list.insertAtEnd(2);
        list.insertAtEnd(3);
        list.insertAtEnd(4);

        //Creating New Node
        Node newNode = new Node();    
        //Updating data of newNode
        newNode.data = 5;
        //Generating the Address of x'th Node
        Node x = list.generateX(2);
        //Storing the Address of the Node
        Node y = x.next;

        //Updating the `next` variable of x as newNode
        x.next = newNode;
        //Updating the `next` variable of newNode as y
        newNode.next = y;

        //Printing the Linked List
        list.print(list);    
    }
}

Python

class Node:
    # Constructor
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self): 
        self.head = None

    def print(self):
        temp = self.head
        while temp is not None:
            print(temp.data,end = " ")
            temp = temp.next

    def insertAtEnd(self, val):
        if self.head == None:
            # Inserting First Node in the Linked List
            self.head = Node(val)
        else:
            # Creating New Node
            newNode = Node(val)
            # Updating the `next` variable of newNode as head
            newNode.next = self.head
            # Creating a temp node to iterate over Linked List
            temp = self.head
            # Iterating till the `next` variable of temp is not equal to None
            while temp.next is not None:
                temp = temp.next
            # Temp is at tail of the Linked List
            temp.next = newNode;
            # Updating `next` variable of newNode as None
            newNode.next = None;
    def generateX(self,pos):
        # If the Linked List is empty return None
        if self.head == None:
            return self.head

        cnt = 1
        x = None
        temp = self.head
        while temp is not None:
            if cnt == pos:
                # If the count is equal to pos store the address of head and break the iteration
                x = temp
                break
            cnt+=1
            temp = temp.next
        return x

list = LinkedList()
list.insertAtEnd(1)
list.insertAtEnd(2)
list.insertAtEnd(3)
list.insertAtEnd(4)

# Creating New Node
newNode = Node(5);    
# Generating the Address of x'th Node
x = list.generateX(2);
# Storing the Address of y'th Node
y = x.next;

# Updating the `next` variable of x as newNode
x.next = newNode;
# Updating the `next` variable of newNode as y
newNode.next = y;

# Printing the Linked List
list.print()

Output:

1 2 5 3 4 

:::
:::section{.main}

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,

//Creating New Node
Node *newNode = new Node();    
//Updating data of newNode
newNode->data = val;

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.

class Node 
{ 
    public:
    int data; 
    Node *next; 
    //Constructor
    Node(int val,Node *address = NULL){
        data = val;
        next = address;
    }
};

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

Node *newNode = new Node(5);

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

Node *x = new Node(6);
Node *newNode = new Node(5,x);

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

Conclusion

• Linked List is a linear data structure that stores elements in non-contiguous memory locations.
• Insertion in Linked List can be divided into three cases, Insert Node in Linked List at the Beginning, Insert Node in Linked List at the End, and Insert Node in Linked List after a given Node.
• There are some common steps that are important when we insert a node in Linked List, these are
  • Draw the Linked List before and after insertion of the node.
  • Identify the nodes whose next variable is changed and also identify the variables that have been changed in the insertion process.
  • Update the next variable of the required nodes and also update the required variables.