In this article, you’ll learn how to insert a node at a specific position in a linked list in C++, along with that you’ll also see the algorithm to insert a node at a specific position in a linked list.
So, Let’s get started!
Prerequisite: You should have the knowledge of How do you create a node in a linked list? and How to traverse a singly linked list?
How do you insert a node at a specific position in a linked list?
Let’s see how you can insert a node at a specific position in a linked list step-by-step:
Variables we are using here:
- head: A pointer of
Nodetype pointing to the first node of the linked list. - temp: The node to be inserted (It will also be of
Nodetype). - pos: The position where we wish to insert the node.
- ptr: A pointer of
Nodetype used to traverse the list till the position less than one.
The following algorithm inserts a node at a specific position in a linked list:
Algorithm to insert a node at a specific position in a linked list:
- Step 01: Start
- Step 02: Create a new node named
tempofNodetype with the given data - Step 03: If
head == NULLorpos == 1- Step 04: Call the function
insertAtHead(head, data) - Step 05: Go to step
21
- Step 04: Call the function
- Step 10: [End of If ]
- Step 11: Else
- Step 12: Create a new node named
ptrofNodetype and initialize it withhead. - Step 13: [Initialize counter variable. ]
Set i = 1 - Step 14: Repeat Step 15 and 16 for
i=1toi<pos - 1 - Step 15: Set
ptr=ptr→next - Step 16: [Increase counter. ] Set
i=i + 1 - Step 17: [End of step 14 loop. ]
- Step 12: Create a new node named
- Step 18: Set
temp→next=ptr→next - Step 19: Set
ptr→next=temp - Step 20: [End of Else block. ]
- Step 21: Stop
Visual Representation:
Implementation in C++:
Case 01: If the linked list is empty.
// writing a program in C++ to insert a node at a specific position in a linked list
#include<iostream>
using namespace std;
// creating a class "Node"
class Node
{
public:
int data;
Node *next;
//constructor
Node(int data)
{
this -> data = data;
this -> next = NULL;
}
};
// Traversing a linked list
void TraverseList(Node* &head)
{
if(head == NULL)
cout << "List is empty" << endl;
else
{
Node* temp = head;
while(temp != NULL)
{
cout << temp -> data << " -> " ;
temp = temp -> next;
}
cout << "Null" << endl;
}
}
// function to insert a node at the head of a linked list
void insertAtHead(Node* &head, int data)
{
//new node creation
Node* temp = new Node(data);
//if list is empty
if(head == NULL)
head = temp;
else
{
temp -> next = head;
head = temp;
}
}
// function to insert a node at the tail of a linked list
void insertAtTail(Node* &head, int data)
{
//creation of a new node
Node* tail = new Node(data);
//empty list
if(head == NULL)
head = tail;
else
{
Node* temp = head;
while(temp -> next != NULL)
{
temp = temp -> next;
}
temp -> next = tail;
}
}
// function to insert a node at a specific position in a linked list
void insertAtPosition(Node* &head, int pos, int data)
{
//new node creation
Node* temp = new Node(data);
//if list is empty
if(head == NULL || pos == 1)
insertAtHead(head, data);
else
{
Node* ptr = head;
for(int i = 1; i < pos - 1; i++)
ptr = ptr -> next;
temp -> next = ptr -> next;
ptr -> next = temp;
}
}
//Driver's code
int main()
{
// if list is empty
Node* head = NULL;
insertAtPosition(head, 1, 7);
TraverseList(head);
return 0;
}
If you compile and run the above program, it will produce the following result:
Output:
7 -> Null
Case 02: If the linked list is not empty.
// writing a program in C++ to insert a node at a specific position in a linked list
#include<iostream>
using namespace std;
// creating a class "Node"
class Node
{
public:
int data;
Node *next;
//constructor
Node(int data)
{
this -> data = data;
this -> next = NULL;
}
};
// Traversing a linked list
void TraverseList(Node* &head)
{
if(head == NULL)
cout << "List is empty" << endl;
else
{
Node* temp = head;
while(temp != NULL)
{
cout << temp -> data << " -> " ;
temp = temp -> next;
}
cout << "Null" << endl;
}
}
// function to insert a node at the head of a linked list
void insertAtHead(Node* &head, int data)
{
//new node creation
Node* temp = new Node(data);
//if list is empty
if(head == NULL)
head = temp;
else
{
temp -> next = head;
head = temp;
}
}
// function to insert a node at the tail of a linked list
void insertAtTail(Node* &head, int data)
{
//creation of a new node
Node* tail = new Node(data);
//empty list
if(head == NULL)
head = tail;
else
{
Node* temp = head;
while(temp -> next != NULL)
{
temp = temp -> next;
}
temp -> next = tail;
}
}
// function to insert a node at a specific position in a linked list
void insertAtPosition(Node* &head, int pos, int data)
{
//new node creation
Node* temp = new Node(data);
//if list is empty
if(head == NULL || pos == 1)
insertAtHead(head, data);
else
{
Node* ptr = head;
for(int i = 1; i < pos - 1; i++)
ptr = ptr -> next;
temp -> next = ptr -> next;
ptr -> next = temp;
}
}
//Driver's code
int main()
{
// if list is empty
Node* head = NULL;
insertAtPosition(head, 1, 7);
insertAtTail(head, 13);
insertAtTail(head, 58);
insertAtTail(head, -9);
insertAtTail(head, 20);
insertAtPosition(head, 4, 64);
TraverseList(head);
return 0;
}
If you compile and run the above program, it will produce the following result:
Output:
7 -> 13 -> 58 -> 64 -> -9 -> 20 -> Null
Conclusion:
In this article, you learned how to insert a node at a specific position in a linked list in C++, you also became familiar with the algorithm to insert a node at a specific position in a linked list.
So,
I really hope that you liked my article and got a lot of value from it.
Now, It’s your turn!
If you have any question, feel free to ask in the comment section below right now.
And, and, and…
Don’t forget to share this article to your lovely friends.
Coz, as you know, Sharing is Caring! ?… Right?