Open In App

Insert a node at a specific position in a linked list

Last Updated : 03 Apr, 2025
Suggest changes
Share
Like Article
Like
Report

Given a singly linked list, a position pos, and data, the task is to insert that data into a linked list at the given position. 

Examples:

Input: 3->5->8->10, data = 2, pos = 2
Output: 3->2->5->8->10

Input: 3->5->8->10, data = 11, pos = 5
Output: 3->5->8->10->11 

Insertion-at-a-Specific-Position-of-the-Singly-Linked-List-copy
Insertion at specific position in Linked List

[Expected Approach] Using Iterative Method - O(n) time and O(1) space:

  • Initialize a variable , say curr points to head and allocate the memory to the new node with the given data.
  • Traverse the Linked list using curr pointer upto position-1 nodes.
  • If curr's next is not null , then next pointer of the new node points to the next of curr node.
  • The next pointer of current node points to the new node.
  • return the head of linked list.

Below is the implementation of the above approach: 

C++
// C++ program for insertion in a single linked // list at a specified position #include <bits/stdc++.h> using namespace std; class Node {  public:  int data;  Node *next;  Node(int x) {  data = x;  next = nullptr;  } }; // function to insert a Node at required position Node *insertPos(Node *head, int pos, int data) {  // This condition to check whether the  // position given is valid or not.  if (pos < 1)  return head;  // head will change if pos=1  if (pos == 1) {  Node *newNode = new Node(data);  newNode->next = head;  return newNode;  }  Node *curr = head;  // Traverse to the node that will be  // present just before the new node  for (int i = 1; i < pos - 1 && curr != nullptr; i++) {  curr = curr->next;  }    // If position is greater than the   // number of nodes  if (curr == nullptr)   return head;    Node *newNode = new Node(data);  // update the next pointers  newNode->next = curr->next;  curr->next = newNode;  return head; } void printList(struct Node *head) {  Node *curr = head;  while (curr != nullptr) {  cout << curr->data << " ";  curr = curr->next;  }  cout << endl; } int main() {  // Creating the list 3->5->8->10  Node *head = new Node(3);  head->next = new Node(5);  head->next->next = new Node(8);  head->next->next->next = new Node(10);  int data = 12, pos = 3;  head = insertPos(head, pos, data);  printList(head);  return 0; } 
C
// C program for insertion in a single linked // list at a specified position #include <stdio.h> #include <stdlib.h> struct Node {  int data;  struct Node *next; }; struct Node *createNode(int x); // Function to insert a Node at the required position struct Node *insertPos(struct Node *head, int pos, int data) {  // return if invalid input  if (pos < 1)  return head;  // Head will change if pos=1  if (pos == 1) {  struct Node *newNode = createNode(data);  newNode->next = head;  return newNode;  }  struct Node *curr = head;  // Traverse to the node that will be  // present just before the new node  for (int i = 1; i < pos - 1 && curr != NULL; i++) {  curr = curr->next;  }    // if position is greater than  // number of nodes  if (curr == NULL)   return head;    struct Node *newNode = createNode(data);  // Update the next pointers  newNode->next = curr->next;  curr->next = newNode;  return head; } void printList(struct Node *head) {  struct Node *curr = head;  while (curr != NULL) {  printf("%d ", curr->data);  curr = curr->next;  }  printf("\n"); } struct Node *createNode(int x) {  struct Node *new_node =   (struct Node *)malloc(sizeof(struct Node));  new_node->data = x;  new_node->next = NULL;  return new_node; } int main() {  // Creating the list 3->5->8->10  struct Node *head = createNode(3);  head->next = createNode(5);  head->next->next = createNode(8);  head->next->next->next = createNode(10);  int data = 12, pos = 3;  head = insertPos(head, pos, data);  printList(head);  return 0; } 
Java
// Java program for insertion in a single linked // list at a specified position class Node {  int data;  Node next;  Node(int x) {  data = x;  next = null;  } } class GfG {  // function to insert a Node at required position  static Node insertPos(Node head, int pos, int data) {  // This condition to check whether the  // position given is valid or not.  if (pos < 1)  return head;  // head will change if pos=1  if (pos == 1) {  Node newNode = new Node(data);  newNode.next = head;  return newNode;  }  Node curr = head;  // Traverse to the node that will be   // present just before the new node  for (int i = 1; i < pos - 1 && curr != null; i++) {  curr = curr.next;  }    // if position is greater than number of elements  if (curr == null)  return head;    Node newNode = new Node(data);  // update the next pointers  newNode.next = curr.next;  curr.next = newNode;  return head;  }  static void printList(Node node) {  while (node != null) {  System.out.print(node.data + " ");  node = node.next;  }  System.out.println();  }  public static void main(String[] args) {  // Creating the list 3->5->8->10  Node head = new Node(3);  head.next = new Node(5);  head.next.next = new Node(8);  head.next.next.next = new Node(10);  int data = 12, pos = 3;  head = insertPos(head, pos, data);  printList(head);  } } 
Python
# Python program for insertion in a single linked # list at a specified position class Node: def __init__(self, x): self.data = x self.next = None # function to insert a Node at required position def insert_pos(head, pos, data): # This condition to check whether the # position given is valid or not. if pos < 1: return head # head will change if pos=1 if pos == 1: new_node = Node(data) new_node.next = head return new_node curr = head # Traverse to the node that will be  # present just before the new node for _ in range(1, pos - 1): if curr == None: break curr = curr.next # if position is greater # number of nodes if curr is None: return head new_node = Node(data) # update the next pointers new_node.next = curr.next curr.next = new_node return head def print_list(head): curr = head while curr is not None: print(curr.data, end=" ") curr = curr.next print() if __name__ == "__main__": # Creating the list 3->5->8->10 head = Node(3) head.next = Node(5) head.next.next = Node(8) head.next.next.next = Node(10) data = 12 pos = 3 head = insert_pos(head, pos, data) print_list(head) 
C#
// C# program for insertion in a single linked // list at a specified position using System; class Node {  public int data;  public Node next;  public Node(int x) {  data = x;  next = null;  } } class GfG {  // function to insert a Node at required position  static Node InsertPos(Node head, int pos, int data) {  // This condition to check whether the  // position given is valid or not.  if (pos < 1)  return head;  // head will change if pos=1  if (pos == 1) {  Node newHead = new Node(data);  newHead.next = head;  return newHead;  }  Node curr = head;  // Traverse to the node that will be   // present just before the new node  for (int i = 1; i < pos - 1 && curr != null; i++) {  curr = curr.next;  }    // if position is greater than  // size of list  if (curr == null)  return head;    Node newNode = new Node(data);  // update the next pointers  newNode.next = curr.next;  curr.next = newNode;  return head;  }  static void PrintList(Node head) {  Node curr = head;  while (curr != null) {  Console.Write(curr.data + " ");  curr = curr.next;  }  Console.WriteLine();  }  static void Main() {  // Creating the list 3->5->8->10  Node head = new Node(3);  head.next = new Node(5);  head.next.next = new Node(8);  head.next.next.next = new Node(10);  int data = 12, pos = 3;  head = InsertPos(head, pos, data);  PrintList(head);  } } 
JavaScript
// JavaScript program for insertion in a single linked // list at a specified position class Node {  constructor(x) {  this.data = x;  this.next = null;  } } // function to insert a Node at required position function insertPos(head, pos, data) {    // This condition to check whether the  // position given is valid or not.  if (pos < 1)  return head;    // head will change if pos=1  if (pos === 1) {  let newNode = new Node(data);  newNode.next = head;  return newNode;  }    let curr = head;    // Traverse to the node that will be   // present just before the new node  for (let i = 1; i < pos - 1 && curr != null; i++) {  curr = curr.next;  }    // if position is greater  // than size of list  if (curr == null)  return head;    let newNode = new Node(data);    // update the next pointers  newNode.next = curr.next;  curr.next = newNode;    return head; } function printList(head) {  let curr = head;  while (curr !== null) {  console.log(curr.data);  curr = curr.next;  } } // Creating the list 3->5->8->10 let head = new Node(3); head.next = new Node(5); head.next.next = new Node(8); head.next.next.next = new Node(10); let data = 12, pos = 3; head = insertPos(head, pos, data); printList(head); 

Output
3 5 12 8 10 

Time Complexity: O(n), where n is the number of nodes in the linked list.
Auxiliary Space: O(1)


Similar Reads

Article Tags :
Practice Tags :