Last Updated on June 6, 2022 by Ria Pathak
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.
Problem Statement
In this article, we are going to learn about the insertion operations in a circular linked list. In a circular linked list, the last node doesn’t point to NULL. Instead, it points to the first node, forming a circle.
There are four main insertion operations:
- Insert at the beginning of the list
- Insert at the end of the list.
- Insert in an empty list.
- Insert in between the nodes.
Let’s have a glance at the approaches and algorithms for the above four insertion operations.
Approach (Insert at the beginning)
While inserting at the beginning in a circular linked list, we have to keep in mind that the last node always points to the head node.
If we keep the above point in mind, we can say that firstly, we will make the new node point to the head node. Now, as we know that the last should point to the first node of the list, so we will make the last node point to the new node. In this way, the last node will point to the newly created node, and the newly created node will point to the head. Now, the newly created node will become the head.
Algorithm
- Create the node which is to be inserted, say NewNode.
- Do NewNode – > next = last – > next. This step ensures that the current node is being added at the beginning of the list, as the next of the last node is always the head of the list. The NewNode will become the head.
- As it is a circular linked list, the last will now point to the new node, so last – > next = NewNode. By doing this, the last node will now point to the newly created node, which is our new head. In this way, the tail is being updated.
Function Implementation
struct Node *addBegin(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *temp
= (struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = last -> next;
last -> next = temp;
return last;
}
struct Node *addBegin(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *NewNode =
(struct Node *)malloc(sizeof(struct Node));
NewNode -> data = data;
NewNode -> next = last -> next;
last -> next = NewNode;
return last;
}
Node addBegin(Node last,int data)
{
if(last==null)
{
return addToEmpty(last,data);
}
Node newNode=new Node(data);
newNode.next=last.next;
last.next=newNode;
return last;
}
def addBegin(self, data): if (self.last == None): return self.addToEmpty(data) NewNode = Node(data) NewNode.next = self.last.next self.last.next = NewNode return self.last
Approach (Insert at the end)
While inserting at the end in a circular linked list, we have to keep in mind that the last node always points to the head node.
If we keep the above point in mind, we can say that firstly, we will make the new node point to the next of the last node. After doing this, we will make the last node point to the new node. In the end, the new node will become the last node.
Algorithm
- Create the node which is to be inserted, say NewNode.
- Make the new node point to the next of the last node NewNode – > next = last – > next.
- Make the last node point to the new node last – > next = NewNode. By doing this, the last node, instead of pointing to the head node, will point to the new node.
- In the end, the NewNode will become the last node. In this way, the tail is being updated.
Function Implementation
struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *temp =
(struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = last -> next;
last -> next = temp;
last = temp;
return last;
}
struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *NewNode =
(struct Node *)malloc(sizeof(struct Node));
NewNode -> data = data;
NewNode -> next = last -> next;
last -> next = NewNode;
last = NewNode;
return last;
}
Node addEnd(Node last,int data)
{
if(last=null)
{
return addToEmpty(last,data);
}
Node NEwNode=new Node(data);
NewNode.next=last.next;
last.next=NewNode;
last=NewNode;
return last;
}
def addEnd(self, data): if (self.last == None): return self.addToEmpty(data) NewNode = Node(data) NewNode.next = self.last.next self.last.next = NewNode self.last = NewNode return self.last
Approach (Insert in an empty list)
While inserting in an empty list, we have to keep in mind that the last node will be NULL initially.
If we keep the above point in mind, we can say that firstly, we will allocate memory for the new node. Now, the new node will become the new tail. As there is only a singly node, so this new node is the tail as well as the head of the list. So, the new node will point to itself. In this way, we can update the head and tail, and insert in an empty list.
Algorithm
- Create the node which is to be inserted, say NewNode.
- Make the new node the last node last = NewNode.
- As it is the only node in the list, it will be the tail as well as head.
- Keeping the above point in mind, we will make the NewNode point to the last(itself) NewNode – > next = last.
- By performing the above steps, the head and tail are being updated, as well as the NewNode is being added to the empty list.
Function Implementation
struct Node *addToEmpty(struct Node *last, int data)
{
if (last != NULL)
return last;
struct Node *NewNode =
(struct Node*)malloc(sizeof(struct Node));
NewNode -> data = data;
last = NewNode;
last -> next = last;
return last;
}
struct Node *addToEmpty(struct Node *last, int data)
{
if (last != NULL)
return last;
struct Node *NewNode =
(struct Node*)malloc(sizeof(struct Node));
NewNode -> data = data;
last = NewNode;
last -> next = last;
return last;
}
Node addToEmpty(Node last,int data)
{
if(last!=null)
{
return last;
}
Node NewNode=new Node(data);
last=NewNode;
last.next=last;
return last;
}
def addToEmpty(self, data): if (self.last != None): return self.last NewNode = Node(data) self.last = NewNode self.last.next = self.last return self.last
Approach (Insert in between the nodes)
In this approach, we will be given a node’s data. We will have to insert the new node just after this given node.
To achieve this, we will first create the node which is to be inserted, say NewNode, then we will simply traverse the list till we find the the node with the given data. Let the node that is found is P. So, to insert this New Node just after P, we will simply do NewNode – > next = P -> next. After this, make P point to this NewNode. By doing this, we are successfully inserting the new node after a given node.
Algorithm
- Create the node which is to be inserted, say NewNode.
- Traverse through the list till the node with the given data is not found.
- Store the node in P.
- Make the next of NewNode point to the next of P, NewNode – > next = P – > next
- Make P point to the NewNode P – > next = NewNode.
Function Implementation
struct Node *addAfter(struct Node *last, int data, int item)
{
if (last == NULL)
return NULL;
struct Node *temp, *P;
P = last -> next;
do
{
if (P ->data == item)
{
temp = (struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = P -> next;
P -> next = temp;
if (P == last)
last = temp;
return last;
}
P = P -> next;
} while(P != last -> next);
printf(" \n not present in the list.");
return last;
}
struct Node *addAfter(struct Node *last, int data, int item)
{
if (last == NULL)
return NULL;
struct Node *temp, *P;
P = last -> next;
do
{
if (P ->data == item)
{
temp = (struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = P -> next;
P -> next = temp;
if (P == last)
last = temp;
return last;
}
P = P -> next;
} while(P != last -> next);
cout << item << " not present in the list." << endl;
return last;
}
public void insertAfter(Node prev_node, int new_data)
{
/* 1. Check if the given Node is null */
if (prev_node == null) {
System.out.println(
"The given previous node cannot be null");
return;
}
/* 2. Allocate the Node &
3. Put in the data*/
Node new_node = new Node(new_data);
/* 4. Make next of new Node as next of prev_node */
new_node.next = prev_node.next;
/* 5. make next of prev_node as new_node */
prev_node.next = new_node;
}
def addAfter(self, data, item): if (self.last == None): return None NewNode = Node(data) p = self.last.next while p: if (p.data == item): NewNode.next = p.next p.next = NewNode if (p == self.last): self.last = NewNode return self.last else: return self.last p = p.next if (p == self.last.next): print(item, "not present in the list") break
Dry Run
Code Implementation
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};
struct Node *addToEmpty(struct Node *last, int data)
{
if (last != NULL)
return last;
struct Node *NewNode =
(struct Node*)malloc(sizeof(struct Node));
NewNode -> data = data;
last = NewNode;
last -> next = last;
return last;
}
struct Node *addBegin(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *NewNode =
(struct Node *)malloc(sizeof(struct Node));
NewNode -> data = data;
NewNode -> next = last -> next;
last -> next = NewNode;
return last;
}
struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *NewNode =
(struct Node *)malloc(sizeof(struct Node));
NewNode -> data = data;
NewNode -> next = last -> next;
last -> next = NewNode;
last = NewNode;
return last;
}
struct Node *addAfter(struct Node *last, int data, int item)
{
if (last == NULL)
return NULL;
struct Node *temp, *p;
p = last -> next;
do
{
if (p ->data == item)
{
temp = (struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = p -> next;
p -> next = temp;
if (p == last)
last = temp;
return last;
}
p = p -> next;
} while(p != last -> next);
printf("%d \nnot present in the list.",&item);
return last;
}
void traverse(struct Node *last)
{
struct Node *p;
if (last == NULL)
{
printf("\nList is empty.");
return;
}
p = last -> next;
do
{
printf("%d ",&p -> data);
p = p -> next;
}
while(p != last->next);
}
int main()
{
struct Node *last = NULL;
last = addToEmpty(last, 2);
last = addBegin(last, 1);
last = addEnd(last, 3);
last=addAfter(last,4,2);
traverse(last);
return 0;
}
#include<bits stdc++.h="">
using namespace std;
struct Node
{
int data;
struct Node *next;
};
struct Node *addToEmpty(struct Node *last, int data)
{
if (last != NULL)
return last;
struct Node *NewNode =
(struct Node*)malloc(sizeof(struct Node));
NewNode -> data = data;
last = NewNode;
last -> next = last;
return last;
}
struct Node *addBegin(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *NewNode =
(struct Node *)malloc(sizeof(struct Node));
NewNode -> data = data;
NewNode -> next = last -> next;
last -> next = NewNode;
return last;
}
struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *NewNode =
(struct Node *)malloc(sizeof(struct Node));
NewNode -> data = data;
NewNode -> next = last -> next;
last -> next = NewNode;
last = NewNode;
return last;
}
struct Node *addAfter(struct Node *last, int data, int item)
{
if (last == NULL)
return NULL;
struct Node *temp, *p;
p = last -> next;
do
{
if (p ->data == item)
{
temp = (struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = p -> next;
p -> next = temp;
if (p == last)
last = temp;
return last;
}
p = p -> next;
} while(p != last -> next);
cout << item << " not present in the list." << endl;
return last;
}
void traverse(struct Node *last)
{
struct Node *p;
if (last == NULL)
{
cout << "List is empty." << endl;
return;
}
p = last -> next;
do
{
cout << p -> data << " ";
p = p -> next;
}
while(p != last->next);
}
int main()
{
struct Node *last = NULL;
last = addToEmpty(last, 2);
last = addBegin(last, 1);
last = addEnd(last, 3);
last=addAfter(last,4,2);
traverse(last);
return 0;
}
public class PrepBytes
{
static class Node
{
int data;
Node next;
};
static Node addToEmpty(Node last, int data)
{
if (last != null)
return last;
Node temp = new Node();
temp.data = data;
last = temp;
last.next = last;
return last;
}
static Node addBegin(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
return last;
}
static Node addEnd(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
static Node addAfter(Node last, int data, int item)
{
if (last == null)
return null;
Node temp, p;
p = last.next;
do
{
if (p.data == item)
{
temp = new Node();
temp.data = data;
temp.next = p.next;
p.next = temp;
if (p == last)
last = temp;
return last;
}
p = p.next;
} while(p != last.next);
System.out.println(item + " not present in the list.");
return last;
}
static void traverse(Node last)
{
Node p;
if (last == null)
{
System.out.println("List is empty.");
return;
}
p = last.next;
do
{
System.out.print(p.data + " ");
p = p.next;
}
while(p != last.next);
}
public static void main(String[] args)
{
Node last = null;
last = addToEmpty(last, 2);
last = addBegin(last, 1);
last = addEnd(last, 3);
last=addAfter(last,4,2);
traverse(last);
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.last = None
def addToEmpty(self, data):
if (self.last != None):
return self.last
NewNode = Node(data)
self.last = NewNode
self.last.next = self.last
return self.last
def addBegin(self, data):
if (self.last == None):
return self.addToEmpty(data)
NewNode = Node(data)
NewNode.next = self.last.next
self.last.next = NewNode
return self.last
def addEnd(self, data):
if (self.last == None):
return self.addToEmpty(data)
NewNode = Node(data)
NewNode.next = self.last.next
self.last.next = NewNode
self.last = NewNode
return self.last
def addAfter(self, data, item):
if (self.last == None):
return None
NewNode = Node(data)
p = self.last.next
while p:
if (p.data == item):
NewNode.next = p.next
p.next = NewNode
if (p == self.last):
self.last = NewNode
return self.last
else:
return self.last
p = p.next
if (p == self.last.next):
print(item, "not present in the list")
break
def traverse(self):
if (self.last == None):
print("List is empty.")
return
NewNode = self.last.next
while NewNode:
print(NewNode.data, end = " ")
NewNode = NewNode.next
if NewNode == self.last.next:
break
if __name__ == '__main__':
llist = CircularLinkedList()
last = llist.addToEmpty(2)
last = llist.addBegin(1)
last = llist.addEnd(3)
last = llist.addAfter(4,2)
llist.traverse()
Output
1 2 4 3
[forminator_quiz id=”3847″]
Space Complexity: O(1), as only temporary variables are being created.
So, in this article, we have tried to explain the most efficient approach to insert a node in a circular linked list. Inserting nodes at various positions in circular linked list is must to know from coding interviews perspective. 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.