Delete a Node at End of Doubly Circular Linked List

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

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.
Single Node Case:
- If the list has only one node (i.e., head->next is head), delete head, set it to NULL, and exit.
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.
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.

What did you think?