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

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.

• Recommended Problem - Reverse a Stack using Recursion

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!