# Deletion At Different Positions in A Circular Linked List ### Introduction

The linked list is one of the most important concepts to know while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews.

### Problem Statement

We will be given a circular linked list and a position, and we need to delete the element present at that position in the list.

Note: we need to follow 0 based indexing while deleting the nodes

### Problem Statement Understanding

Let’s try to understand the problem with the help of an example.

If the linked list given to us is: Now, if position = 0.

• Then, we need to delete the first node of the list, and after deletion, the list will now look like this: If the position = 2.

• Then, we need to delete the third node, and the list after deletion will look like this: At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

• If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

### Approach

We will divide our problem into three sections:
1) When position = 0:
a) It means that we need to delete the first node of the circular linked list.
b) In this case, we need to reach the last node and then connect it with the second node.
c) After that, we will update the head pointer for the list.

2) When position = length of the list (we need to delete the last node):
a) In this case, we need to reach the last second node and connect it with the first node.

3) When we need to delete a middle node:
a) We need to keep track of node position while iterating the list.
b) when we find the node at the specified position, we need to connect its previous node with its next node.

Let’s move to the algorithm section to see the above approach in more depth.

### Algorithm

1) First, calculate the length of the list and save it in len variable.
2) Initialize a variable count by 1.
3) If the head is NULL, then it means that the list is empty, so return from the function.
4) If the position is less than 0 or greater than len, then return from the function.
5) If position == 0 then, call deleteFirstNode function:

• Initialize curr and left with the head of the list.
• Return from the function if the head is NULL.
• Make the head NULL and return from the function, if left->next is left (this is the case when there is only 1 node in the list).
• Run a while loop till left->next is not equal to head.
• Inside the loop, advance left by one node and update curr with the next node of left.
• Now, when the loop is executed completely, connect the next pointer of left to the next node of curr.
• Update the head node by left->next.
• Delete the old head node, i.e., curr.
6) If position == (len-1) then, call deleteLastNode function:
• Initialize the curr pointer with head and left with NULL.
• Return from the function if the head is NULL.
• Make the head NULL and return from the function, if curr->next is curr (this is the case when there is only 1 node in the list).
• Run a while loop till curr->next is not equal to head.
• Inside the loop, save the value of curr in left and advance curr by one node.
• Now, when the loop is executed completely, connect the next pointer of left to the next node of curr.
• Update the head node by left->next.
• Delete the old head node, i.e., curr.
7) Run a while loop till len is positive.
• If position is equal to count then,
• Connect previous node’s next pointer to current node’s next pointer.
• Delete the curr pointer and return from the function.
• Advance previous by one node and update curr to the node next to previous.
• Decrement len and increment count by one.
8) Return from the function once while loop breaks.

### Dry Run   ### Code Implementation

```#include
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int d)
{
data = d;
next = NULL;
}
};
// This function will print data of
// all the nodes present in the list
{

// In case of an empty list:
printf("\nDisplay List is empty\n");
return;
}

// iterate the complete list
else {
do {
cout<<(temp->data);
temp = temp->next;
cout<<" ";
}
cout<<'\n';
}

// This function calculates the
// number of nodes in the list
{
int len = 0;

// in case of an empty list, return 0
return 0;
}

// iterate the complete list
else {
do {
temp = temp->next;
len++;
}
return len;
}

// This node deletes the first node
// of the list
{

// if the list is empty
printf("\nList is empty\n");
return;
}

// In case, the list has a single node
if (left->next == left) {
return;
}

// iterate the complete list

left = left->next;
curr = left->next;
}

// left will be pointing to the last node
// and curr will be the head of the list
// so, we will connect left with the curr->next
left->next = curr->next;

// make second node as head node
free(curr);

return;
}

// This function deletes the last
// node of the list
{
Node *curr = *head,  *left = NULL;

// if the list is empty
printf("\nList is empty\n");
return;
}

// In case, the list has a single node
if (curr->next == curr) {
return;
}

//iterate the list
left = curr;
curr = curr->next;
}

left->next = curr->next;
free(curr);

return;
}

{
// find length of the list
int count = 1;

// check if the list is empty
printf("\nDelete Last List is empty\n");
return;
}

// check if the given position is out of
// bound of the list
if (position >= len || position < 0) {
return;
}

// first node deletion
if (position == 0) {
return;
}
// last node deletion
else if(position == len-1){
return;
}

// iterate the complete list
while (len > 0) {

// delete the node when position is found
if (position == count) {
previous->next = curr->next;
free(curr);
return;
}
previous = previous->next;
curr = previous->next;
len--;
count++;
}
return;
}

int main()
{
cout<<"Original list ";
cout<<"After deleting third node ";
cout<<"After deleting last node ";
cout<<"After deleting first node ";
}
```
```#include
#include

struct Node {
int data;
struct Node* next;
};
// This function will print data of
// all the nodes present in the list
{

// In case of an empty list:
printf("\nDisplay List is empty\n");
return;
}

// iterate the complete list
else {
do {
printf("%d",temp->data);
temp = temp->next;
printf(" ");
}
printf("\n");
}
// This function calculates the
// number of nodes in the list
{
int len = 0;

// in case of an empty list, return 0
return 0;
}

// iterate the complete list
else {
do {
temp = temp->next;
len++;
}
return len;
}
// This node deletes the first node
// of the list
{

// if the list is empty
printf("\nList is empty\n");
return;
}

// In case, the list has a single node
if (left->next == left) {
return;
}

// iterate the complete list

left = left->next;
curr = left->next;
}

// left will be pointing to the last node
// and curr will be the head of the list
// so, we will connect left with the curr->next
left->next = curr->next;

// make second node as head node
free(curr);

return;
}
// This function deletes the last
// node of the list
{
struct Node *curr = *head,  *left = NULL;

// if the list is empty
printf("\nList is empty\n");
return;
}

// In case, the list has a single node
if (curr->next == curr) {
return;
}

//iterate the list
left = curr;
curr = curr->next;
}

left->next = curr->next;
free(curr);

return;
}
void deleteAtPosition(struct Node** head, int position)
{
// find length of the list
int count = 1;

// check if the list is empty
printf("\nDelete Last List is empty\n");
return;
}

// check if the given position is out of
// bound of the list
if (position >= len || position < 0) {
return;
}

// first node deletion
if (position == 0) {
return;
}
// last node deletion
else if(position == len-1){
return;
}

// iterate the complete list
while (len > 0) {

// delete the node when position is found
if (position == count) {
previous->next = curr->next;
free(curr);
return;
}
previous = previous->next;
curr = previous->next;
len--;
count++;
}
return;
}

void push(struct Node** head_ref, int data)
{
struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));
ptr1->data = data;

temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1; /*For the first node */

}
int main()
{
printf("Original list ");
printf("After deleting third node ");
printf("After deleting last node ");
printf("After deleting first node ");
}

```
```class DeletetionAtPos
{

// structure for a node
static class Node
{
int data;
Node next;
};

// Function to insert a node at the end of
static Node Insert(Node head, int data)
{

// Create a new node
Node newNode = new Node();

// insert data into newly created node
newNode.data = data;

// check list is empty
// if not have any node then
// make first node it
{
newNode.next = newNode;
}

// if list have already some node
else
{

// move first node to last node
{
current = current.next;
}

// put new node address into last
current.next = newNode;
}
}

// Function print data of list
{

// if list is empty, simply show message
{
System.out.printf("\nDisplay List is empty\n");
return;
}

// traverse first to last node
else
{
do
{
System.out.printf("%d ", current.data);
current = current.next;
}
}

// Function return number of nodes present in list
{
int count = 0;

// if list is empty
// simply return length zero
{
return 0;
}

// traverse first to last node
else
{
do
{
current = current.next;
count++;
}
return count;
}

// Function delete First node of
{

// check list have any node
// if not then return
{
System.out.printf("\nList is empty\n");
return null;
}

// check list have single node
// if yes then delete it and return
if (previous.next == previous)
{
return null;
}

// traverse second to first
{
previous = previous.next;
next = previous.next;
}

// now previous is last node and
// next is first node of list
// put in last node(previous) link
previous.next = next.next;

// make second node as head node

}

// Function to delete last node of
{

// check if list doesn't have any node
// if not then return
{
System.out.printf("\nList is empty\n");
return null;
}

// check if list have single node
// if yes then delete it and return
if (current.next == current)
{
return null;
}

// move first node to last
// previous
{
previous = current;
current = current.next;
}

previous.next = current.next;

}

// Function delete node at a given position
static Node DeleteAtPosition( Node head, int index)
{
// Find length of list
int count = 1;

// check list have any node
// if not then return
{
System.out.printf("\nDelete Last List is empty\n");
return null;
}

// given index is in list or not
if (index >= len || index < 0)
{
return null;
}

// delete first node
if (index == 0)
{
}

// traverse first to last node
while (len > 0)
{

// if index found delete that node
if (index == count)
{
previous.next = next.next;

}
previous = previous.next;
next = previous.next;
len--;
count++;
}
}

// Driver Code
public static void main(String args[])
{

// Deleting Node at position
System.out.printf("Initial List: ");
System.out.printf("\nAfter Deleting node at index 4: ");

// Deleting first Node
System.out.printf("\n\nInitial List: ");
System.out.printf("\nAfter Deleting first node: ");

// Deleting last Node
System.out.printf("\n\nInitial List: ");
System.out.printf("\nAfter Deleting last node: ");
}
}

```
```
class Node:
def __init__(self, new_data):
self.data = new_data
self.next = None
self.prev = None

# This function to insert a node at the end of a list

newNode = Node(0)

if (newNode == None):

print("\nMemory Error\n")
return None

newNode.data = data

newNode.next = newNode

else:

current = current.next

current.next = newNode

# This function will print data of all the nodes present in the list

# In case of an empty list:

print("\nDisplay List is empty\n")
return

# iterate the complete list
else:

while(True):
print( current.data,end=" ")
current = current.next
break

# This function calculates the number of nodes in the list
count = 0

# in case of an empty list, return 0

return 0

# iterate the complete list
else:

while(True):
current = current.next
count = count + 1
break

return count

# This node deletes the first node of the list

print("\nList is empty")
return None

if (previous.next == previous) :

return None

previous = previous.next
next = previous.next

previous.next = next.next

# This function deletes the last node of the list
previous = None

print("\nList is empty")
return None

if (current.next == current) :
return None

previous = current
current = current.next

previous.next = current.next

# This function delete node at a given position of List

# Find length of list
count = 1

# check if the list is empty
print("\nDelete Last List is empty")
return None

# check if the given position is out of bound of the list
if (index >= len or index < 0) :
return None

# first node deletion
if (index == 0) :

# iterate the complete list
while (len > 0):

# delete the node when position is found
if (index == count):
previous.next = next.next

previous = previous.next
next = previous.next
len = len - 1
count = count + 1

print("Original List: ")
print("\nAfter deleting node at index 3: ")

print("\nAfter deleting last node: ")

print("\nAfter Deleting first node: ")
```

#### Output

Original list 3 7 2 5
After deleting third node 3 7 5
After deleting last node 3 7
After deleting first node 7

Time Complexity: O(n), where n is the number of nodes in the list
[forminator_quiz id=”5474″]

So, in this blog, we have tried to explain how you can delete nodes at different positions in a circular list in the most optimal way. If you want to practice more questions on linked lists, feel free to solve them at Prepbytes (Linked Lists).