Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
4.
Approach
5.
C++ Implementation
6.
Complexities
6.1.
Time Complexity
6.2.
Space Complexity
7.
Frequently Asked Questions
8.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Insert a Node in a Singly Linked List at a given Position using Recursion

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

A Linked List is one of the essential linear data structures. Its supremacy over arrays is that a linked list can be as long as we want. But this feature comes at a cost. To insert a value at the end of a linked list, we need to traverse the whole linked list, which increases our cost of insertion. 

This article will discuss three ways a node can be inserted into a Linked List. They are:

  • At the front of the linked list.
  • At the rear end of the linked list.
  • At any random position in between the linked list.


This article requires basic knowledge of Linked List and Recursion Readers may increase their knowledge on the same by visiting CN Library | Free Online Coding Resources

Problem Statement

You have been provided with a linked list, a node, and the position. Your task is to insert the given node at the given position.

For the positions, the numbering starts from 1.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example

Sample Input: Linked List = [10, 20, 30, 40, 50], node = 41, pos = 3.

Expected Output: [10, 20, 41, 30, 40, 50].

Approach

It is clear from the problem statement that the insertion can be done at three different positions, that is:

  • At the front of the linked list.
  • At the rear end of the linked list.
  • At a random position in between the linked list.


Inserting a node in the front and rear is an easy task as we don’t need to move the linked list elements. Inserting a node at a random position is a bit tedious. The three insertion methods are as follows.

  1. To insert a node at the front of the Linked List.
  • Create a function (say insertFront()) that takes the head pointer of the linked list and the node (say x) to be inserted as function arguments.
  • Create a temporary node (say temp) that points to the head of the linked list. 
  • Insert the node temp before the current head node. That is, make the new node point to temp.
  • Finally, make the new node the new head. 
  • Create a temporary node (say temp) that points to the head of the linked list.
     

 2. To insert a node at the rear end of the Linked List.

  • Create a function (say insertRear()) that takes the head node pointer and the new node as function arguments. The function recursively traverses to the last node and inserts the new node.
  • The base is when the head pointer points to NULL. 
    • In that case, make the head pointer point to the new node.
    • Return the head pointer.
  • Else, call the function insertRear() for head->next.
  • Return the head pointer after the recursive step.
     

3. To insert a node at the given position in the Linked List. 

  • This case is somewhat similar to inserting at the end of the linked list. We will recursively traverse to the desired position and insert the new node there. The only difference is that we need the new node to point to the next node rather than pointing to null.
  • To do the desired task, create a function (say insertRandom()) that takes the head pointer, the new node, and the position as the function argument. 
  • The base case of this function is when the value of the position variable is 2.
    • In that case, check if the head pointer points to NULL or not.
      • If it does not point then, make the new node point to the node after the current head node, that is, newNode->next = currHead->next.
      • Then make the current head point to the new node.
      • The key point to remember is to change the address pointer of the new node and then the head node. If the reverse is done (that is, we point to the new node first) then the address of the next node is lost forever. This is not a desirable situation.
  • If the head node points to null, that means the value of the position variable is more than the length of our linked list.
    • In that case, return the head node.
  • In the recursive step, call insertRandom() for head->next, and decrement the value of the position variable by one. 
  • Finally, return the head pointer.
     

To see our linked list, we also make a printing function named displayLL(). In the function, we recursively traverse the linked list and print the value of the head node.

C++ Implementation

#include <iostream>
using namespace std;

struct nodeLL {
    int data;
    nodeLL* next;

    nodeLL(int data, nodeLL* next)
    {
        this->data = data;
        (*this).next = next;
    }
};

nodeLL* insertFront(nodeLL*& llHead, nodeLL* x)
{
    nodeLL* temp = llHead;
    x->next = temp;
    llHead = temp = x;
    return temp;
}

nodeLL* insertRear(nodeLL* llHead, nodeLL* x)
{
    if (llHead->next == NULL) {
        llHead->next = x;
        return llHead;
    }
    llHead->next = insertRear(llHead->next, x);
    return llHead;
}

nodeLL* insertRandom(nodeLL* llHead, nodeLL* x, int pos)
{
    if (pos == 2) {
        if (llHead != NULL) {
            x->next = llHead->next;
            llHead->next = x;
        }
        return llHead;
    }
    if (llHead == NULL) {
        return llHead;
    }
    llHead->next = insertRandom(llHead->next, x, --pos);
    return llHead;
}

void displayLL(nodeLL* head)
{
    if (head == NULL) {
        return;
    }
    cout << head->data << " ";
    displayLL(head->next);
}

int main()
{
    nodeLL* llhead = new nodeLL(10, 0);

    for (int i = 20; i < 101; i+=10)
        insertRear(llhead, new nodeLL(i, 0));

    cout << "Before Changes: " ;
    displayLL(llhead);
    cout << endl;

    insertRandom(llhead, new nodeLL(85, 0), 9);
    insertRandom(llhead, new nodeLL(61, 0), 7);
    insertRandom(llhead, new nodeLL(102, 0), 200);
    insertFront(llhead, new nodeLL(9, 0));
    insertRear(llhead, new nodeLL(101, 0));

    cout << "After Changes: " ;
    displayLL(llhead) ;
    return 0;
}

 

OUTPUT

Before Changes: 10 20 30 40 50 60 70 80 90 100
After Changes: 9 10 20 30 40 50 60 61 70 80 85 90 100 101

Complexities

Time Complexity

In the given implementation, in the worst case, we have to traverse the entire linked list to insert a new node if we want the node to be inserted at the end. Thus the time complexity comes out to be,

T(n) = O(n),

where n is the size of the linked list.

Space Complexity

We use auxiliary space for the recursion stack in the given implementation. Thus,

Space complexity = O(n),

where n is the size of the linked list.

Must Read Recursion in Data Structure

Frequently Asked Questions

  1. What is a Linked List? 
    A linked list is a linear data structure of variable length. A linked list is made up of nodes, where each node contains two things- the data of that node and the address of the next node. To learn more about linked lists visit, Linked List
     
  2. What is the benefit of using a Linked List?
    Linked lists are preferred over static arrays when the number of elements to be stored is unknown. 

Key Takeaways

To summarize the article, we discussed how to insert a node in a singly linked list at a given position using Recursion. We first saw the problem statement, an example, the approach, and its C++ implementation. After discussing the time and the space complexities, we saw a few FAQs.


Want to know more about Data Structures and Algorithms? Visit Data Structures and Algorithms | Learn & Practice from Coding Ninjas Studio to read many interesting articles.
Want to learn about topics like Web Technologies, Programing Fundamentals, Aptitude, DSA, and much more? Visit CN Library | Free Online Coding Resources today. 

 

Happy Coding!

Previous article
Tail Recursion
Next article
Different Ways to Add Parentheses
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass