Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Insert a Node at a Specific Position in a Linked List

Linked lists are a dynamic linear data structure used in various real-life applications. It is important to know how to insert at any position in the linked list. Here we will learn in detail how to insert a node at a specific position in a linked list in C.

How to Insert a Node at a Specific Position in a Linked List in C?

The problem is quite simple. We just have to insert a node at a specific position in a linked list in C. Here is an example to understand what is meant by to insert a node at a specific position in a linked list.

Example :

Input:

list = 1β†’2β†’3β†’4β†’5, 
          data = 6
          position = 2

Output:

1 β†’ 6 β†’ 2β†’ 3 β†’ 4 β†’ 5

Explanation:
Suppose the given list is 1 β†’ 2 β†’ 3 β†’ 4 β†’ 5, position = 2, and the data to be inserted is 6.

  • According to the problem statement, we need to insert a node with value = 6 at 2nd position in the linked list.
  • So, after adding the node with value = 6 at the 2nd position in the given linked list, our resultant list will be 1 β†’ 6 β†’ 2β†’ 3 β†’ 4 β†’ 5.

Now the problem statement is clear. So, now the main question is how we should approach this problem. What is the first thing that comes to mind when we talk about insertion at a specific position in a linked list?

  • List traversal, right? Yes. We are going to use list traversal for insertion at a specific position in a linked list.

Before moving further to the approach section, try to think of the approach by yourself.

  • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach to Insert a Node at a Specific Position in a Linked List in C

Our approach to insert at any position in linked list is going to be pretty simple. Here is our approach.

  • We will simply traverse till (position -1)th node and add the newnode just after that node. Well, how will this work? Let us take an example.
    • Suppose the list is 1 β†’ 2 β†’ 3, and we have to insert 4 at the 2nd position.
    • Now, we will traverse (position -1) = (2-1) = 1 node and after traversing 1 node, we will be standing at 1.
    • Now we will make 4 β†’ next = 1 β†’ next as we have to insert it after 1, and finally, 1 β†’ next = 4 to link the nodes.
    • By doing the above steps, 4 will be added at that specific position, and our resultant linked list will be: 1 β†’ 4 β†’ 2 β†’ 3.

We can get a clearer look at the approach by looking at the dry run.

Algorithm to Insert a Node at a Specific Position in a Linked List in C

The algorithm to insert a node at a specific position in a linked list is given below.

  • If the position where we are asked to insert pos is smaller than 1 or greater than the size of the list, it is invalid, and we will return.
  • Else, we will make a variable curr and make it point to the head of the list.
  • Now we will run a for loop using curr to reach to the node at (pos-1)th position:
    • The for loop will be: for(int i=1;inext;}
    • After the termination of the above loop, curr will be standing at the (position – 1)th node.
    • As explained above, we will simply make newnode β†’ next = curr β†’ next and curr β†’ next = newnode.
  • If the pos was equal to 1, we will make the head point to newnode as newnode will become the first node of the list.

Dry Run to Insert a Node at a Specific Position in a Linked List in C

Code to Insert a Node at a Specific Position in a Linked List in C

Here is the code implementation for how to insert a node at a specific position in a linked list in C, C++, Java, and Python.
n.

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

struct Node {
    int data;
    struct Node* next;
};
int size = 0;
// Using this function we will be creating new nodes
struct Node* getNode(int data)
{
   struct Node* newNode
= (struct Node*)malloc(
sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
// Using this function we will insert the newnode at the specific position
void insertAtPosition(struct Node* head, int pos, int data)
{
    if (pos < 1 || pos > size + 1)
        printf( "Invalid position!\n" );
    else {
       struct Node *curr=head;
        for(int i=1;i<pos-1;i++) curr="curr-">next;
        struct Node* temp=getNode(data);
        temp->next=curr->next;
        curr->next=temp;
        if(pos=1)
        head=temp;
        size++;
    }
}
// Using this function we will print the linked list
void printList(struct Node* head)
{
    while (head != NULL) {
        printf("%d ",head->data);
        head = head->next;
    }
    printf("\n");
}
// Driver function
int main()
{
    struct Node* head = NULL;
    head = getNode(1);
    head->next = getNode(2);
    head->next->next = getNode(3);
    head->next->next->next = getNode(4);
    head->next->next->next->next = getNode(5);
    size = 5;
    printf("Linked list before insertion: ");
    printList(head);
    int data = 6, pos = 2;
    insertAtPosition(head, pos, data);
    printf("Linked list after insertion of 6 at position 2: ");
    printList(head);
    
    return 0;
}
#include <bits stdc++.h="">
using namespace std;

// Node structure of a singly linked list node
struct Node {
    int data;
    struct Node* next;
};

int size = 0;

// Using this function we will be creating new nodes
Node* getNode(int data)
{
    Node* newNode = new Node();

    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Using this function we will insert the newnode at the specific position
void insertAtPosition(Node* head, int pos, int data)
{
    if (pos < 1 || pos > size + 1)
        cout << "Invalid position!" << endl;
    else {
        Node *curr=head;
        for(int i=1;i<pos-1;i++) {="" curr="curr-">next;
        }
        Node* temp=getNode(data);
        temp->next=curr->next;
        curr->next=temp;
        if(pos=1)
        head=temp;
        size++;
    }
}

// Using this function we will print the linked list
void printList(struct Node* head)
{
    while (head != NULL) {
        cout << " " << head->data;
        head = head->next;
    }
    cout << endl;
}

// Driver function
int main()
{

    Node* head = NULL;
    head = getNode(1);
    head->next = getNode(2);
    head->next->next = getNode(3);
    head->next->next->next = getNode(4);
    head->next->next->next->next = getNode(5);

    size = 5;

    cout << "Linked list before insertion: ";
    printList(head);

    int data = 6, pos = 2;
    insertAtPosition(head, pos, data);
    cout << "Linked list after insertion of 6 at position 2: ";
    printList(head);
    
    return 0;
}

public class PrepBytes {
    // Structure of a singly linked list node
    static class Node {
        public int data;
        public Node nextNode;

        public Node(int data) {
            this.data = data;

        }
    }

    // Function to create a new node and return
    static Node GetNode(int data) {
        return new Node(data);
    }

    // Function to insert an element at a specified index
    static Node InsertAtPos(Node headNode, int position, int data) {
        Node head = headNode;
        if (position < 1)
            System.out.print("Invalid position");

        if (position == 1) {
            Node newNode = new Node(data);
            newNode.nextNode = headNode;
            head = newNode;
        } else {
            for(int i=1;i<position - 1;i++)
            {
                headNode=headNode.nextNode;
            }
            
            Node newNode= new Node(data);
            newNode.nextNode=headNode.nextNode;
            headNode.nextNode=newNode;
            
        }
        return head;
    }

    // Function to print the list
    static void PrintList(Node node) {
        while (node != null) {
            System.out.print(node.data);
            node = node.nextNode;
            if (node != null)
                System.out.print(",");
        }
        System.out.println();
    }

    // Driver function
    public static void main(String[] args) {
        Node head = GetNode(1);
        head.nextNode = GetNode(2);
        head.nextNode.nextNode = GetNode(3);
        head.nextNode.nextNode.nextNode = GetNode(4);
        head.nextNode.nextNode.nextNode.nextNode = GetNode(5);

        System.out.print("Linked list before insertion: ");
        PrintList(head);

        int data = 6, pos = 2;
        head = InsertAtPos(head, pos, data);
        System.out.print("Linked list after" + " insertion of 6 at position 2: ");
        PrintList(head);
    }
}



# A linked list Node
class Node:
    def __init__(self, data):
        self.data = data
        self.nextNode = None

# function to create and return a Node
def getNode(data):

    newNode = Node(data)
    return newNode

# function to insert a Node at required position
def insertPos(headNode, position, data):
    head = headNode
    
    if (position < 1):    
        print("Invalid position!")
    
    if position == 1:
        newNode = Node(data)
        newNode.nextNode = headNode
        head = newNode
            
    else:
    
        while (position != 0):        
            position -= 1

            if (position == 1):

                newNode = getNode(data)
                newNode.nextNode = headNode.nextNode
                headNode.nextNode = newNode
                break
            
            headNode = headNode.nextNode
            if headNode == None:
                break        
        if position != 1:
            print("position out of range")    
    return head
    
def printList(head):
    while (head != None):    
        print(' ' + str(head.data), end = '')
        head = head.nextNode
    print()
    
if __name__=='__main__':
    
    head = getNode(1)
    head.nextNode = getNode(2)
    head.nextNode.nextNode = getNode(3)
    head.nextNode.nextNode.nextNode = getNode(4)
    head.nextNode.nextNode.nextNode.nextNode = getNode(5)
    print("Linked list before insertion: ", end='')
    printList(head)
    data = 6
    position = 2
    head = insertPos(head, position, data)
    print("Linked list after insertion of 6 at position 2: ", end = '')
    printList(head)

Output:

Linked list before insertion: 1,2,3,4,5
Linked list after insertion of 6 at position 2: 1,6,2,3,4,5

Time Complexity: O(n), as we are traversing the whole linked list to reach the desired position.

Space Complexity: O(1), since we have not used any extra space for inserting a single node in the linked list.

Conclusion
So, in this article, we have tried to explain how to insert a node at a specific position in a linked list in C using an easy and efficient approach. We have comprehensively covered the algorithm and the practical implementation of the code for better understanding. For additional practice on linked list problems, our knowledgeable mentors at PrepBytes have curated a resourceful collection of questions which can be accessed through this link.

Frequently Asked Questions (FAQs)

Here are some Frequently Asked Questions on how to insert a node at a specific position in a linked list in C.

Ques 1. How can a loop be terminated?
Ans. A break statement exits a for loop or a while loop and after that we can use continue to go through with the other code except for the loop which has terminated.

Ques 2. In a linked list what is a node?
Ans. A node is a collection of two parts. One is the data part which stores the value and the other part which stores the link to the next node.

Ques 3. Is the head considered the node in the linked list?
Ans. A head in a linked list is the reference to the first node. So, the head is not considered a node.

*Ques 4. What is a struct node in a linked list?
Ans.** It is the representation of a node that consists of the first part as the data and the next part as the pointer, which stores the address of the next node.

Ques 5. What happens if the linked list is empty when trying to insert a node at a specific position?
Ans. If the linked list is empty, the new node becomes the first node in the linked list.

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Student management system using linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

Leave a Reply

Your email address will not be published. Required fields are marked *