Deletion from beginning in circular linked list in C++

How to delete from beginning in circular linked list?

In this article, we will learn how to write a program for deletion from beginning in circular linked list in C++.

So to delete node from circular linked list we first need to create a circular linked list and then we can delete the node from beginning. And after deleting the first node we will make second node as head of the list and will link the pointer of last node with the new head node.

Delete from beginning in circular linked list in C++

Steps to delete from beginning in circular linked list in CPP

  1. If the circular linked list is empty, terminate function.
  2. Else define two node pointers(p and temp).
  3. Initialize p with head.
  4. Now traverse until pointer of p points to the head
  5. Now store head in the second node pointer i.e temp.
  6. Make second node as new head of the list.
  7. Link the pointer of last node with new head.
  8. Free temp i.e the node pointer storing the previous head of the list.
struct Node
{
  int num;
  struct Node *next;
};
Deletion in circular linked list in C++ – 2

Algorithm to write a CPP program to delete from beginning in Circular Linked List

  • STRUCT P &TEMP
  • P=HEAD
  • WHILE(P->NEXT!=HEAD)
  • P=P->NEXT
  • END WHILE
  • TEMP=HEAD
  • HEAD=HEAD->NEXT
  • P->NEXT=HEAD
  • FREE(TEMP)

C++ program for deletion from beginning in circular linked list

A C++ program for deletion from the beginning in a circular linked list removes the first node while ensuring the circular connection between the remaining nodes stays intact. This operation updates the head pointer to the next node and maintains the loop structure of the list efficiently.

Run

#include<iostream>
using namespace std;

struct Node
{
  int num;
  struct Node *next;
} *head;

void insertStart (struct Node **head, int data)	//function to create linked list
{
  struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
  newNode->num = data;

  // if its the first node being entered
  if (*head == NULL)
    {
      *head = newNode;		// assigning itself as head
      (*head)->next = *head;	// assigning itself as next node

      cout << newNode->num << " Inserted\n"; return; } // if CLL already as >=1 node
  struct Node *curr = *head;

  // traverse till last node in CLL
  while (curr->next != *head)
    {
      curr = curr->next;
    }

  curr->next = newNode;		// last node's next as this new node
  newNode->next = *head;	// new node's next as current head node

  *head = newNode;		// changing head node to this new node
  cout << newNode->num << " Inserted\n"; // previous head node becomes 2nd node } void deleteBegin (struct Node **head) //function to delete beginning node from the circular linked list { struct Node *p, *temp; p = *head; while (p->next != (*head))
    {
      p = p->next;
    }
  temp = *head;
  p->next = (*head)->next;
  *head = (*head)->next;

  free (temp);
}

void display (struct Node *head)
{

  cout << "\nCircular Linked List : " << endl;

  // if circular linked list is empty currently
  if (head == NULL)
    return;

  struct Node *temp = head;

  // since we need to take care of circular nature of linked list
  do
    {
      cout << temp->num << " "; temp = temp->next;

    }
  while (temp != head);
  cout << endl;
}

int main ()				//main function
{
  // first node will be null at creation    
  struct Node *head = NULL;

  insertStart (&head, 1);
  insertStart (&head, 2);
  insertStart (&head, 3);
  insertStart (&head, 4);
  insertStart (&head, 5);
  cout << "Before insertion ";
  display (head);
  deleteBegin (&head);
  cout << "After insertion ";
  display (head);
  return 0;
}

Output:

1 Inserted
2 Inserted
3 Inserted
4 Inserted
5 Inserted
Before insertion 
Circular Linked List : 
5 4 3 2 1 
After insertion 
Circular Linked List : 
4 3 2 1

Explanation:

  • The code illustrates how a circular linked list can be implemented in C++, including node insertion and deletion operations.
  • In the insertStart() function, a new node is created and linked such that it becomes the new head, while the last node’s pointer is updated to maintain the circular structure.
  • During deletion in deleteBegin(), the first node is removed by adjusting the last node’s pointer to the next of the current head and freeing the removed node’s memory.
  • The display() function uses a do-while loop to traverse and print the list elements, ensuring all nodes are displayed exactly once in a circular manner.
  • Inside the main() function, nodes are inserted sequentially, then the first node is deleted, demonstrating the working of insertion and deletion in a circular linked list.

Time and Space Complexity:

OperationTime ComplexitySpace Complexity
Insert Node at BeginningO(n)O(1)
Delete Node from BeginningO(n)O(1)
Display ListO(n)O(1)

To wrap it up:

Deleting a node from the beginning of a circular linked list involves identifying the last node, updating its next pointer to the new head, and freeing the memory of the removed node. This ensures that the circular structure of the list remains intact even after deletion.

This operation plays an important role in understanding how circular linked lists manage dynamic data efficiently. With the clear explanation and code provided, you can now implement and modify this logic confidently in C++ for various programming and interview scenarios.

FAQs

When the first node is deleted, the head pointer is moved to the next node, and the last node’s next pointer is updated to point to the new head.

No, deletion isn’t possible in an empty list. The function should first check if the head is NULL before attempting deletion.

The time complexity is O(n) because we may need to traverse the list to update the last node’s pointer.

If the circular linked list has a single node, deleting it will make the head NULL, effectively making the list empty.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Circular Linked List

  • Introduction to Circular Linked List
    Click Here
  • Circular Linked List Applications
    Click Here
  • Circular Linked List in –
    C | C++ | Java
  • Insertion in Circular Linked List –
    C | C++ | Java
  • Insertion at the beginning–
    C | C++ | Java
  • Insertion at the end –
    C | C++ | Java
  • Insertion at nth position –
    C | C++ | Java
  • Deletion in Circular Linked List –
    C | C++ | Java
  • Deletion from beginning in Circular Linked List –
    C | C++ | Java
  • Deletion from nth position in Circular Linked List –
  • Deletion from end in Circular Linked List –
    C | C++ | Java
  • Insertion and Deletion in Circular Linked List – C | C++ | Java
  • Split a Circular Linked List in two halves –
    C | C++ | Java
  • Count nodes in Circular Linked List –
    C | C++ | Java
  • Sorted Insert In Circular Linked List –
    C | C++ | Java
  • Insertion in the middle in Circular Linked List –
    C | C++ | Java

Circular Linked List