Delete Node at Beginning 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 Node from Beginning of Doubly Circular Linked List

  1. Check if the List is Empty:
    • If the head pointer is NULL, the list is empty. Indicate that deletion is not possible.
  2. Single Node Case:
    • If the list has only one node (i.e., head->next is head), delete head and set it to NULL.
  3. Multiple Nodes Case:
    • If the list contains more than one node:
      • Update the next pointer of the last node to point to the second node in the list (head->next).
      • Set the prev pointer of the second node to point to the last node.
      • Delete the first node (head).
      • Update head to the second node.
  4. The First Node is Deleted:
    • The list’s first node is removed, and the list still maintains its circular structure.

Example

  • Given List: Imagine we have a Doubly Circular Linked List with the elements: 10, 20, 30.
  • Task: We want to delete the first node (which currently has the data 10).

Steps

Initial State of the List

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

Step 1: Check if the List is Empty

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

Step 2: Single Node Case

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

Step 3: Multiple Nodes Case

  • Let’s delete the first node [10]:
    • Find Last Node: In this case, it’s the node [30].
    • Update Pointers:
      • Set [30]->next to [20] (which is head->next).
      • Set [20]->prev to [30].
    • Delete First Node:
      • Remove [10] and free its memory.
    • Update Head:
      • Set head to [20].

Final State of the List

  • List After Deletion: head -> [20] <-> [30] <-> back to [20]

The First Node is Deleted

  • The node containing 10 is successfully removed.
  • The list still maintains its circular structure.

Conclusion

  • Outcome: The first node ([10]) is deleted, and the new head of the list is the node [20].

C Program to Delete a Node from the Beginning of a 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 the Doubly Circular Linked List From Beginning
void deleteFromBeginningInDCLL(Node** head) {
    if (*head == NULL) {
        printf("List is empty. No node to delete.\n");
        return;
    }
    Node* toDelete = *head;
    if ((*head)->next == *head) {
        *head = NULL;
    } else {
        Node* last = (*head)->prev;
        *head = (*head)->next;
        (*head)->prev = last;
        last->next = *head;
    }
    free(toDelete);
    printf("Node deleted from the beginning.\n");
}

// Print the Doubly Circular Linked List
void printDoublyCircularLinkedList(Node* head) {
    if (!head) {
        printf("The 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);
    insertAtEnd(&head, 60);
    printf("Doubly Circular Linked List Before Deletion:\n");
    printDoublyCircularLinkedList(head);

    deleteFromBeginningInDCLL(&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 60 
Node deleted from the beginning.
Doubly Circular Linked List After Deletion:
Doubly Circular Linked List: 20 30 40 50 60

Explanation of the above program

Node Structure Definition

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

typedef struct Node Node;
  • Defines a structure Node for each element in the doubly circular linked list.
  • Each Node contains:
    • int data: The 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

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 given data.
  • Process:
    • Allocates memory for the new node.
    • Initializes the node’s data field.
    • Sets the next and prev pointers to point to the node itself. This is key for maintaining the circular nature of the list, particularly when the node is the only one in the list.

Function: insertAtEnd

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 doubly circular linked list.
  • Process:
    • If the list is empty (*head == NULL), the new node becomes the head.
    • If the list is not empty:
      • Identifies the last node (the one before the head).
      • Inserts the new node between the last node and the head, updating the next and prev pointers to maintain the circular structure.

Function: deleteFromBeginningInDCLL

void deleteFromBeginningInDCLL(Node** head) {
    if (*head == NULL) {
        printf("List is empty. No node to delete.\n");
        return;
    }
    Node* toDelete = *head;
    if ((*head)->next == *head) {
        *head = NULL;
    } else {
        Node* last = (*head)->prev;
        *head = (*head)->next;
        (*head)->prev = last;
        last->next = *head;
    }
    free(toDelete);
    printf("Node deleted from the beginning.\n");
}
  • Purpose: Deletes the first node of the doubly circular linked list.
  • Process:
    • If the list is empty, it indicates that there are no nodes to delete.
    • If the list has only one node (where head->next is head), deletes the head and sets it to NULL.
    • In case of multiple nodes, it updates the next pointer of the last node to the second node and the prev pointer of the second node to the last node, then deletes the first node (head).

Function: printDoublyCircularLinkedList

void printDoublyCircularLinkedList(Node* head) {
    if (!head) {
        printf("The 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 elements of the doubly circular linked list.
  • Process:
    • Starts from the head and traverses the list by following the next pointers, printing each node’s data until it cycles back to the head.

Main Function

int main() {
    Node* head = NULL;
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);

    printf("Before Deletion:\n");
    printList(head);

    deleteFromBeginning(&head);

    printf("After Deletion:\n");
    printList(head);

    return 0;
}
  • Purpose: Demonstrates the functionality of the list.
  • Process:
    • Initializes an empty list (head = NULL).
    • Inserts several nodes at the end of the list.
    • Prints the list before and after deleting the first node to show the effect of the deleteFromBeginningInDCLL function.

Hope above program and algorithm helped you to understand how to delete from beginning on Doubly Circular Linked List