Delete a Node at End of Doubly Circular Linked List

by

In this tutorial we will learn writing Algorithm and Program to delete a node from beginning on Doubly Circular Linked List.

Algorithm to Delete a Node at the End of Doubly Circular Linked List

  1. Check if the List is Empty:
    • If the head pointer is NULL, it means the list is empty. Print a message indicating that deletion is not possible and exit the function.
  2. Single Node Case:
    • If the list has only one node (i.e., head->next is head), delete head, set it to NULL, and exit.
  3. Multiple Nodes Case:
    • If the list contains more than one node:
      • Find the second-to-last node (the node whose next pointer points to head).
      • Update its next pointer to head, effectively removing the last node from the list.
      • Update the prev pointer of head to point to this new last node.
      • Delete the original last node.
  4. Completion:
    • The last node is removed from the list, and the list still maintains its circular structure.

Example

  • Given List: A Doubly Circular Linked List with elements: 10, 20, 30, 40.
  • Task: Delete the last node (which contains the element 40).

Initial State of the List

  • List: head -> [10] <-> [20] <-> [30] <-> [40] <-> back to [10]

Step 1: Check if the List is Empty

  • Check: Since head is not NULL, the list is not empty.

Step 2: Single Node Case

  • Determine: The list has more than one node, so this step is not applicable.

Step 3: Multiple Nodes Case

  • Find the Second-to-Last Node
    • Start from head (node [10]).
    • Move to the next nodes until reaching the node [30], which is the second-to-last node as its next is [40] (the last node).
  • Update Pointers
    • Set the next of [30] to head ([10]).
    • Update the prev pointer of head ([10]) to point to [30].
  • Delete the Last Node
    • Remove node [40] and free its memory.

Completion

  • Final State of the List: head -> [10] <-> [20] <-> [30] <-> back to [10]
  • The node containing 40 is successfully removed.
  • The list still maintains its circular structure.

Conclusion

  • Outcome: The last node ([40]) has been deleted from the list.

C Program to delete from End of Doubly Circular Linked List 

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

struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
}; 

typedef struct Node Node;

// Create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode;
    newNode->prev = newNode;
    return newNode;
}

// Insert at the End of the Doubly Circular Linked List
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* last = (*head)->prev;
        newNode->next = *head;
        newNode->prev = last;
        last->next = (*head)->prev = newNode;
    }
}

// Delete a node from End
void deleteFromEnd(Node** head) {
    if (*head == NULL) {
        printf("List is empty. No node to delete.\n");
        return;
    }
    Node* toDelete = (*head)->prev;
    if (toDelete == *head) {
        *head = NULL;
    } else {
        Node* newLast = toDelete->prev;
        newLast->next = *head;
        (*head)->prev = newLast;
    }
    free(toDelete);
    printf("Node deleted from the end.\n");
}

// Print the Doubly Circular Linked List
void printDoublyCircularLinkedList(Node* head) {
    if (!head) {
        printf("Doubly Circular Linked List is empty.\n");
        return;
    }
    Node* temp = head;
    printf("Doubly Circular Linked List: ");
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

int main() {
    Node* head = NULL;
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    printf("Doubly Circular Linked List Before Deletion:\n");
    printDoublyCircularLinkedList(head);

    deleteFromEnd(&head);
    printf("Doubly Circular Linked List After Deletion:\n");
    printDoublyCircularLinkedList(head);

    return 0;
}

Output

Doubly Circular Linked List Before Deletion:
Doubly Circular Linked List: 10 20 30 40 50 
Node deleted from the end.
Doubly Circular Linked List After Deletion:
Doubly Circular Linked List: 10 20 30 40

Program Explanation

Node Structure Definition

struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
}; 

typedef struct Node Node;
  • Defines a Node structure for each element in the DCLL.
  • Contains:
    • int data: The integer value stored in the node.
    • struct Node* next: A pointer to the next node in the list.
    • struct Node* prev: A pointer to the previous node in the list.
  • The typedef keyword in C is used to create an alias for a data type. The statement typedef struct Node Node; creates an alias Node for struct Node.

Function: createNode

// Create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode;
    newNode->prev = newNode;
    return newNode;
}
  • Purpose: Creates a new node with the specified data.
  • Process:
    • Allocates memory for a new Node.
    • Initializes the node’s data with the given value.
    • Points next and prev to the node itself (crucial for a circular list).

Function: insertAtEnd

// Insert at the End of the Doubly Circular Linked List
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* last = (*head)->prev;
        newNode->next = *head;
        newNode->prev = last;
        last->next = (*head)->prev = newNode;
    }
}
  • Purpose: Inserts a new node at the end of the DCLL.
  • Process:
    • If the list is empty (*head == NULL), sets the new node as head.
    • If not, finds the current last node ((*head)->prev).
    • Inserts the new node between the last node and the head.
    • Adjusts next and prev pointers of relevant nodes to maintain the circular structure.

Function: deleteFromEnd

// Delete a node from End
void deleteFromEnd(Node** head) {
    if (*head == NULL) {
        printf("List is empty. No node to delete.\n");
        return;
    }
    Node* toDelete = (*head)->prev;
    if (toDelete == *head) {
        *head = NULL;
    } else {
        Node* newLast = toDelete->prev;
        newLast->next = *head;
        (*head)->prev = newLast;
    }
    free(toDelete);
    printf("Node deleted from the end.\n");
}
  • Purpose: Deletes the last node from the DCLL.
  • Process:
    • Checks if the list is empty. If so, prints a message and exits.
    • Identifies the node to delete ((*head)->prev).
    • If this node is the only node in the list, sets head to NULL.
    • If there are multiple nodes, adjusts the next of the second-to-last node and the prev of head to bypass the last node.
    • Frees the memory allocated to the last node.

Function: printDoublyCircularLinkedList

// Print the Doubly Circular Linked List
void printDoublyCircularLinkedList(Node* head) {
    if (!head) {
        printf("Doubly Circular Linked List is empty.\n");
        return;
    }
    Node* temp = head;
    printf("Doubly Circular Linked List: ");
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}
  • Purpose: Prints the contents of the DCLL.
  • Process:
    • Checks if the list is empty. If so, prints a message and exits.
    • Traverses the list from head, printing the data of each node, until it reaches head again.

Main Function

int main() {
    Node* head = NULL;
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    printf("Doubly Circular Linked List Before Deletion:\n");
    printDoublyCircularLinkedList(head);

    deleteFromEnd(&head);
    printf("Doubly Circular Linked List After Deletion:\n");
    printDoublyCircularLinkedList(head);

    return 0;
}
  • Functionality:
    • Initializes an empty DCLL (head = NULL).
    • Inserts several nodes at the end of the list (with values 10, 20, 30, 40, 50).
    • Prints the list before deletion.
    • Deletes the last node.
    • Prints the list after deletion to show the updated list.

Output of the Program

  • Initially, the program will display the DCLL with nodes containing 10, 20, 30, 40, 50.
  • After executing deleteFromEnd, the last node (containing 50) will be removed. The program then displays the updated list: 10, 20, 30, 40.

Hope this article helped you in understanding the writing Program and Algorithm to perform delete operation from end on Doubly Circular Linked List.