Delete node at given location in 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 Specified Location in a Doubly Circular Linked List

  1. Check if the List is Empty:
    • If the head pointer is NULL, it means the list is empty. Indicate that deletion is not possible and exit.
  2. Single Node Case:
    • If the list has only one node (head->next is head), and the position is 1, delete head and set it to NULL.
  3. Multiple Nodes Case:
    • If the list contains more than one node, traverse to the specified location.
    • Keep track of the current position while traversing.
    • Upon reaching the desired node:
      • Update the next pointer of the previous node to point to the next node of the current node.
      • Update the prev pointer of the next node to point to the previous node of the current node.
    • Delete the node at the specified position.
  4. Position Not Found:
    • If the specified position is beyond the length of the list, indicate that the position is invalid.
  5. Completion:
    • The node at the specified position is removed, and the list maintains its circular structure.

Example

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

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

  • Traverse to the Specified Location (Position 3)
    • Start from head (node [10]).
    • Move to the next node (node [20]).
    • Reach the desired node (node [30]).
  • Update Pointers
    • The next of [20] should now point to [40].
    • The prev of [40] should now point to [20].
  • Delete the Node
    • Remove node [30] and free its memory.

Step 4: Position Not Found

  • Check: Position 3 is valid in this case, so no action is needed for this step.

Completion

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

Conclusion

  • Outcome: The node at position 3 (containing 30) has been deleted from the list.
  • List Integrity: The circular nature of the list is preserved, with node [20] now directly linked to node [40].

C Program to delete from Specific Location in 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 a specified location 
void deleteFromPositionInDCLL(Node** head, int position) {
    if (*head == NULL) {
        printf("List is empty.\n");
        return;
    }
    if (position == 1) {
        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);
    } else {
        Node* current = *head;
        for (int i = 1; i < position && current->next != *head; i++) {
            current = current->next;
        }
        if (current->next == *head && position != 1) {
            printf("Position is beyond list length.\n");
        } else {
            Node* prevNode = current->prev;
            Node* nextNode = current->next;
            prevNode->next = nextNode;
            nextNode->prev = prevNode;
            if (current == *head) {
                *head = nextNode;
            }
            free(current);
        }
    }
}

// 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);
    insertAtEnd(&head, 60);
    printf("Doubly Circular Linked List Before Deletion:\n");
    printDoublyCircularLinkedList(head);

    deleteFromPositionInDCLL(&head, 3);
    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 
Doubly Circular Linked List After Deletion:
Doubly Circular Linked List: 10 20 40 50 60

Explanations

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 DCLL.
  • Contains:
    • int data: The integer value stored in the node.
    • struct Node* next: A pointer to the next node.
    • struct Node* prev: A pointer to the previous node.
  • 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 a given data value.
  • Process:
    • Allocates memory for the node.
    • Sets the node’s data field.
    • Initializes next and prev to point to the node itself (important for the circular nature).

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 node at the end of the DCLL.
  • Process:
    • Checks if the list is empty (*head == NULL). If so, the new node becomes the head.
    • If not, locates the last node ((*head)->prev).
    • Inserts the new node between the last node and the head, adjusting the next and prev pointers to maintain the circular structure.

Function: deleteFromPositionInDCLL

// Delete a node from a specified location 
void deleteFromPositionInDCLL(Node** head, int position) {
    if (*head == NULL) {
        printf("List is empty.\n");
        return;
    }
    if (position == 1) {
        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);
    } else {
        Node* current = *head;
        for (int i = 1; i < position && current->next != *head; i++) {
            current = current->next;
        }
        if (current->next == *head && position != 1) {
            printf("Position is beyond list length.\n");
        } else {
            Node* prevNode = current->prev;
            Node* nextNode = current->next;
            prevNode->next = nextNode;
            nextNode->prev = prevNode;
            if (current == *head) {
                *head = nextNode;
            }
            free(current);
        }
    }
}
  • Purpose: Deletes a node from a specified position in the DCLL.
  • Process:
    • If the list is empty, indicates so and exits.
    • If the position is 1, handles the deletion of the head node. Special consideration is given if the list has only one node.
    • For other positions, traverses to the desired node, adjusts the next and prev pointers of adjacent nodes, and frees the memory of the node to be deleted.
    • If the position is beyond the length of the list, it prints an error message.

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, indicates this and exits.
    • If not, traverses the list from the head, 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);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    insertAtEnd(&head, 60);
    printf("Doubly Circular Linked List Before Deletion:\n");
    printDoublyCircularLinkedList(head);

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

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

Output of the Program

  • The first print statement will show the list with the nodes: 10, 20, 30, 40, 50, 60.
  • After deleting the node at position 3, the second print statement will show the updated list: 10, 20, 40, 50, 60.

Hope above program and algorithm helped you to understand how to delete from given location in Doubly Circular Linked List.