Insert the Node at a Particular Position in the Linked List

Linked lists are a fundamental data structure in programming that allows dynamic memory allocation and flexible data management. This article will explore how to create and insert the node at particular positions and display the list using a simple C program.

Step 01: Node Structure in Linked List

Define a structure for the node containing data and a pointer to the next node. A linked list is a collection of nodes where each node contains two parts:

  1. Data: The value stored in the node.
  2. Pointer: A reference to the next node in the sequence.

The structure of the node is given below

Node Structure in Linked List

Step 02: Consider a Singly-linked List

Consider a singly linked list which has four nodes with the following data and addresses: 10 at 350, 20 at 380, 30 at 700, and 40 at 900. Each node points to the next, and the last node points to NULL, indicating the end of the list.

Example A Singly Linked List

Step 03: Specific Position Number 03 is Selected

The following figure shows the position to insert a new node at position 3 in the singly linked list

Inserting a Node at a Certain Position

Step 04: Create New Node for insertion

To insert a new node (suppose data=15 and address =1200) at a particular position  (suppose 03) in a singly linked list, first, create the new node and assign its data and address.

Create new Node in Linked list

Note: at this position, we need to take another pointer (i.e. “ptr2”) which points to the new node.

Step 05: Create New Pointer (“ptr”)

We need another pointer (i.e. ptr) to find the node just before the position where you want to insert it. It starts traversing from the first node (called the head). For example, if you want to insert at position 3, ptr stops at position 2.

Create new pointer (”ptr”)

Step 06: Reach (“ptr”), one position Before, to insert

After creating pointer ptr and deciding the insertion position =3, the question is, how to reach the desired position-02 to insert new data at a particular position? This will be done with the help of the condition given below.

 

    int currentPosition = 1;

// Traverse to the position before the insertion point

while (ptr!= NULL && currentPosition < position – 1) {

ptr= ptr->next;

currentPosition++;

}

Traverse (”ptr”) to Specific position

  • ptr2: This is the newly created node, which contains the data to be inserted and whose pointer (next) is currently NULL.
  • ptr: This points to the node in the linked list after which the new node ptr2 will be inserted.

Step 07: ptr2->next = ptr->next

By using ptr2->next = ptr->next, The ptr2 is updated from Null to 700 address. As ptr->next contains the address of the next node at 700 address.

Mathematically,
ptr2->next = Null;
ptr->next =700;
ptr2->next = ptr->next, So
ptr2->next = 700;

The following figure explains it all

Inserting a Node at a Certain Position - Part 01

Step 08: ptr->next = ptr2

By using ptr->next = ptr2,  The ptr2 is updated from 700 to 1200 addresses. As ptr2 contains the address of the new node at 1200 address.

Mathematically,
ptr->next = 700;
ptr2 =1200;
ptr->next = ptr2, So
ptr->next = 1200;

The following figure explains it all

Inserting a Node at a Certain Position - Part 02


Unlike arrays, linked lists can grow or shrink dynamically, making them more flexible for certain applications.

Code Example In C: Insert the Node at a Particular Position

The Code for insertion of the node at a particular position in C programming is given below

#include <stdio.h>
#include <stdlib.h>// Define the structure of a node
struct Node {
int data;
struct Node* next;
};// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf(“Memory allocation failed\n”);
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}// Function to insert a node at a specific position
struct Node* insertAtPosition(struct Node* head, int data, int position) {
struct Node* ptr2 = createNode(data); // `ptr2` is used for the new nodeif (position == 1) {
// Insert at the beginning
ptr2->next = head;
return ptr2;
}struct Node* ptr = head; // `ptr` is used for traversal
int currentPosition = 1;

// Traverse to the node before the insertion point
while (ptr != NULL && currentPosition < position – 1) {
ptr = ptr->next;
currentPosition++;
}

if (ptr == NULL) { // Position is out of bounds
printf(“Position out of bounds.\n”);
free(ptr2);
return head;
}

// Insert the new node
ptr2->next = ptr->next;
ptr->next = ptr2;

return head;
}

// Function to display the linked list
void displayList(struct Node* head) {
struct Node* ptr = head; // Use `ptr` for traversal
while (ptr != NULL) {
printf(“%d -> “, ptr->data);
ptr = ptr->next;
}
printf(“NULL\n”);
}

// Main function
int main() {
// Manually creating the linked list
struct Node* head = createNode(10);
head->next = createNode(20);
head->next->next = createNode(30);
head->next->next->next = createNode(40);

printf(“Initial linked list: “);
displayList(head);

// Insert a new node with value 13 at position 3
int newData = 15;
int position = 3;

printf(“\nInserting %d at position %d…\n”, newData, position);
head = insertAtPosition(head, newData, position);

printf(“Linked list after insertion: “);
displayList(head);

return 0;
}

Output:

Initial linked list: 10 -> 20 -> 30 -> 40 -> NULL

Inserting 15 at position 3...
Linked list after insertion: 10 -> 20 -> 15 -> 30 -> 40 -> NULL