  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Circular Linked List – Insertion

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)

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)

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)
{
}
Node newNode=new Node(data);
newNode.next=last.next;
last.next=newNode;

return last;
}
```
```def addBegin(self, data):

if (self.last == None):

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)

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)

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)
{
}
Node NEwNode=new Node(data);
NewNode.next=last.next;
last.next=NewNode;
last=NewNode;

return last;
}
```
```def addEnd(self, data):

if (self.last == None):

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)

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)

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;

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)

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)

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;

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)

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)

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;

traverse(last);
}
}
```
```class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):
self.last = None

if (self.last != None):
return self.last

NewNode = Node(data)
self.last = NewNode

self.last.next = self.last
return self.last

if (self.last == None):

NewNode = Node(data)
NewNode.next = self.last.next
self.last.next = NewNode

return self.last

if (self.last == None):

NewNode = Node(data)
NewNode.next = self.last.next
self.last.next = NewNode
self.last = NewNode

return self.last

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.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.