Table of contents

What is insertion into a linked list?

1. How to Insert a Node at the Front/Beginning of Linked List

2.1.

2.2.

C++

2.3.

Python

2.4.

2.5.

Java

2.6.

Javascript

2. How to Insert a Node after a Given Node in Linked List

3.1.

3.2.

C++

3.3.

3.4.

Java

3.5.

Python

3.6.

Javascript

3. How to Insert a Node at the End of Linked List

4.1.

4.2.

C++

4.3.

4.4.

Java

4.5.

Python

4.6.

Javascript

Approach to Insert a Node at a Specific Position

LinkedList Operations in Python, Java, C, and C++

6.1.

Python

6.2.

Java

6.3.

6.4.

C++

Frequently Asked Questions

7.1.

Where can insertion in a linked list be done from?

7.2.

Why is insertion easy in a linked list?

7.3.

Is insertion order maintained in LinkedList?

7.4.

How do you insert a linked list in order?

Conclusion

Last Updated: Aug 29, 2024

Medium

Insertion in Linked List

Author Vivek Tiwari

Adding a new node to the list at a specific position is known as Insertion in a linked list. Linked lists are a fundamental data structure consisting of nodes containing data and a reference (or pointer) to the next node in the sequence. It depends on where you want to insert a new node, there are several types of insertion operations in a linked list:

Insertion at the Beginning
Insert a Node after a Given Node in the Linked List
Insert a Node at the End of Linked List

In this blog, we will discuss a linked list problem that has been asked frequently in Interviews. The problem is to inserting in a linked list.

Let's start with a discussion on what linked lists are. A linked list is an ordered set of elements, each holding data and a link containing the address to the next element.

Try the Problem yourself before moving on to the solution.

What is insertion into a linked list?

Linked list insertion refers to the addition of a new element to a linked list data structure.

Example:

Original Linked List: A -> B -> C.

To insert "X" between nodes A and B we need to adjust the pointers such that after insertion we get A -> X -> B -> C

Also, read - Merge sort in linked list

Now let's understand how to insert Elements to a Linked List

You can add elements to either the beginning, middle or end of the linked list. Let us know about them in detail.

1. How to Insert a Node at the Front/Beginning of Linked List

To insert at the beginning of the linked list you can follow the the steps as mentioned below.

1. Create a new node with the new data.

2. Set the next pointer of the new node to point to the current head of the linked list.

3. Next update the head pointer to point to the new node, making it the new first node in the list.

To insert at the beginning of the linked list you can follow the the steps as mentioned below.
1. Create a new node with the new data.
2. Set the next pointer of the new node to point to the current head of the linked list.
3. Next update the head pointer to point to the new node, making it the new first node in the list.

// Insert at begin of LinkedList
struct node
{
int data;
node *next;
node(int x)
{
        data=x; // assigning value to data variable
        next=NULL; // initially next is NULL
}
};
node *insertbegin(node *head, int data)
{
node *temp = new node(data);
temp -> next = head;
return temp; 
}

C

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

void push(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}

int main() {
    struct Node* head = NULL;
    push(&head, 1);
    push(&head, 2);
    push(&head, 3);
    printList(head); // Output: 3 2 1
    return 0;
}

You can also try this code with Online C Compiler

Run Code

C++

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void push(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

void printList(Node* n) {
    while (n != NULL) {
        cout << n->data << " ";
        n = n->next;
    }
}

int main() {
    Node* head = nullptr;
    push(&head, 1);
    push(&head, 2);
    push(&head, 3);
    printList(head); // Output: 3 2 1
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Python

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

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

    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

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

if __name__ == '__main__':
    llist = LinkedList()
    llist.push(1)
    llist.push(2)
    llist.push(3)
    llist.printList()  # Output: 3 2 1

You can also try this code with Online Python Compiler

Run Code

C#

using System;

public class Node {
    public int data;
    public Node next;
    
    public Node(int d) {
        data = d;
        next = null;
    }
}

public class LinkedList {
    Node head;

    public void Push(int new_data) {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }

    public void PrintList() {
        Node n = head;
        while (n != null) {
            Console.Write(n.data + " ");
            n = n.next;
        }
    }

    static void Main(string[] args) {
        LinkedList llist = new LinkedList();
        llist.Push(1);
        llist.Push(2);
        llist.Push(3);
        llist.PrintList(); // Output: 3 2 1
    }
}

Java

class LinkedList {
    Node head;
    
    static class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    public void push(int new_data) {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }

    public void printList() {
        Node n = head;
        while (n != null) {
            System.out.print(n.data + " ");
            n = n.next;
        }
    }

    public static void main(String[] args) {
        LinkedList llist = new LinkedList();
        llist.push(1);
        llist.push(2);
        llist.push(3);
        llist.printList(); // Output: 3 2 1
    }
}

You can also try this code with Online Java Compiler

Run Code

Javascript

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
    }

    push(new_data) {
        let new_node = new Node(new_data);
        new_node.next = this.head;
        this.head = new_node;
    }

    printList() {
        let n = this.head;
        while (n != null) {
            console.log(n.data);
            n = n.next;
        }
    }
}

let llist = new LinkedList();
llist.push(1);
llist.push(2);
llist.push(3);
llist.printList(); // Output: 3 2 1

You can also try this code with Online Javascript Compiler

Run Code

2. How to Insert a Node after a Given Node in Linked List

The code given below inserts a new node with the specified data at the nth position in the linked list. It handles special cases for the first position, traverses to the (n-1)th node, performs the insertion, and returns the updated head of the list.

// Insert at nth position of LinkedList

node *insertpos(node *head, int position, int data)
{
node *temp = new node(data);

if(position == 1)
{
         temp -> next = head;
         return temp;
}

node *curr = head;

for(int i = 1;i <= position-2 && curr != NULL; i++)
{
         curr = curr -> next;
}

if(curr == NULL)
{
         return head;
}

//Insertion and returning head
temp -> next = curr -> next;
curr -> next = temp;
return head;
}

C

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

void insertAfter(struct Node* prev_node, int new_data) {
    if (prev_node == NULL) {
        printf("The given previous node cannot be NULL\n");
        return;
    }

    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = prev_node->next;
    prev_node->next = new_node;
}

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}

int main() {
    struct Node* head = NULL;
    struct Node* second = NULL;

    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    
    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = NULL;

    insertAfter(head, 3);
    printList(head); // Output: 1 3 2
    return 0;
}

You can also try this code with Online C Compiler

Run Code

C++

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void insertAfter(Node* prev_node, int new_data) {
    if (prev_node == nullptr) {
        cout << "The given previous node cannot be NULL\n";
        return;
    }

    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = prev_node->next;
    prev_node->next = new_node;
}

void printList(Node* n) {
    while (n != nullptr) {
        cout << n->data << " ";
        n = n->next;
    }
}

int main() {
    Node* head = new Node();
    Node* second = new Node();

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = nullptr;

    insertAfter(head, 3);
    printList(head); // Output: 1 3 2
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

C#

using System;

public class Node {
    public int data;
    public Node next;
    
    public Node(int d) {
        data = d;
        next = null;
    }
}

public class LinkedList {
    Node head;

    public void InsertAfter(Node prev_node, int new_data) {
        if (prev_node == null) {
            Console.WriteLine("The given previous node cannot be null");
            return;
        }

        Node new_node = new Node(new_data);
        new_node.next = prev_node.next;
        prev_node.next = new_node;
    }

    public void PrintList() {
        Node n = head;
        while (n != null) {
            Console.Write(n.data + " ");
            n = n.next;
        }
    }

    static void Main(string[] args) {
        LinkedList llist = new LinkedList();
        llist.head = new Node(1);
        Node second = new Node(2);
        llist.head.next = second;

        llist.InsertAfter(llist.head, 3);
        llist.PrintList(); // Output: 1 3 2
    }
}

Java

class LinkedList {
    Node head;
    
    static class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    public void insertAfter(Node prev_node, int new_data) {
        if (prev_node == null) {
            System.out.println("The given previous node cannot be NULL");
            return;
        }

        Node new_node = new Node(new_data);
        new_node.next = prev_node.next;
        prev_node.next = new_node;
    }

    public void printList() {
        Node n = head;
        while (n != null) {
            System.out.print(n.data + " ");
            n = n.next;
        }
    }

    public static void main(String[] args) {
        LinkedList llist = new LinkedList();
        llist.head = new Node(1);
        Node second = new Node(2);
        llist.head.next = second;

        llist.insertAfter(llist.head, 3);
        llist.printList(); // Output: 1 3 2
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

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

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

    def insertAfter(self, prev_node, new_data):
        if prev_node is None:
            print("The given previous node cannot be None.")
            return

        new_node = Node(new_data)
        new_node.next = prev_node.next
        prev_node.next = new_node

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

if __name__ == '__main__':
    llist = LinkedList()
    llist.head = Node(1)
    second = Node(2)
    llist.head.next = second

    llist.insertAfter(llist.head, 3)
    llist.printList()  # Output: 1 3 2

You can also try this code with Online Python Compiler

Run Code

Javascript

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
    }

    insertAfter(prev_node, new_data) {
        if (prev_node == null) {
            console.log("The given previous node cannot be null");
            return;
        }

        let new_node = new Node(new_data);
        new_node.next = prev_node.next;
        prev_node.next = new_node;
    }

    printList() {
        let current = this.head;
        while (current != null) {
            console.log(current.data);
            current = current.next;
        }
    }
}

let llist = new LinkedList();
llist.head = new Node(1);
let second = new Node(2);
llist.head.next = second;

llist.insertAfter(llist.head, 3);
llist.printList(); // Output: 1 3 2

You can also try this code with Online Javascript Compiler

Run Code

3. How to Insert a Node at the End of Linked List

The code given below inserts a new node with the desired data at the end of the linked list. It handles the case when the list is empty, traverses to the last node, performs the insertion, and returns the updated head of the list.

// insert at end of LinkedList
node *insertend(node *head, int data)
{
node *temp = new node(data);

if(head == NULL)
{
         return temp;
}

node *curr = head;

while(curr->next != NULL)
{
         curr = curr -> next;
}

curr -> next = temp;
temp -> next = NULL;
return head;
}

C

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

void append(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    struct Node *last = *head_ref;
    new_node->data = new_data;
    new_node->next = NULL;

    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }
    last->next = new_node;
}

void printList(struct Node *node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}

int main() {
    struct Node* head = NULL;
    append(&head, 1);
    append(&head, 2);
    append(&head, 3);
    printList(head); // Output: 1 2 3
    return 0;
}

You can also try this code with Online C Compiler

Run Code

C++

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void append(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    Node* last = *head_ref;
    new_node->data = new_data;
    new_node->next = NULL;

    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }
    last->next = new_node;
}

void printList(Node* node) {
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}

int main() {
    Node* head = NULL;
    append(&head, 1);
    append(&head, 2);
    append(&head, 3);
    printList(head); // Output: 1 2 3
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

C#

using System;

public class Node {
    public int data;
    public Node next;
    
    public Node(int d) {
        data = d;
        next = null;
    }
}

public class LinkedList {
    Node head;

    public void Append(int new_data) {
        Node new_node = new Node(new_data);
        if (head == null) {
            head = new_node;
            return;
        }

        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = new_node;
    }

    public void PrintList() {
        Node n = head;
        while (n != null) {
            Console.Write(n.data + " ");
            n = n.next;
        }
    }

    static void Main(string[] args) {
        LinkedList llist = new LinkedList();
        llist.Append(1);
        llist.Append(2);
        llist.Append(3);
        llist.PrintList(); // Output: 1 2 3
    }
}

Java

class LinkedList {
    Node head;
    
    static class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    public void append(int new_data) {
        Node new_node = new Node(new_data);
        if (head == null) {
            head = new_node;
            return;
        }

        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = new_node;
    }

    public void printList() {
        Node n = head;
        while (n != null) {
            System.out.print(n.data + " ");
            n = n.next;
        }
    }

    public static void main(String[] args) {
        LinkedList llist = new LinkedList();
        llist.append(1);
        llist.append(2);
        llist.append(3);
        llist.printList(); // Output: 1 2 3
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

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

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

    def append(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return

        last = self.head
        while last.next:
            last = last.next

        last.next = new_node

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

if __name__ == '__main__':
    llist = LinkedList()
    llist.append(1)
    llist.append(2)
    llist.append(3)
    llist.printList()  # Output: 1 2 3

You can also try this code with Online Python Compiler

Run Code

Javascript

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
    }

    append(new_data) {
        let new_node = new Node(new_data);
        if (this.head === null) {
            this.head = new_node;
            return;
        }

        let last = this.head;
        while (last.next !== null) {
            last = last.next;
        }

        last.next = new_node;
    }

    printList() {
        let current = this.head;
        while (current !== null) {
            console.log(current.data);
            current = current.next;
        }
    }
}

let llist = new LinkedList();
llist.append(1);
llist.append(2);
llist.append(3);
llist.printList(); // Output: 1 2 3

You can also try this code with Online Javascript Compiler

Run Code

Approach to Insert a Node at a Specific Position

Now, we will discuss the approach to Insert a node at a specific position in a linked list.

Declare the structure of the Node and write the function to create and return the node.

⬇

For inserting the Node, check whether the required position is valid.

⬇

Create a new Node

⬇

Traverse till the position asked.

⬇

Update the link

1)New Node should point to the old Node at the same position.

2) Change the pointer of the Node previous to the old Node to point to the new Node

Time Complexity = O(n). In the worst case, you have to traverse the whole LinkedList.

Until now, I assume you must have understood what has been asked in the problem statement. So, I strongly recommend you try it and solve some related problems on the linked list. Refer to this article for more problems, Some Commonly Asked Problems On Linked List. Don't be sad if you cannot solve how to Insert a node at a specific position in a linked list. This is part of the learning process.

Please have a look at the algorithm, and then again, you must give it a try.

LinkedList Operations in Python, Java, C, and C++

Python
Java
C
C++

Python

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

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

   def append(self, data):
       new_node = Node(data)
       if not self.head:
           self.head = new_node
           return
       last_node = self.head
       while last_node.next:
           last_node = last_node.next
       last_node.next = new_node

   def display(self):
       current = self.head
       while current:
           print(current.data, end=" ")
           current = current.next
       print()

# Example Usage
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.display()

You can also try this code with Online Python Compiler

Run Code

Java

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    public void append(int data) {
        Node new_node = new Node(data);
        if (head == null) {
            head = new_node;
            return;
        }
        Node last_node = head;
        while (last_node.next != null) {
            last_node = last_node.next;
        }
        last_node.next = new_node;
    }

    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

// Example Usage
public class Main {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.append(1);
        linkedList.append(2);
        linkedList.append(3);
        linkedList.display();
    }
}

You can also try this code with Online Java Compiler

Run Code

C

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

void append(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;
    new_node->data = new_data;
    new_node->next = NULL;
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
    while (last->next != NULL)
        last = last->next;
    last->next = new_node;
}

void display(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

// Example Usage
int main() {
    struct Node* head = NULL;
    append(&head, 1);
    append(&head, 2);
    append(&head, 3);
    display(head);
    return 0;
}

You can also try this code with Online C Compiler

Run Code

C++

#include <iostream>

class Node {
public:
    int data;
    Node* next;

    Node(int data) {
        this->data = data;
        this->next = nullptr;
    }
};

class LinkedList {
public:
    Node* head = nullptr;

    void append(int data) {
        Node* new_node = new Node(data);
        if (head == nullptr) {
            head = new_node;
            return;
        }
        Node* last_node = head;
        while (last_node->next != nullptr) {
            last_node = last_node->next;
        }
        last_node->next = new_node;
    }

    void display() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

// Example Usage
int main() {
    LinkedList linkedList;
    linkedList.append(1);
    linkedList.append(2);
    linkedList.append(3);
    linkedList.display();
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

1 2 3

Frequently Asked Questions

Where can insertion in a linked list be done from?

Insertion in a linked list can be done from any node because each node in the linked list contains a reference to its next node. So its easy to find node and attach a node next to it.

Why is insertion easy in a linked list?

Insertion is easy in a linked list because there is no need to shift any of the existing nodes in the list. We simply update the next pointer of the previous node to point to the new node.

Is insertion order maintained in LinkedList?

Yes, the insertion order is maintained in a linked list. This is because the next pointer of each node point to its next node in the list, so the order of the nodes remains the same.

How do you insert a linked list in order?

To insert a node into a sorted linked list, traverse the list to find the correct position where the node's value is less than or equal to the next node. Insert the new node at this position, ensuring the list remains ordered.

Conclusion

This article taught us about Insertion in Linked List. We discussed its implementation using illustrations, pseudocode, and then proper code. We hope you can take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the recursive pattern followed in most linked list problems. You can have a look at these articles for more understanding.

For a strong hold on problem-solving. You can practice these problems.

Check out The Interview Guide for Product Based Companies and some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc., on CodE360. Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Live masterclass

IIT Certification: Key to Success in Data Analytics?

by Coding Ninjas

14 Jan, 2025

01:30 PM

8+ registered

Amazon PowerBI essentials: Data Analyst tips for visualization

by Abhishek Soni, Data Scientist @ Amazon

13 Jan, 2025

01:30 PM

1130+ registered

IIT Certification: Key to Success in Full Stack Development?

by Coding Ninjas

13 Jan, 2025

03:30 PM

392+ registered

IIT Certification: Key to Success in Data Analytics?

by Coding Ninjas

14 Jan, 2025

01:30 PM

8+ registered

Amazon PowerBI essentials: Data Analyst tips for visualization

by Abhishek Soni, Data Scientist @ Amazon

13 Jan, 2025

01:30 PM

1130+ registered

View more events