Delete node at given location in Doubly Circular Linked List

Deleting a node at a given location in a Doubly Circular Linked List (DCLL) involves removing a specific node based on its position while keeping the circular and doubly-linked structure intact. In a DCLL, each node has a next pointer to the following node and a prev pointer to the previous node, and the last node points back to the head. To delete a node at a given position, we first traverse the list to reach that position. Then, we adjust the next pointer of the previous node and the prev pointer of the next node to bypass the node being deleted. Finally, we free the memory of the deleted node. This operation is useful when you need precise control over which element to remove from the 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.

Time & Space Complexity

Time Complexity

Space Complexity