Last Updated on March 10, 2022 by Ria Pathak
Introduction
The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.
In this article, we are going to learn about the insertion operations in a singly linked list.
There are three primary insertion operations.
- Insert at the beginning of the list.
- Insert at the end of the list.
- Insert after a given node.
Let us have a look at all these Insertion operations.
Approach (Insert at the beginning)
What should we do to insert a node at the beginning?
It is pretty simple. Let us take an example to understand it.
- Suppose the given list is 2 → 3, and we have to insert 1 at the front of the list. So, to insert 1 at front, we will simply make 1’s next point to 2 and make 1 as the new head of the linked list and our final linked list will be: 1 → 2 → 3.
Also, keep in mind that, the new node which gets added at the front of the list, will be the new head of the list.
This is quite simple. Let the newly created node be x and make x → next = head and then make head = x, as explained above.
Algorithm
1) Create the node which is to be inserted, say newnode.
2) If the list is empty, the head will point to the newnode, and we will return.
3) Else, If the list is not empty:
- Make newnode → next = head. This step ensures that the new node is being added at the beginning of the list.
- Then after that, make head = newnode, as the new node is now the first node of the list, hence the new head.
Time Complexity: O(1), as we are only accessing and changing the head of the list.
Space Complexity: O(1), as no extra space is being used.
Approach (Insert at the end)
What should we do to insert an element at the end of a linked list?
It is pretty simple. Let us take an example to understand it.
- Suppose the list is 1 → 2 →3, and we have to add 4 at the end of this list. So, we just have to make the connection between 3 and 4, and finally, make the next of 4 as null as it is the new last node.
So, following the above approach of insertion at the end, we will first take a pointer curr and using it we will traverse to the last node of the list. As explained above, after reaching the last node, we will simply make curr → next = newnode and newnode → next = NULL.
Algorithm
1) Create the node which is to be inserted, say newnode.
2) If the list is empty, make head point to the newnode, and return.
3) Else, if the list is not empty:
- Using a pointer curr, traverse the list up to the last node of the list.
- After the traversal, curr will be standing at the last node, and now, to insert the newnode at the end of the list, make curr → next = newnode and then newnode → next = NULL, as newnode is the new last node of the linked list.
Time Complexity: O(N), as we have to traverse the list to reach the end of the list.
Space Complexity: O(1), as no extra space is being used.
Approach (Insert after a given node)
In this approach, we will be given a node’s address. We will have to insert the new node just after this given node.
As we have the address of the node, we don’t have to traverse the linked list. Let take an example to understand it more clearly; suppose the given list is: 1 → 2 → 3, and we have the address of 2, and we want to insert a new node (say x) after this node 2.
- So, to insert the node, we will simply do x → next = 2 → next and then 2 → next = x.
- By doing x → next = 2 → next, we are making sure that x is being inserted after 2, and by doing 2 → next = x, we are again making sure that the links are complete.
Suppose the address of the node after which we have to insert the new node is NODE. So, now to insert the newnode just after this node, we will do the following steps.
- First, we will make newnode → next = NODE → next
- Then, we will make NODE → next = newnode
- And our insertion will be done.
Algorithm
1) Create the node which is to be inserted, say NewNode, and the node whose address is given is prevnode.
2) If the address of the given node is NULL, simply return.
3) Else, if address is not NULL:
- Make the next of NewNode point to the next of prevnode and then make next of prevnode point to NewNode (see steps below).
- NewNode → next = prevnode→ next
- prevnode – > next= NewNode
4) After performing the above steps, our new node NewNode will get inserted after the prevnode.
Time Complexity: O(1), as we have the address of the node after which the new node is to be inserted.
Space Complexity: O(1), as no extra space is being used.
To get a clearer understanding, have a look at the dry run. Let us head on to the dry run of these methods.
Dry Run
Code Implementation
#include<stdio.h>
#include<stdlib.h>
struct Node {
int data;
struct Node* next;
};
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Using this function we will inserting a new node after a given node in the linked list */
void addtAfter(struct Node* prev_node, int new_data)
{
if (prev_node == NULL)
{
printf("the given previous node cannot be NULL");
return;
}
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
/* Using this function we will inserting a new node at the end of the linked list */
void append(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node *last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
return;
}
/* Using this function we will be printing the content of the linked list */
void printList(struct Node *node)
{
while (node != NULL)
{
printf("%d ",node->data);
node = node->next;
}
}
/* Driver function */
int main()
{
struct Node* head = NULL;
append(&head, 4);
push(&head, 3);
push(&head, 2);
append(&head, 5);
addtAfter(head->next, 8);
printf("Created Linked list is: ");
printList(head);
return 0;
}
#include <bits stdc++.h="">
using namespace std;
/* Node structure of a linked list node */
class Node
{
public:
int data;
Node *next;
};
/* Using this function we will be inserting new nodes at the head of the list */
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Using this function we will inserting a new node after a given node in the linked list */
void addtAfter(Node* prev_node, int new_data)
{
if (prev_node == NULL)
{
cout<<"the given previous node cannot be NULL";
return;
}
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
/* Using this function we will inserting a new node at the end of the linked list */
void append(Node** head_ref, int new_data)
{
Node* new_node = new Node();
Node *last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
return;
}
/* Using this function we will be printing the content of the linked list */
void printList(Node *node)
{
while (node != NULL)
{
cout<<" "<<node->data;
node = node->next;
}
}
/* Driver function */
int main()
{
Node* head = NULL;
append(&head, 4);
push(&head, 3);
push(&head, 2);
append(&head, 5);
addtAfter(head->next, 8);
cout<<"Created Linked list is: ";
printList(head);
return 0;
}
public class LinkedList
{
Node head;
/* Node structure of a linked list node */
class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}
/* Using this function we will be inserting new nodes at the head of the list */
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
/* Using this function we will inserting a new node after a given node in the linked list */
public void insertAfter(Node prev_node, int new_data)
{
if (prev_node == null)
{
System.out.println("The given previous node cannot be null");
return;
}
Node new_node = new Node(new_data);
new_node.next = prev_node.next;
prev_node.next = new_node;
}
/* Using this function we will inserting a new node at the end of the linked list */
public void append(int new_data)
{
Node new_node = new Node(new_data);
if (head == null)
{
head = new Node(new_data);
return;
}
new_node.next = null;
Node last = head;
while (last.next != null)
last = last.next;
last.next = new_node;
return;
}
/* Using this function we will be printing the content of the linked list */
public void printList()
{
Node tnode = head;
while (tnode != null)
{
System.out.print(tnode.data+" ");
tnode = tnode.next;
}
}
/* Driver function */
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
llist.append(4);
llist.push(3);
llist.push(2);
llist.append(5);
llist.insertAfter(llist.head.next, 8);
System.out.println("\nCreated Linked list is: ");
llist.printList();
}
}
# Node structure of a linked list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Linked List class contains a Node object
class LinkedList:
def __init__(self):
self.head = None
# Using this function we will be inserting new nodes at the head of the list
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Using this function we will inserting a new node after a given node in the linked list
def addAfter(self, prev_node, new_data):
if prev_node is None:
print("the given previous node cannot be NULL")
return
new_node = Node(new_data)
new_node.next = prev_node.next
prev_node.next = new_node
# Using this function we will inserting a new node at the end of the linked list
def append(self, new_data):
new_node = Node(new_data)
if self.head is None:
self.head = new_node
return
last = self.head
while (last.next):
last = last.next
last.next = new_node
# Using this function we will be printing the content of the linked list
def printList(self):
temp = self.head
while (temp):
print(temp.data,end=" ")
temp = temp.next
if __name__=='__main__':
llist = LinkedList()
llist.append(4)
llist.push(3)
llist.push(2)
llist.append(5)
llist.addAfter(llist.head.next, 8)
print("Created Linked list is:")
llist.printList()
Output
Created Linked list is: 2 3 8 4 5
Time Complexity: O(n), as list traversal is needed
[forminator_quiz id=”5751″]
So, in this article, we have tried to explain how to insert nodes at different positions in a linked list. As we are doing the insertions in O(1) time mostly (not in the case of inserting at the end), this problem becomes an important one for coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.