C Program for Deletion from nth position in circular linked list

C Program for Deletion from nth position in Circular Linked List 1

Perform deletion at nth node in circular linked list

In this section we will learn how to write a code in C Program for Deletion from nth position in circular linked list. The circular linked list have more features than doubly or singly  linked list. In circular linked list the last node pointer point the first node of the list, hence make a loop.
For Example :- Input : 45 2 3 9 84 2
Enter the position you want to delete node= 2
Output : 45 3 9 84 2

Deletion From nth Position in Circular Linked List in C

Working

  • Assign the two pointer, name them u and v.
  • Assign a new count variable as w.
  • And Assign delete with position – 1.
  • Then, run for loop while w index not equal to delete.
  • In this for loop make u = v and u = u → next pointer.
  • As the value of w increase one on every successful iteration of loop.
  • Then make the next of v equal to next of u.
  • At last free the node pointed by pointer u.

Construction of node in circular linked list :-

struct node
 {
     int data; 
     struct node* next;  
 };
C Program for Deletion from nth position in circular linked list

Algorithm

  • Step 1: MAKE A TWO NEW NODE U AND V
  • Step 2: SET VALUE OF W = 0
  • Step 3: THEN SET DELETE = POSITION-1
  • Step 4: MAKE U = HEAD
  • Step 5: MAKE A LOOP WHILE (W != DELETE)
  • Step 6: SET VALUE EQUAL TO V = U
  • Step 7: THEN U = U → NEXT
  • Step 8: INCREMENT VARIABLE VALUE W++
  • Step 9: AT LAST V → NEXT = U →NEXT
  • Step 10: FREE NODE U

C Program For Deletion From nth position

Run
#include< stdio.h>
#include< stdlib.h>

// structure for Circular Linked List
struct Node
{
  int data;
  struct Node *next;
};

int calcSize (struct Node *head);

void deleteBegin(struct Node **head)
{

  struct Node *tempNode = *head;

  // if there are no nodes in Linked List can't delete
  if (*head == NULL)
    {
      printf ("Linked List Empty, nothing to delete");
      return;
    }

  // if only 1 node in CLL
  if (tempNode->next == *head)
    {
      *head = NULL;
      return;
    }

  struct Node *curr = *head;

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

  // assign last node's next to 2nd node in CLL
  curr->next = (*head)->next;

  // move head to next node
  *head = (*head)->next;
  free (tempNode);
}

void deleteEnd (struct Node **head)
{
  struct Node *tempNode = *head;
  struct Node *previous;

  // if there are no nodes in Linked List can't delete
  if (*head == NULL)
    {
      printf ("Linked List Empty, nothing to delete");
      return;
    }

  // if Linked List has only 1 node
  if (tempNode->next == *head)
    {
      *head = NULL;
      return;
    }

  // else traverse to the last node
  while (tempNode->next != *head)
    {
      // store previous link node as we need to change its next val
      previous = tempNode;
      tempNode = tempNode->next;
    }
  // Curr assign 2nd last node's next to head
  previous->next = *head;
  // delete the last node
  free (tempNode);
  // 2nd last now becomes the last node
}

void deletePos (struct Node **head, int n)
{

  int size = calcSize (*head);

  if (n < 1 || size < n) {
      printf ("Can't delete, %d is not a valid position\n", n);
      }
      else if (n == 1)
      deleteBegin(head);
      else if (n == size) 
      deleteEnd (head);
      else 
      { 
          struct Node *tempNode = *head;
          struct Node *previous; // traverse to the nth node
          while (--n) { // store previous link node as we need to change its next val 
          previous = tempNode; 
          tempNode = tempNode->next;
	}

      // change previous node's next node to nth node's next node
      previous->next = tempNode->next;
      // delete this nth node
      free (tempNode);
    }
}

void insert (struct Node **head, int data)
{
  struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
  newNode->data = data;

  if (*head == NULL)
    {
      *head = newNode;
      (*head)->next = *head;
      return;
    }

  struct Node *curr = *head;

  while (curr->next != *head)
    {
      curr = curr->next;
    }

  curr->next = newNode;
  newNode->next = *head;
  *head = newNode;
}

int calcSize (struct Node *head)
{
  int size = 0;
  struct Node *temp = head;

  if (temp == NULL)
    return size;

  do
    {
      size++;
      temp = temp->next;

    }
  while (temp != head);

  return size;
}

void display (struct Node *head)
{
  // if there are no node in CLL
  if (head == NULL)
    return;

  struct Node *temp = head;

  //need to take care of circular structure of CLL
  do
    {
      printf ("%d ", temp->data);
      temp = temp->next;

    }
  while (temp != head);
  printf ("\n");
}

int main ()
{

  // first node will be null at creation    
  struct Node *head = NULL;

  insert (&head, 10);
  insert (&head, 11);
  insert (&head, 12);
  insert (&head, 13);
  insert (&head, 14);
  insert (&head, 15);
  insert (&head, 16);

  display (head);

  deletePos (&head, 3);
  display (head);

  return 0;
}
16 15 14 13 12 11 10 
16 15 13 12 11 10 

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

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