Delete a Node at End of Doubly Circular Linked List

Deleting a node at the end of a Doubly Circular Linked List (DCLL) means removing the last node in the list while keeping the circular and doubly-linked structure intact. In a DCLL, every node has two pointers: next pointing to the next node and prev pointing to the previous node. The last node’s next points to the head, and the head’s prev points to the last node. To delete the last node, we first identify it using the prev pointer of the head (or by traversing the list).

Then, we update the prev pointer of the head to point to the second-last node and update the next pointer of the second-last node to point to the head. Finally, we free the memory of the last node. After this operation, the list remains circular and doubly linked, but its size is reduced by one. This operation is useful for managing data where elements are frequently added or removed from the end.

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.

Time & Space Complexity

Time Complexity

Space Complexity