Delete in Doubly Linked List: Beginning, End and Given location

Deleting nodes in a Doubly Linked List involves removing elements from the list while properly updating the next and prev pointers of the surrounding nodes to maintain the structure. There are three common types of deletion: deletion at the beginning, deletion at the end, and deletion at a given position.

• Deletion at Beginning: Removes the first node of the list and updates the head pointer to the next node.
• Deletion at End: Removes the last node and updates the previous node’s next pointer to NULL.
• Deletion at Given Position: Removes a node from a specified position, adjusting the next and prev pointers of neighboring nodes to maintain the doubly linked structure.

This operation is important for managing memory and modifying the list dynamically in programs. It allows efficient removal of elements from anywhere in the list while keeping the doubly linked structure intact.

Algorithm for Deleting Nodes

1. Delete from the Beginning

• Check if List is Empty: Start by checking if the list is empty. If the head of the list is NULL, it means there are no nodes to delete. In this case, indicate that deletion is not possible.
• Single Node in the List: If the list contains only one node (i.e., head->next is NULL), delete this node and set head to NULL. This action leaves the list empty.
• Multiple Nodes in the List: If there are multiple nodes in the list, proceed to remove the first node. To do this:
  • Update the head of the list to point to the second node (head->next).
  • Set the prev pointer of the new head node to NULL to make it as a head node.
  • Delete the old head node.

2. Delete from the End

• Check if List is Empty: As with deletion from the beginning, start by checking if the list is empty. If it is, indicate that deletion is not possible.
• Single Node in the List: If the list has only one node, delete it and set head to NULL.
• Multiple Nodes in the List: If the list contains more than one node, you need to find the last node and remove it. To do this:
  • Traverse the list to reach the last node (where node->next is NULL).
  • Set the next pointer of the second-to-last node to NULL, It will remove the last node from the list.
  • Delete the last node.

3. Delete from a Specific Location

• Check for Empty List or Invalid Location: If the list is empty or the given location is less than 1, indicate that deletion is not possible.
• Deletion at the First Position: If the specified location is 1, use the procedure for deleting from the beginning.
• Deletion at a Specific Position: If the location is greater than 1, you must find the node at that position and remove it. To do this:
  • Traverse the list to reach the node at the given position.
  • Once you find the node, adjust the next pointer of its previous node to point to its next node. Similarly, adjust the prev pointer of its next node (if it exists) to point to its previous node.
  • These adjustments effectively remove the target node from the list.
  • Finally, delete the node from memory.

Delete Operation in Doubly Linked List using C

#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 = NULL;
    newNode->prev = NULL;
    return newNode;
}

// Insert at the end of Doubly linked list
void insertAtEnd(Node** head, int data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node *temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

// Delete from the Begining of Doubly linked list
void deleteFromBeginning(Node** head) {
    if (*head == NULL) {
        printf("Given List is empty. Can't Perform delete operation.\n");
        return;
    }
    Node *temp = *head;
    if (temp->next == NULL) {
        *head = NULL;
    } else {
        *head = temp->next;
        (*head)->prev = NULL;
    }
    free(temp);
}

// Delete from the End of Doubly linked list
void deleteFromEnd(Node** head) {
    if (*head == NULL) {
        printf("Given List is empty. Can't Perform delete operation.\n");
        return;
    }
    Node *temp = *head;
    if (temp->next == NULL) {
        *head = NULL;
        free(temp);
    } else {
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->prev->next = NULL;
        free(temp);
    }
}

// Delete from the given position of Doubly linked list
void deleteFromGivenPosition(Node** head, int position) {
    if (*head == NULL || position < 1) {
        printf("Invalid position or list is empty.\n");
        return;
    }
    if (position == 1) {
        deleteFromBeginning(head);
        return;
    }
    Node *temp = *head;
    for (int i = 1; temp != NULL && i < position; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("Position beyond list length.\n");
        return;
    }
    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }
    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    }
    free(temp);
}

// Traverse and print the Doubly Linked List
void traverseDoublyLinkedList(Node* head) {
    Node* temp = head;
    printf("Doubly Linked List After Delete Operations: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    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);
    deleteFromBeginning(&head);
    deleteFromEnd(&head);
    deleteFromGivenPosition(&head, 2);
        traverseDoublyLinkedList(head);

    return 0;
}

Output

Doubly Linked List After Delete Operations: 20 40 50 

Execution of the program

Initial State: Empty list (head = NULL).

After insertAtEnd(&head, 10):

List: 10 

After insertAtEnd(&head, 20):

List: 10 -> 20 

After insertAtEnd(&head, 30):

List: 10 -> 20 -> 30 

After insertAtEnd(&head, 40):

List: 10 -> 20 -> 30 -> 40 

After insertAtEnd(&head, 50):

List: 10 -> 20 -> 30 -> 40 -> 50 

After insertAtEnd(&head, 60):

List: 10 -> 20 -> 30 -> 40 -> 50 -> 60 

After deleteFromBeginning(&head):

List: 20 -> 30 -> 40 -> 50 -> 60 

After deleteFromEnd(&head):

List: 20 -> 30 -> 40 -> 50 

After deleteFromGivenPosition(&head, 2):

This deletes the node at position 2, which is ’30’ in this case.

List: 20 -> 40 -> 50 

After traverseDoublyLinkedList(head):

This traverses the list and prints its elements.

Expected Output: "Doubly Linked List After Delete Operations: 20 40 50".

Explanation of the above program

Defining the Node Structure

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

In the above code, a structure for a node in a doubly linked list is defined. Each node contains three parts: an integer data that stores the value of the node, a pointer next that points to the next node in the list, and a pointer prev that points to the previous node. This structure enables traversal in both directions—forward and backward—making it possible to efficiently insert or delete nodes at the beginning, at the end, or at any specific position in the doubly linked list.

Creating a New Node

Node *createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

In the above code, the createNode function is used to create a new node for the doubly linked list. It first allocates memory for the new node using malloc, sets the node’s data field with the given value, and initializes both the next and prev pointers to NULL. This ensures that the node is standalone and ready to be linked into the list at the beginning, end, or any specified position.

Inserting at the End of the List

void insertAtEnd(Node** head, int data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node *temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

In the above code, the insertAtEnd function inserts a new node at the end of the doubly linked list. It first creates a new node using createNode. If the list is empty (*head == NULL), the new node becomes the head of the list. Otherwise, it traverses the list to find the last node, then updates the next pointer of the last node to point to the new node and sets the prev pointer of the new node to the last node, maintaining the doubly linked structure.

Deleting from the Beginning of the List

void deleteFromBeginning(Node** head) {
    if (*head == NULL) {
        printf("Given List is empty. Can't Perform delete operation.\n");
        return;
    }
    Node *temp = *head;
    if (temp->next == NULL) {
        *head = NULL;
    } else {
        *head = temp->next;
        (*head)->prev = NULL;
    }
    free(temp);
}

In the above code, the deleteFromBeginning function removes a node from the beginning of the doubly linked list. It first checks if the list is empty; if so, it prints a message and exits. If the list has only one node, deleting it sets the head to NULL. Otherwise, it moves the head pointer to the second node and updates its prev pointer to NULL to maintain the doubly linked structure. Finally, it frees the memory of the removed node to avoid memory leaks.

Deleting from the End of the List

void deleteFromEnd(Node** head) {
    if (*head == NULL) {
        printf("Given List is empty. Can't Perform delete operation.\n");
        return;
    }
    Node *temp = *head;
    if (temp->next == NULL) {
        *head = NULL;
        free(temp);
    } else {
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->prev->next = NULL;
        free(temp);
    }
}

In the above code, the deleteFromEnd function removes a node from the end of the doubly linked list. It first checks if the list is empty; if it is, a message is printed and the function exits. If the list has only one node, it sets the head to NULL and frees that single node. Otherwise, it traverses the list to reach the last node, updates the next pointer of the second-to-last node to NULL to detach the last node, and then frees the memory of the removed node, ensuring the doubly linked structure remains intact.

Deleting from a Given Position

void deleteFromGivenPosition(Node** head, int position) {
    if (*head == NULL || position < 1) {
        printf("Invalid position or list is empty.\n");
        return;
    }
    if (position == 1) {
        deleteFromBeginning(head);
        return;
    }
    Node *temp = *head;
    for (int i = 1; temp != NULL && i < position; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("Position beyond list length.\n");
        return;
    }
    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }
    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    }
    free(temp);
}

In the above code, the deleteFromGivenPosition function removes a node from a specified position in the doubly linked list. It first checks if the list is empty or if the given position is invalid (less than 1). If the position is 1, it calls deleteFromBeginning to remove the first node. Otherwise, it traverses the list to reach the node at the given position. If the node exists, it updates the prev pointer of the next node and the next pointer of the previous node to bypass the node being deleted, maintaining the doubly linked structure. Finally, it frees the memory of the deleted node.

Traversing and Printing the List

void traverseDoublyLinkedList(Node* head) {
    Node* temp = head;
    printf("Doubly Linked List After Delete Operations: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

In the above code, the traverseDoublyLinkedList function is used to display the contents of the doubly linked list after delete operations. It starts from the head node and moves through the list by following the next pointers. For each node, it prints the data value. The traversal continues until the end of the list is reached (temp becomes NULL), ensuring all remaining nodes in the list are displayed in order.

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);
    deleteFromBeginning(&head);
    deleteFromEnd(&head);
    deleteFromGivenPosition(&head, 2);
    traverseDoublyLinkedList(head);

    return 0;
}

In the above code, the main function demonstrates deletion operations in a doubly linked list. First, it creates an empty list (head = NULL) and inserts six nodes with values 10, 20, 30, 40, 50, and 60 at the end using insertAtEnd. Then, it performs deletion operations: deleteFromBeginning removes the first node (10), deleteFromEnd removes the last node (60), and deleteFromGivenPosition removes the node at position 2 (originally 30). Finally, traverseDoublyLinkedList prints the remaining list to show the final state after these deletions. The output will display the nodes still in the list in order.

Time & Space Complexity

Time complexity

Operation	Time Complexity
insertAtEnd	O(n)
deleteFromBeginning	O(1)
deleteFromEnd	O(n)
deleteFromGivenPosition	O(n)
traverseDoublyLinkedList	O(n)

Space Complexity

Operation	Space Complexity
insertAtEnd	O(1)
deleteFromBeginning	O(1)
deleteFromEnd	O(1)
deleteFromGivenPosition	O(1)
traverseDoublyLinkedList	O(1)