C Data Structures - Circular Doubly Linked List Other Related Topics

C - Delete odd nodes of the Circular Doubly Linked List



Deleting odd nodes of a circular doubly linked list requires traverse through the list and deleting odd nodes one by one. It involves the following process. If the list contains only head then make the head null. If the list contains more than one element then delete the head and adjust the link of last element with the new head. If next of head is not head then, create three nodes - evenNode pointing to head, oddNode pointing to next of head and temp to store last even node. Then delete oddNode and update evenNode and oddNode to next set of odd-even nodes and continue the process till any of the node reaches head. After that if evenNode reaches head, make next of temp as head else make next of evenNode as head and adjust other links accordingly.

The function deleteOddNodes is created for this purpose. It is a 5-step process.

void deleteOddNodes(struct Node** head_ref) {
  //1. if head is the only element element in 
  //   list make the head as null  
  if(*head_ref != NULL && (*head_ref)->next == *head_ref) {
    free(*head_ref);
    *head_ref = NULL;
  } else if(*head_ref != NULL) {

    //2. if the list contains more than one element
    //   delete the head and adjust the link of
    //   last element with the new head       
    struct Node* temp = *head_ref;
    while(temp->next != *head_ref) {
      temp = temp->next;
    }
    temp->next = (*head_ref)->next;
    (*head_ref)->next->prev = temp;
    free(*head_ref);
    *head_ref = temp->next;

    //3. create evenNode node - pointing to head
    //   oddNode node - pointing to next of head
    //   temp node - to store last even node
    if(*head_ref != NULL && (*head_ref)->next != *head_ref) {

      struct Node* evenNode = *head_ref;
      struct Node* oddNode = (*head_ref)->next; 
      while(1) {
        
        //4. delete odd node and update evenNode and 
        //   oddNode to next set of odd-even nodes update
        //   temp node to latest evenNode node continue
        //   the process till any of the node reaches head
        temp = evenNode;
        evenNode->next = oddNode->next;
        evenNode->next->prev = evenNode;
        free(oddNode);
        evenNode = evenNode->next;
        oddNode = evenNode->next;
        if(evenNode == *head_ref || oddNode == *head_ref)
          break;
      }
      
      //5. if evenNode reaches head, make next of temp
      //   as head else make next of evenNode as head
      //   and adjust other links accordingly
      if(evenNode == *head_ref) {
        temp->next = *head_ref;
        (*head_ref)->prev = temp;
      } else {
        evenNode->next = *head_ref;
        (*head_ref)->prev = evenNode;
      }
    }
  } 
}

The below is a complete program that uses above discussed concept of deleting odd nodes of a circular doubly linked list.

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

//node structure
struct Node {
  int data;
  struct Node* next;
  struct Node* prev;
};

//Add new element at the end of the list
void push_back(struct Node** head_ref, int newElement) {  
  struct Node *newNode, *temp;
  newNode = (struct Node*)malloc(sizeof(struct Node)); 
  newNode->data = newElement;  
  newNode->next = NULL;
  newNode->prev = NULL;
  if(*head_ref == NULL) {
    *head_ref = newNode;
     newNode->next = *head_ref;
     newNode->prev = *head_ref;
  } else {
    temp = *head_ref;
    while(temp->next != *head_ref) {
      temp = temp->next;
    }    
    temp->next = newNode;
    newNode->next = *head_ref;
    newNode->prev = temp;
    (*head_ref)->prev = newNode;
  }
}

//delete odd nodes of the list
void deleteOddNodes(struct Node** head_ref) {
  if(*head_ref != NULL && (*head_ref)->next == *head_ref) {
    free(*head_ref);
    *head_ref = NULL;
  } else if(*head_ref != NULL) {      
    struct Node* temp = *head_ref;
    while(temp->next != *head_ref) {
      temp = temp->next;
    }
    temp->next = (*head_ref)->next;
    (*head_ref)->next->prev = temp;
    free(*head_ref);
    *head_ref = temp->next;

    if(*head_ref != NULL && (*head_ref)->next != *head_ref) {

      struct Node* evenNode = *head_ref;
      struct Node* oddNode = (*head_ref)->next; 
      while(1) {
        temp = evenNode;
        evenNode->next = oddNode->next;
        evenNode->next->prev = evenNode;
        free(oddNode);
        evenNode = evenNode->next;
        oddNode = evenNode->next;
        if(evenNode == *head_ref || oddNode == *head_ref)
          break;
      }
      
      if(evenNode == *head_ref) {
        temp->next = *head_ref;
        (*head_ref)->prev = temp;
      } else {
        evenNode->next = *head_ref;
        (*head_ref)->prev = evenNode;
      }
    }
  } 
}

//display the content of the list
void PrintList(struct Node* head_ref) {
  struct Node* temp = head_ref;
  if(head_ref != NULL) {
    printf("The list contains: ");
    while (1) {
      printf("%i ",temp->data);
      temp = temp->next;
      if(temp == head_ref)
        break;    
    }
    printf("\n");
  } else {
    printf("The list is empty.\n");
  }   
}

// test the code 
int main() {
  struct Node* MyList = NULL;

  //Add five elements in the list.
  push_back(&MyList, 10);
  push_back(&MyList, 20);
  push_back(&MyList, 30);
  push_back(&MyList, 40);
  push_back(&MyList, 50);

  //Display the content of the list.
  PrintList(MyList);

  //delete odd nodes of the list
  deleteOddNodes(&MyList);

  printf("After deleting odd nodes:\n");
  //Display the content of the list.
  PrintList(MyList);

  return 0; 
}

The above code will give the following output:

The list contains: 10 20 30 40 50 
After deleting odd nodes:
The list contains: 20 40