C Exercises: Delete a node from the middle of a circular linked list
Last update on December 20 2021 09:10:56 (UTC/GMT +8 hours)Deletion from a Circular Linked List
We have already discussed circular linked list and traversal in a circular linked list in the below articles:
Introduction to circular linked list
Traversal in a circular linked list
In this article, we will learn about deleting a node from a circular linked list. Consider the linked list as shown below:
We will be given a node and our task is to delete that node from the circular linked list.
Examples:
Input : 2->5->7->8->10->(head node) data = 5 Output : 2->7->8->10->(head node) Input : 2->5->7->8->10->(head node) 7 Output : 2->5->8->10->(head node)Algorithm
Case 1: List is empty.
- If the list is empty we will simply return.
Case 2:List is not empty
- If the list is not empty then we define two pointers curr and prev and initialize the pointer curr with the head node.
- Traverse the list using curr to find the node to be deleted and before moving to curr to the next node, every time set prev = curr.
- If the node is found, check if it is the only node in the list. If yes, set head = NULL and free(curr).
- If the list has more than one node, check if it is the first node of the list. Condition to check this( curr == head). If yes, then move prev until it reaches the last node. After prev reaches the last node, set head = head -> next and prev -> next = head. Delete curr.
- If curr is not the first node, we check if it is the last node in the list. Condition to check this is (curr -> next == head).
- If curr is the last node. Set prev -> next = head and delete the node curr by free(curr).
- If the node to be deleted is neither the first node nor the last node, then set prev -> next = curr -> next and delete curr.
Delete middle of linked list
Given a singly linked list, delete the middle of the linked list. For example, if the given linked list is 1->2->3->4->5 then the linked list should be modified to 1->2->4->5
If there are even nodes, then there would be two middle nodes, we need to delete the second middle element. For example, if given linked list is 1->2->3->4->5->6 then it should be modified to 1->2->3->5->6.
If the input linked list is NULL, then it should remain NULL.
If the input linked list has 1 node, then this node should be deleted and a new head should be returned.
About Linked List
Linked List is a one of the DataStructure used for storing collection of data. A Linked List has the following properties:
- A Linked List is linear dynamic DataStructure.
- The number of nodes in Linked List is not fixed, it can grow and shrink on demand.
- Each node of the Linked List is made up of two items - the data and a reference to the next node.
- The Last node has reference to null.
- The entry point is called head
- If the list is empty then the head is null reference.
Basic Structure of Linked List-
Deletion in Circular Linked List in C
June 6, 2020
In this topic we want to discuss about delete the any node in circular linked list So, In this scenario is also have three ways to delete the node in linked list like doubly or singly linked list.
- Deletion at beginning
- Deletion at middle
- Deletion at end
1. It is not easy to reverse the linked list.
2. If proper care is not taken, then the problem of infinite loop can occur.
3. If we are at a node, then we can go to any node. But in linear linked list it is not possible to go to previous node. Easy implementation of some operations is possible
Deletion at beginning
When we delete the node at beginning then there are some condition as follows them:-
the first one is if the list have no element or node then( head=Null) will then we can’t delete the node because list is empty and print the simply “underflow” and then exit.
the second case if we have one more node in the list then we will put the simple condition (head->next==head) and when we delete the node in entire list then free the head pointer.
the third case is when we have more than one node in the list then we traverse the list by using ptr pointer. when the pointer will reach the last node ,then last node will also point to the head and then free the head by using free() method.
Algorithm
1: IF HEAD = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
2: SET PTR = HEAD
3: Repeat Step 4 while PTR → NEXT != HEAD
4: SET PTR = PTR → next
[END OF LOOP]
5: SET PTR → NEXT = HEAD → NEXT
6: FREE HEAD
7: SET HEAD = PTR → NEXT
8: EXIT
Deletion at middle
Firstly we create a circular linked list.
in deletion at middle or nth position we want to delete any node in the circular linked list so, if the list is empty then we are do same thing (head==Null). Else the list have more than one node then,
we exchange the address of previous node and next node where as delete the node.and the middle node will be delete,before the middle node and after the middle will be connected.
- First, find the length of the linked list. That is, the number of nodes in the list.
- Take two pointers previous and current to traverse the list. Such that previous is one position behind the current node.
- Take a variable count initialized to 0 to keep track of the number of nodes traversed.
- Traverse the list until the given index is reached.
- Once the given index is reached, do previous->next = current->next.
Deletion at end
There are three cases in of deleting a node in circular linked list.
Firstly we need to create a list,if we have empty list then simply the condition (head=null) is true then print the “underflow”.
Second case is when we have only one node in list then we will put the simple condition (head->next==head) and when we delete the node in entire list then free the head pointer.
Third is when we contains more than one node in linked list then we keep track of second last node of the list,and second last pointer(preptr) to point the head(ptr),and then make pointer is free(ptr).
Algorithm
1: IF HEAD = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
2: SET PTR = HEAD
3: Repeat Steps 4 and 5 while PTR -> NEXT != HEAD
4: SET PREPTR = PTR
5: SET PTR = PTR -> NEXT
[END OF LOOP]
6: SET PREPTR -> NEXT = HEAD
7: FREE PTR
8: EXIT
Code for Deletion in circular
#include<stdio.h>#include<stdlib.h>
void create(int);
void deletion_beginning(); //function declare for delete node at beginning
struct node
{
int data; //create node
struct node *next; // next pointer
struct node *prev; //previous pointer
};
struct node *head;
void main ()
{
int choice,item,choice1;
do
{
printf("1.Append List\n2.Delete Node from beginning\n3.Exit\n4.Enter your choice?");
scanf("%d",&choice);
switch(choice)
{
case 1: //switch case condition
printf("\nEnter the item\n");
scanf("%d",&item);
create(item);
break;
case 2:
deletion_beginning();
break;
case 3:
exit(0);
break;
default:
printf("\nPlease Enter valid choice\n");
}
} while(choice != 3);
}
void create(int item) //function declared for create the list
{
struct node *ptr = (struct node *) malloc(sizeof(struct node)); // for dynamic memory allocation
struct node *temp;
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
}
else
{
ptr->data=item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else
{
temp = head;
while(temp->next !=head)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
head -> prev = ptr;
ptr -> next = head;
}
}
printf("\nNode Inserted\n");
}
void deletion_beginning() // funtion calling for delete the node at beginning
{
struct node *temp;
if(head == NULL)
{
printf("\n UNDERFLOW\n");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nNode Deleted\n");
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = head -> next;
head -> next -> prev = temp;
free(head);
head = temp -> next;
printf("\nNode Deleted\n");
}
}
Login/Signup to comment
Python program to delete a node from the middle of the Circular Linked List
When it is required to delete a node from the middle of the circular linked list, a 'Node' class needs to be created. In this class, there are two attributes, the data that is present in the node, and the access to the next node of the linked list.
In a circular linked list, the head and the rear are adjacent to each other. They are connected to form a circle, and don't have 'NULL' value in the last node.
Another class needs to be created that would have an initialization function, and the head of the node would be initialized to 'None'. The size variable is initialized to 0.
There will be user defined functions that help add node to the linked list, print them on the console, and delete a node from the middle index.
Below is a demonstration for the same −