Linked List Insertion

  1. Linked List Insertion Algorithm
  2. Linked List Insertion Illustration
  3. Linked List Insertion Implementation
  4. Linked List Insertion Algorithm Complexity

In this article, we will learn how to insert a node in a linked list. We can see that 4 different scenarios arise.

  1. We want to insert a node before the head of the linked list. This operation resembles the push operation in the stack.
  2. We want to insert a node at the end of the linked list i.e. next to the tail node.
  3. We want to insert a node at the i-th position of the linked list.
  4. We have the reference of the node, after which we want to insert the new node.

Linked List Insertion Algorithm

Let the head be the pointer to the first node of the linked list and let x be the data to be inserted into the linked list.

Insert Node at the Head of the Linked List push()

  • Create a new node temp with data x.
  • Set temp->next to head to insert temp before the head.
  • Set temp as the head of the linked list.

Insert Node at the End of the Linked List append()

  • Create a new node temp with data x.
  • Initialize tail pointing towards the head.
  • If the linked list is empty, set temp as head of the linked list and return.
  • Else iterate towards the end of the linked list, such that tail->next!= NULL, so that you land at the last element
  • Set tail->next as the temp.

Insert Node at the i-th Position of the Linked List insertNpos()

  • If position pos <= 0, return;
  • If pos == 0 and the head is empty, create a new node with data as x and set it as the head.
  • Else if pos == 1, call push().
  • Else, create a new node temp with data x.
  • Initialize curr pointing towards the head.
  • while pos--, do the following:
    • If pos == 1,

      • If curr is not NULL
        • Set temp->next as curr->next to insert temp after curr.
        • Set curr->next as the temp to connect curr to temp.
      • Return;
    • Else set curr as curr->next.

Insert Node Next to Reference of Given Node insertAfter()

  • if prev == NULL, return;
  • Create a new node curr with data x.
  • Point curr->next to prev->next to add new node after prev.
  • Point prev->next towards curr to complete the insertion.

Linked List Insertion Illustration

Assume that we have a node temp with a data value equal to 5 and we want to insert it in the linked list. Let us consider all 4 cases and illustrate how the above algorithms work.

Insert Node at the Head of the Linked List push()

  • Set temp'ss pointer towards the head.
  • Point head to temp.

Insert node at the head of the linked list

Insert Node at the End of the Linked List append()

  • Point curr towards the head with data as 2.
  • Set curr as curr->next and move it to the node with data 3.
  • Set curr as curr->next and move it to the node with data 4.
  • Exit the while loop and set curr->next as temp.

Insert node at the end of the linked list

Insert Node at the i-th Position of the Linked List insertNpos()

We will insert our node at position 3.

  • Point curr towards head with data as 1, pos = pos-1 = 2.
  • Set curr as curr->next and move it to node with data 3, pos = pos -1 = 1.
  • Set temp->next as curr->next to insert temp after curr.
  • Set curr->next as the temp to complete insertion of temp between curr and curr->next.

Insert node at the specific position of the linked list

Insert Node Next to Reference of Given Node insertAfter()

  • Set temp->next as prev->next to insert temp between prev and prev->next.
  • Set prev->next as the temp to complete the insertion.

Insert node next to reference of given node

Linked List Insertion Implementation

#include <bits/stdc++.h>
using namespace std;

class Node {
    public:
        int data;
        Node* next;
        Node(int x) {
            this->data = x;
            this->next = NULL;
        }
};

void push(Node** head, int x)
{
    Node* temp = new Node(x);
    temp->next = (*head);
    (*head) = temp;
}

void insertAfter(Node* prev, int x)
{
    if (prev == NULL) {
        return;
    }
    Node* curr = new Node(x);
    curr->next = prev->next;
    prev->next = curr;
}

void printList(Node* head)
{
    Node*curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
}
void insertNpos(Node**head, int x, int pos) {
    if (pos <= 0) {
        return;
    }
    if (!head && pos == 1) {
        *head = new Node(x);
    }
    else if (pos == 1) {
        push(head, x);
    }
    Node* temp = new Node(x);
    Node*curr = *head;
    while (pos--) {
        if (pos == 1) {
            if (curr) {
                temp->next = curr->next;
                curr->next = temp;
            }
            return;
        }
        curr = curr->next;
    }
}
void append(Node** head, int x)
{
    Node* temp = new Node(x);
    Node *tail = *head;
    if (*head == NULL)
    {
        *head = temp;
        return;
    }
    while (tail->next != NULL)
        tail = tail->next;
    tail->next = temp;
    return;
}

int main()
{
    Node* head = new Node(1);
    head -> next = new Node(2);
    printList(head); cout << "\n";
    push(&head, 3);
    push(&head, 4);
    printList(head); cout << "\n";
    append(&head, 5);
    printList(head); cout << "\n";
    insertAfter(head->next->next, 6);
    printList(head); cout << "\n";
    insertNpos(&head, 24, 2);
    printList(head);
    return 0;
}

Linked List Insertion Algorithm Complexity

Time Complexity

  • Average Case

To insert a node at the i-th position in the linked list, we have to visit i nodes. So, the time complexity is of the order of O(i). And we have n nodes in the linked list, so on the average-case time complexity is O(n/2) or O(n). The time complexity is of the order of O(n).

  • Best Case

The best-case occurs when we want to insert a node at the head of the linked list or we have the reference to the node before the site of insertion. The best-case time complexity is O(1).

  • Worst Case

The worst-case time complexity is O(n). It is the same average-case time complexity.

Space Complexity

This insertion algorithm’s space complexity is O(1) as no extra space other than curr pointer is required.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Data Structure

  • Linked List Deletion
  • Linked List Reversal
  • Related Article - Linked List

  • Convert Binary Tree to Binary Search Tree
  • Binary Search Tree