Linked List Insertion
 Linked List Insertion Algorithm
 Linked List Insertion Illustration
 Linked List Insertion Implementation
 Linked List Insertion Algorithm Complexity
In this article, we will learn how to insert a node in a linked list. We can see that 4 different scenarios arise.
 We want to insert a node before the head of the linked list. This operation resembles the push operation in the stack.
 We want to insert a node at the end of the linked list i.e. next to the tail node.
 We want to insert a node at the
ith
position of the linked list.  We have the reference of the node, after which we want to insert the new node.
Linked List Insertion Algorithm
Let the head
be the pointer to the first node of the linked list and let x
be the data to be inserted into the linked list.
Insert Node at the Head of the Linked List push()

Create a new node
temp
with datax
. 
Set
temp>next
tohead
to inserttemp
before thehead
. 
Set
temp
as the head of the linked list.
Insert Node at the End of the Linked List append()

Create a new node
temp
with datax
. 
Initialize
tail
pointing towards thehead
. 
If the linked list is empty, set
temp
ashead
of the linked list and return. 
Else iterate towards the end of the linked list, such that
tail>next
!=NULL
, so that you land at the last element 
Set
tail>next
as thetemp
.
Insert Node at the ith
Position of the Linked List insertNpos()

If position
pos
<=0
, return; 
If
pos
==0
and thehead
is empty, create a new node with data asx
and set it as thehead
. 
Else if
pos
==1
, callpush()
. 
Else, create a new node
temp
with datax
. 
Initialize
curr
pointing towards thehead
. 
while
pos
, do the following:
If
pos
==1
, If
curr
is notNULL
 Set
temp>next
ascurr>next
to inserttemp
aftercurr
.  Set
curr>next
as thetemp
to connectcurr
totemp
.
 Set
 Return;
 If

Else set
curr
ascurr>next
.

Insert Node Next to Reference of Given Node insertAfter()

if
prev
==NULL
, return; 
Create a new node
curr
with datax
. 
Point
curr>next
toprev>next
to add new node after prev. 
Point
prev>next
towardscurr
to complete the insertion.
Linked List Insertion Illustration
Assume that we have a node temp
with a data value equal to 5
and we want to insert it in the linked list. Let us consider all 4
cases and illustrate how the above algorithms work.
Insert Node at the Head of the Linked List push()

Set
temp's
s pointer towards thehead
. 
Point
head
totemp
.
Insert Node at the End of the Linked List append()

Point
curr
towards thehead
with data as2
. 
Set
curr
ascurr>next
and move it to the node with data3
. 
Set
curr
ascurr>next
and move it to the node with data4
. 
Exit the while loop and set
curr>next
astemp
.
Insert Node at the ith
Position of the Linked List insertNpos()
We will insert our node at position 3
.

Point
curr
towardshead
with data as1
,pos
=pos1
=2
. 
Set
curr
ascurr>next
and move it to node with data3
,pos
=pos 1
=1
. 
Set
temp>next
ascurr>next
to insert temp aftercurr
. 
Set
curr>next
as thetemp
to complete insertion oftemp
betweencurr
andcurr>next
.
Insert Node Next to Reference of Given Node insertAfter()

Set
temp>next
asprev>next
to inserttemp
betweenprev
andprev>next
. 
Set
prev>next
as thetemp
to complete the insertion.
Linked List Insertion Implementation
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
this>data = x;
this>next = NULL;
}
};
void push(Node** head, int x) {
Node* temp = new Node(x);
temp>next = (*head);
(*head) = temp;
}
void insertAfter(Node* prev, int x) {
if (prev == NULL) {
return;
}
Node* curr = new Node(x);
curr>next = prev>next;
prev>next = curr;
}
void printList(Node* head) {
Node* curr = head;
while (curr != NULL) {
cout << curr>data << " ";
curr = curr>next;
}
}
void insertNpos(Node** head, int x, int pos) {
if (pos <= 0) {
return;
}
if (!head && pos == 1) {
*head = new Node(x);
} else if (pos == 1) {
push(head, x);
}
Node* temp = new Node(x);
Node* curr = *head;
while (pos) {
if (pos == 1) {
if (curr) {
temp>next = curr>next;
curr>next = temp;
}
return;
}
curr = curr>next;
}
}
void append(Node** head, int x) {
Node* temp = new Node(x);
Node* tail = *head;
if (*head == NULL) {
*head = temp;
return;
}
while (tail>next != NULL) tail = tail>next;
tail>next = temp;
return;
}
int main() {
Node* head = new Node(1);
head>next = new Node(2);
printList(head);
cout << "\n";
push(&head, 3);
push(&head, 4);
printList(head);
cout << "\n";
append(&head, 5);
printList(head);
cout << "\n";
insertAfter(head>next>next, 6);
printList(head);
cout << "\n";
insertNpos(&head, 24, 2);
printList(head);
return 0;
}
Linked List Insertion Algorithm Complexity
Time Complexity
 Average Case
To insert a node at the ith
position in the linked list, we have to visit i
nodes. So, the time complexity is of the order of O(i)
. And we have n
nodes in the linked list, so on the averagecase time complexity is O(n/2)
or O(n)
. The time complexity is of the order of O(n)
.
 Best Case
The bestcase occurs when we want to insert a node at the head of the linked list or we have the reference to the node before the site of insertion. The bestcase time complexity is O(1)
.
 Worst Case
The worstcase time complexity is O(n)
. It is the same averagecase time complexity.
Space Complexity
This insertion algorithm’s space complexity is O(1)
as no extra space other than curr
pointer is required.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedInRelated Article  Data Structure
 Circular Doubly Linked List
 Circular Linked List
 Doubly Linked List
 Linked List Deletion
 Linked List Merge Sort