Deletion in Circular Linked List Data Structure | DSA Tutorials

Deletion in Circular Linked List – To perform deletion in a circular linked list, we need to maintain and store the reference of the last node of the list. Because using the reference of the last node, the deletion operation can be done in constant time.

Deletion in Circular Linked List

So in this tutorial, we are going to learn how to

1. Deletion of the first node in the circular linked list.
2. Delete the only node of the list.
3. Delete the last node of the list.
4. Delete a node at any position in the list.

Delete the first node of the circular linked list

Let’s say we have a list that has four nodes in it.

To delete the first node of the list, we simply store the second node’s reference in the last node’s link part.

Now the first node is deleted from the linked list.

Delete the only node

If we have a linked list that has only one node.

Then, to delete this only node, we simply store None or a null value into the last variable.

So now our list becomes empty.

Delete the last node

To delete the last node first, we need to find a reference p of the predecessor of the last node.

Then we store the first node’s reference into the linked part of node p.

After that, we update the list variable’s position. Because after the deletion of the last node, the node p becomes the last node of the list.

So now, after performing these operations, the last node is deleted.

Delete a node at the kth position

To delete a node at position x, first, we need to find the reference to the predecessor of the node. Like we want to delete the third node on the list. Then we need to find the reference p of the second node.

After that, we store the node’s reference that comes after the node that we want to delete in the linked part of node p.

So now the third node’s deleted from the linked list.