Deletion in Doubly Linked List (DLL)

Welcome back, coding enthusiasts! Today, we're going to delve into one of the essential data structures - Doubly Linked List (DLL), and specifically focus on deletion in DLL. Let's get started! 🎯

Understanding Doubly Linked List (DLL)

Before we dive into deletion, let's quickly recap what a Doubly Linked List is. Unlike a singly linked list, each node in a DLL has a reference to both the next and previous nodes. This allows us to traverse the list in both directions - forward and backward.

markdown

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

📝 Note: Here, data is the value stored in the node, next is a pointer to the next node, and prev is a pointer to the previous node.

Deleting a Node in DLL

Now that we understand DLL, let's learn how to delete a node from it. We'll cover three scenarios: deleting a node at the beginning, deleting a node in the middle, and deleting a node at the end.

Deleting a Node at the Beginning

To delete a node at the beginning (head), we need to update the next pointer of the second node to point to the node that was originally the third node (if any). After that, we can free the memory occupied by the deleted node.

markdown

void deleteAtBeginning(Node* head) {
    if(head != NULL) {
        Node* temp = head;
        head = head->next;
        head->prev = NULL;
        free(temp);
    }
}

📝 Note: In the above code, we first save a copy of the head node, then update the head to point to the second node. Finally, we free the memory of the deleted node.

Deleting a Node in the Middle

To delete a node in the middle, we need to update the prev and next pointers of the nodes surrounding the one we want to delete.

markdown

void deleteFromMiddle(Node* prev, Node* current) {
    if(prev != NULL && current != NULL) {
        prev->next = current->next;
        if(current->next != NULL)
            current->next->prev = prev;
        free(current);
    }
}

📝 Note: Here, we pass the previous and current nodes as arguments to the function, and update the pointers accordingly.

Deleting a Node at the End

To delete a node at the end (tail), we need to update the prev pointer of the second-to-last node to point to the node before that one. After that, we can free the memory occupied by the deleted node.

markdown

void deleteAtEnd(Node* tail) {
    if(tail != NULL) {
        Node* temp = tail;
        tail = tail->prev;
        tail->next = NULL;
        free(temp);
    }
}

📝 Note: In the above code, we first save a copy of the tail node, then update the tail to point to the second-to-last node. Finally, we free the memory of the deleted node.

That's it for today's lesson! Deletion in DLL might seem complex at first, but with practice, you'll find it straightforward. Keep coding and happy learning! 💡

Stay tuned for more exciting lessons on Data Structures and Algorithms. Until then, keep practicing! ✅