Skip to main content

Deletion of last node in circular doubly list

Now we will see how to delete node at last position in circular doubly link list.

Algorithm to delete node at last position in circular doubly link list:

  • Declare TEMP = START
  • If list has no node i.e. [START == NULL]
    • Deletion not possible
  • Else If list have only one node i.e. START->NEXT = NULL
    • Set START = NULL
  • Else
    • Set TEMP = START->PREV
    • Set START->PREV->PREV->NEXT = START
    • Set START->PREV = START->PREV->PREV
  • Free (TEMP)
  • End If;

Function to delete last node in circular doubly link list:


int deleteAtLast(NODE **start){
 NODE *temp = *start;
 int info = -1;
 if(*start == NULL){
  printf("\nError: The list has no nodes\n");
 }
 else{
  if((*start)->next == *start){
   *start = NULL;
  }
  else{
   temp = (*start)->prev;
   (*start)->prev->prev->next = *start;
   (*start)->prev = (*start)->prev->prev;
  }
  info = temp->info;
  free(temp);
 }
 return info;
}
 

Program to delete last node in the circular doubly link list:


#include <stdio.h>
#include <malloc.h>

typedef struct node{
 struct node *prev;
 int info;
 struct node *next;
} NODE;

void insertAtFirst(NODE **, int);
int deleteAtLast(NODE **);
void traverse(NODE **);

int main(){
 NODE *start = NULL;
 deleteAtLast(&start);
 insertAtFirst(&start, 3);
 traverse(&start);
 deleteAtLast(&start);
 insertAtFirst(&start, 24);
 insertAtFirst(&start, 4);
 traverse(&start);
 deleteAtLast(&start);
 traverse(&start);
 return 0;
}

void insertAtFirst(NODE **start, int info){
 NODE *ptr = (NODE*) malloc(sizeof(NODE));
 ptr->info = info;
 if(*start == NULL){
  *start = ptr;
  ptr->next = ptr;
  ptr->prev = ptr;
 }
 else{
  ptr->next = *start;
  ptr->prev = (*start)->prev;
  (*start)->prev->next = ptr;
  (*start)->prev = ptr;
  *start = ptr;
 }
}

int deleteAtLast(NODE **start){
 NODE *temp = *start;
 int info = -1;
 if(*start == NULL){
  printf("\nError: The list has no nodes\n");
 }
 else{
  if((*start)->next == *start){
   *start = NULL;
  }
  else{
   temp = (*start)->prev;
   (*start)->prev->prev->next = *start;
   (*start)->prev = (*start)->prev->prev;
  }
  info = temp->info;
  free(temp);
 }
 return info;
}

void traverse(NODE **start){
 NODE *ptr = *start;
 if(ptr == NULL){
  printf("\nEmpty list\n");
  return;
 }
 while( ptr->next != *start ){
  printf("%d  ",ptr->info);
  ptr = ptr->next;
 }
 printf("%d\n",ptr->info);
}
Output:
Error: The list has no nodes
3
4  24
4
 

Related topics:

Labels:

Comments

Post a Comment