Operations on the circular linked list
We can do some operations on the circular linked list similar to the singly linked list which are:
- Insertion
- Deletion
A node can be added in three ways:
- Insertion at the beginning of the list
- Insertion at the end of the list
- Insertion in between the nodes
1) Insertion at the beginning of the list: To insert a node at the beginning of the list, follow these steps:
- Create a node, say T.
- Make T -> next = last -> next.
- last -> next = T.
And then,
2) Insertion at the end of the list: To insert a node at the end of the list, follow these steps:
- Create a node, say T.
- Make T -> next = last -> next;
- last -> next = T.
- last = T.
Before insertion,
After insertion,
3) Insertion in between the nodes: To insert a node in between the two nodes, follow these steps:
- Create a node, say T.
- Search for the node after which T needs to be inserted, say that node is P.
- Make T -> next = P -> next;
- P -> next = T.
Suppose 12 needs to be inserted after the node has the value 10,
After searching and insertion,
2. Deletion in a circular linked list:
1) Delete the node only if it is the only node in the circular linked list:
- Free the node’s memory
- The last value should be NULL A node always points to another node, so NULL assignment is not necessary.
Any node can be set as the starting point.
Nodes are traversed quickly from the first to the last.
2) Deletion of the last node:
- Locate the node before the last node (let it be temp)
- Keep the address of the node next to the last node in temp
- Delete the last memory
- Put temp at the end
3) Delete any node from the circular linked list: We will be given a node and our task is to delete that node from the circular linked list.
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.
- If the node is not present in the list return head and don’t do anything.
Below is the implementation for the above approach:
// C++ program to delete a given key from
// linked list.
#include <bits/stdc++.h>
using namespace std;
// Structure for a node
class Node {
public:
int data;
Node* next;
};
// Function to insert a node at the
// beginning of a Circular linked list
void push(Node** head_ref, int data)
{
// Create a new node and make head
// as next of it.
Node* ptr1 = new Node();
ptr1->data = data;
ptr1->next = *head_ref;
// If linked list is not NULL then
// set the next of last node
if (*head_ref != NULL) {
// Find the node before head and
// update next of it.
Node* temp = *head_ref;
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
// For the first node
ptr1->next = ptr1;
*head_ref = ptr1;
}
// Function to print nodes in a given
// circular linked list
void printList(Node* head)
{
Node* temp = head;
if (head != NULL) {
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
}
cout << endl;
}
// Function to delete a given node
// from the list
void deleteNode(Node** head, int key)
{
// If linked list is empty
if (*head == NULL)
return;
// If the list contains only a
// single node
if ((*head)->data == key && (*head)->next == *head) {
free(*head);
*head = NULL;
return;
}
Node *last = *head, *d;
// If head is to be deleted
if ((*head)->data == key) {
// Find the last node of the list
while (last->next != *head)
last = last->next;
// Point last node to the next of
// head i.e. the second node
// of the list
last->next = (*head)->next;
free(*head);
*head = last->next;
return;
}
// Either the node to be deleted is
// not found or the end of list
// is not reached
while (last->next != *head && last->next->data != key) {
last = last->next;
}
// If node to be deleted was found
if (last->next->data == key) {
d = last->next;
last->next = d->next;
free(d);
}
else
cout << "Given node is not found in the list!!!\n";
}
// Driver code
int main()
{
// Initialize lists as empty
Node* head = NULL;
// Created linked list will be
// 2->5->7->8->10
push(&head, 2);
push(&head, 5);
push(&head, 7);
push(&head, 8);
push(&head, 10);
cout << "List Before Deletion: ";
printList(head);
deleteNode(&head, 7);
cout << "List After Deletion: ";
printList(head);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
// Structure for a node
struct Node {
int data;
struct Node* next;
};
// Function to insert a node at the
// beginning of a Circular linked list
void push(struct Node** head_ref, int data)
{
// Create a new node and make head
// as next of it.
struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));
ptr1->data = data;
ptr1->next = *head_ref;
// If linked list is not NULL then
// set the next of last node
if (*head_ref != NULL) {
// Find the node before head and
// update next of it.
struct Node* temp = *head_ref;
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
// For the first node
ptr1->next = ptr1;
*head_ref = ptr1;
}
// Function to print nodes in a given
// circular linked list
void printList(struct Node* head)
{
struct Node* temp = head;
if (head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
}
printf("\n");
}
// Function to delete a given node
// from the list
void deleteNode(struct Node** head, int key)
{
// If linked list is empty
if (*head == NULL)
return;
// If the list contains only a
// single node
if ((*head)->data == key && (*head)->next == *head) {
free(*head);
*head = NULL;
return;
}
struct Node *last = *head, *d;
// If head is to be deleted
if ((*head)->data == key) {
// Find the last node of the list
while (last->next != *head)
last = last->next;
// Point last node to the next of
// head i.e. the second node
// of the list
last->next = (*head)->next;
free(*head);
*head = last->next;
return;
}
// Either the node to be deleted is
// not found or the end of list
// is not reached
while (last->next != *head && last->next->data != key) {
last = last->next;
}
// If node to be deleted was found
if (last->next->data == key) {
d = last->next;
last->next = d->next;
free(d);
}
else
printf("Given node is not found in the list!!!\n");
}
// Driver code
int main()
{
// Initialize lists as empty
struct Node* head = NULL;
// Created linked list will be
// 2->5->7->8->10
push(&head, 2);
push(&head, 5);
push(&head, 7);
push(&head, 8);
push(&head, 10);
printf("List Before Deletion: ");
printList(head);
deleteNode(&head, 7);
printf("List After Deletion: ");
printList(head);
return 0;
}
// Java program to delete a given key from
// linked list.
import java.io.*;
import java.util.*;
public class GFG {
/* structure for a node */
static class Node {
int data;
Node next;
};
/* Function to insert a node at the beginning of
a Circular linked list */
static Node push(Node head_ref, int data)
{
// Create a new node and make head as next
// of it.
Node ptr1 = new Node();
ptr1.data = data;
ptr1.next = head_ref;
/* If linked list is not null then set the
next of last node */
if (head_ref != null) {
// Find the node before head and update
// next of it.
Node temp = head_ref;
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
ptr1.next = ptr1; /*For the first node */
head_ref = ptr1;
return head_ref;
}
/* Function to print nodes in a given
circular linked list */
static void printList(Node head)
{
Node temp = head;
if (head != null) {
do {
System.out.printf("%d ", temp.data);
temp = temp.next;
} while (temp != head);
}
System.out.printf("\n");
}
/* Function to delete a given node from the list */
static Node deleteNode(Node head, int key)
{
if (head == null)
return null;
int flag = 0;
// Find the required node
Node curr = head, prev = new Node();
while (curr.data != key) {
if (curr.next == head) {
System.out.printf(
"Given node is not found in the list!!!\n");
flag = 1;
break;
}
prev = curr;
curr = curr.next;
}
// Check if the element is not present in the list
if (flag == 1)
return head;
// Check if node is only node
if (curr == head && curr.next == head) {
head = null;
return head;
}
// If more than one node, check if
// it is first node
if (curr == head) {
prev = head;
while (prev.next != head)
prev = prev.next;
head = curr.next;
prev.next = head;
}
// check if node is last node
else if (curr.next == head) {
prev.next = head;
}
else {
prev.next = curr.next;
}
return head;
}
/* Driver code */
public static void main(String args[])
{
/* Initialize lists as empty */
Node head = null;
/* Created linked list will be 2.5.7.8.10 */
head = push(head, 2);
head = push(head, 5);
head = push(head, 7);
head = push(head, 8);
head = push(head, 10);
System.out.printf("List Before Deletion: ");
printList(head);
head = deleteNode(head, 7);
System.out.printf("List After Deletion: ");
printList(head);
}
}
// This code is contributed by Susobhan Akhuli
using System;
// Structure for a node
public class Node {
public int data;
public Node next;
}
// Class for Circular Linked List
public class CircularLinkedList {
// Function to insert a node at the
// beginning of a Circular linked list
public static void Push(ref Node head_ref, int data)
{
// Create a new node and make head
// as next of it.
Node ptr1 = new Node();
ptr1.data = data;
ptr1.next = head_ref;
// If linked list is not NULL then
// set the next of last node
if (head_ref != null) {
// Find the node before head and
// update next of it.
Node temp = head_ref;
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
// For the first node
ptr1.next = ptr1;
head_ref = ptr1;
}
// Function to print nodes in a given
// circular linked list
public static void PrintList(Node head)
{
Node temp = head;
if (head != null) {
do {
Console.Write(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
Console.WriteLine();
}
// Function to delete a given node
// from the list
public static void DeleteNode(ref Node head, int key)
{
// If linked list is empty
if (head == null)
return;
// If the list contains only a
// single node
if (head.data == key && head.next == head) {
head = null;
return;
}
Node last = head, d;
// If head is to be deleted
if (head.data == key) {
// Find the last node of the list
while (last.next != head)
last = last.next;
// Point last node to the next of
// head i.e. the second node
// of the list
last.next = head.next;
head = last.next;
return;
}
// Either the node to be deleted is
// not found or the end of list
// is not reached
while (last.next != head && last.next.data != key) {
last = last.next;
}
// If node to be deleted was found
if (last.next.data == key) {
d = last.next;
last.next = d.next;
}
else
Console.WriteLine(
"Given node is not found in the list!!!");
}
// Driver code
public static void Main()
{
// Initialize lists as empty
Node head = null;
// Created linked list will be
// 2->5->7->8->10
Push(ref head, 2);
Push(ref head, 5);
Push(ref head, 7);
Push(ref head, 8);
Push(ref head, 10);
Console.Write("List Before Deletion: ");
PrintList(head);
DeleteNode(ref head, 7);
Console.Write("List After Deletion: ");
PrintList(head);
}
}
// Javascript program to delete a given key from linked list.
// Structure for a node
class Node {
constructor() {
this.data;
this.next;
}
}
// Function to insert a node at the
// beginning of a Circular linked list
function push(head, data) {
// Create a new node and make head
// as next of it.
var ptr1 = new Node();
ptr1.data = data;
ptr1.next = head;
// If linked list is not NULL then
// set the next of last node
if (head != null) {
// Find the node before head and
// update next of it.
let temp = head;
while (temp.next != head) temp = temp.next;
temp.next = ptr1;
}
// For the first node
else ptr1.next = ptr1;
head = ptr1;
return head;
}
// Function to print nodes in a given
// circular linked list
function printList(head) {
let tempp = head;
if (head != null) {
do {
console.log(tempp.data);
tempp = tempp.next;
} while (tempp != head);
}
}
// Function to delete a given node
// from the list
function deleteNode(head, key) {
// If linked list is empty
if (head == null) return;
// If the list contains only a
// single node
if (head.data == key && head.next == head) {
head = null;
return;
}
let last = head;
// If head is to be deleted
if (head.data == key) {
// Find the last node of the list
while (last.next != head) last = last.next;
// Point last node to the next of
// head i.e. the second node
// of the list
last.next = head.next;
head = last.next;
return;
}
// Either the node to be deleted is
// not found or the end of list
// is not reached
while (last.next != head && last.next.data != key) {
last = last.next;
}
// If node to be deleted was found
if (last.next.data == key) {
d = last.next;
last.next = d.next;
d = null;
} else console.log("Given node is not found in the list!!!");
}
// Driver code
// Initialize lists as empty
head = null;
// Created linked list will be
// 2->5->7->8->10
head = push(head, 2);
head = push(head, 5);
head = push(head, 7);
head = push(head, 8);
head = push(head, 10);
console.log("List Before Deletion: ");
printList(head);
deleteNode(head, 7);
console.log("List After Deletion: ");
printList(head);
# Python program to delete a given key from linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to insert a node at the
# beginning of a Circular linked list
def push(head, data):
# Create a new node and make head as next of it.
newP = Node(data)
newP.next = head
# If linked list is not NULL then
# set the next of last node
if head != None:
# Find the node before head and
# update next of it.
temp = head
while (temp.next != head):
temp = temp.next
temp.next = newP
else:
newP.next = newP
head = newP
return head
# Function to print nodes in a given circular linked list
def printList(head):
if head == None:
print("List is Empty")
return
temp = head.next
print(head.data, end=' ')
if (head != None):
while (temp != head):
print(temp.data, end=" ")
temp = temp.next
print()
# Function to delete a given node
# from the list
def deleteNode(head, key):
# If linked list is empty
if (head == None):
return
# If the list contains only a
# single node
if (head.data == key and head.next == head):
head = None
return
last = head
# If head is to be deleted
if (head.data == key):
# Find the last node of the list
while (last.next != head):
last = last.next
# Point last node to the next of
# head i.e. the second node
# of the list
last.next = head.next
head = last.next
return
# Either the node to be deleted is
# not found or the end of list
# is not reached
while (last.next != head and last.next.data != key):
last = last.next
# If node to be deleted was found
if (last.next.data == key):
d = last.next
last.next = d.next
d = None
else:
print("Given node is not found in the list!!!")
# Driver code
# Initialize lists as empty
head = None
# Created linked list will be
# 2->5->7->8->10
head = push(head, 2)
head = push(head, 5)
head = push(head, 7)
head = push(head, 8)
head = push(head, 10)
print("List Before Deletion: ")
printList(head)
deleteNode(head, 7)
print("List After Deletion: ")
printList(head)
Output
List Before Deletion: 10 8 7 5 2 List After Deletion: 10 8 5 2
Time Complexity: O(N), Worst case occurs when the element to be deleted is the last element and we need to move through the whole list.
Auxiliary Space: O(1), As constant extra space is used.