Understanding Doubly Linked List

A doubly linked list is a type of linked list in which each node contains three parts:

1. Data: The value stored in the node.
2. Next Pointer: A pointer to the next node in the list.
3. Previous Pointer: A pointer to the previous node in the list.

This structure allows traversal of the list in both directions, making doubly linked lists more flexible than singly linked lists, which can only be traversed in one direction.

This article contains deletion of the node of doubly-linked list at various position:

1. Deletion of head node
2. Deletion of tail node
3. Deletion of node from any position

1️⃣ Deletion of Head Node

Problem Statement

You are given the head of the doubly linked list, remove the node at the head of the linked list, and return the head of the modified list.

Examples

Example 1:

Input: head -> 1 <-> 2 <-> 3
Output: head -> 2 <-> 3

Explanation: The node with value 1 was removed.

Example 2:

Input: head -> 7
Output: head

Explanation: The node has null value after the removal.

Intuition:

In a doubly linked list, each node has a reference to both its next and previous nodes. To delete the head node, we need to:

1. Update the head pointer to the next node.
2. Adjust the prev pointer of the new head node to be nullptr (since it will be the new head).
3. Free the memory occupied by the old head node.

By taking advantage of the doubly linked list's bidirectional pointers, this operation is straightforward and efficient.

Approach:

1. Check if the list is empty: If the head is nullptr, there's nothing to delete.
2. Move the head pointer: Set the head to point to the next node in the list.
3. Adjust the new head's previous pointer: If the new head is not nullptr, set its prev pointer to nullptr.
4. Delete the old head node: Free the memory associated with the old head node to prevent memory leaks.

Code:

#include <iostream>

// Definition for a Node in a doubly linked list
struct Node {
    int data;
    Node* prev;
    Node* next;

    // Constructor to initialize a new node
    Node(int value) : data(value), prev(nullptr), next(nullptr) {}
};

// Function to delete the head node in a doubly linked list
void deleteHead(Node*& head) {
    // If the list is empty, nothing to delete
    if (head == nullptr) {
        std::cout << "List is empty. Nothing to delete." << std::endl;
        return;
    }

    Node* temp = head;    // Store the current head node
    head = head->next;    // Move the head pointer to the next node

    if (head != nullptr) {
        head->prev = nullptr;  // Set the previous pointer of the new head to nullptr
    }

    delete temp;  // Delete the old head node
}

// Function to print the list
void printList(Node* node) {
    while (node != nullptr) {
        std::cout << node->data << " ";
        node = node->next;
    }
    std::cout << std::endl;
}

int main() {
    // Create a doubly linked list: 10 <-> 20 <-> 30
    Node* head = new Node(10);
    head->next = new Node(20);
    head->next->prev = head;
    head->next->next = new Node(30);
    head->next->next->prev = head->next;

    std::cout << "Original List: ";
    printList(head);

    // Delete the head node
    deleteHead(head);

    std::cout << "After deleting head: ";
    printList(head);

    // Clean up remaining nodes
    deleteHead(head); // Deletes 20
    deleteHead(head); // Deletes 30
    deleteHead(head); // Tries to delete from an empty list

    return 0;
}

OR:

#include <bits/stdc++.h>
using namespace std;

// Definition of doubly linked list
struct ListNode
{
    int val;
    ListNode *next;
    ListNode *prev;
    ListNode()
    {
        val = 0;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1, ListNode *next1, ListNode *prev1)
    {
        val = data1;
        next = next1;
        prev = prev1;
    }
};

// Solution class
class Solution {
public:
    // Function to delete the head of the doubly linked list
    ListNode* deleteHead(ListNode* head) {
        if (head == nullptr || head->next == nullptr) 
            return nullptr; // Return NULL 

        // Store current head as 'prev'
        ListNode* prev = head;      
        // Move 'head' to next node
        head = head->next;    

        // Set 'prev' pointer 
        head->prev = nullptr;   

        // Set 'next' pointer 
        prev->next = nullptr;  

        // Return new head
        return head;          
    }
};

// Helper Function to convert an array to a doubly linked list
ListNode* arrayToLinkedList(vector<int> &nums) {
    // If array is empty, return nullptr
    if (nums.empty()) return nullptr; 

    // Create head node with first element of the array
    ListNode* head = new ListNode(nums[0]); 
    // Initialize 'prev' to the head node
    ListNode* prev = head;             

    for (int i=1; i < nums.size(); i++) {
        // Create a new node 
        ListNode* temp = new ListNode(nums[i], nullptr, prev);
        // Update 'next' pointer
        prev->next = temp;    
        // Move 'prev' to newly created node
        prev = temp;         
    }
    
    // Return head
    return head;  
}

// Helper Function to print the linked list
void printLL(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    
    // Creating the doubly linked list from given array
    ListNode* head = arrayToLinkedList(nums);
    
    // Print the Original list 
    cout << "Original List: ";
    printLL(head);
    
    // Create an instance of Solution class 
    Solution sol;
    
    // Function call to delete the head of the doubly linked list
    head = sol.deleteHead(head);
    
    // Print the Modified list
    cout << "Modified list: ";
    printLL(head);

    return 0;
}

Complexity Analysis:

• Time Complexity: The time complexity of deleting the head node is O(1) because:
  • We only update a few pointers (constant time operations).
  • No traversal of the list is needed.
• Space Complexity: The space complexity is O(1), assuming the list itself is already allocated in memory. We are not using any additional data structures or extra space except for a few pointers.

2️⃣ Deletion at the Tail

Problem Statement:

Given the head of a doubly linked list, remove the node at the tail of the linked list and return the head of the modified list.

The tail is the last node of the linked list.

Examples:

Example 1:

Input: head -> 1 <-> 2 <-> 3
Output: head -> 1 <-> 2

Explanation: The node with value 3 was removed.

Example 2:

Input: head -> 7
Output: head

Explanation: Note that the head null value after removal.

Example 3:

Input: head -> 2 <-> 4
Output: head -> 2

Explanation: The last node 4 was removed.

Intuition:

In a doubly linked list, each node contains pointers to both the next and previous nodes. This bidirectional reference allows easy access to the last node (tail) of the list. To delete the tail node, we need to update the next pointer of the node preceding the tail to nullptr and then free the memory occupied by the old tail node.

Approach:

1. Check if the list is empty: If the head is nullptr, there is nothing to delete.
2. Find the tail node: Traverse the list to the last node (tail).
3. Update the second-to-last node's next pointer: Set the next pointer of the node before the tail to nullptr.
4. Delete the tail node: Free the memory occupied by the tail node.

Code:

#include <iostream>

// Definition for a Node in a doubly linked list
struct Node {
    int data;
    Node* prev;
    Node* next;

    // Constructor to initialize a new node
    Node(int value) : data(value), prev(nullptr), next(nullptr) {}
};

// Function to delete the tail node in a doubly linked list
void deleteTail(Node*& head) {
    if (head == nullptr) {
        std::cout << "List is empty. Nothing to delete." << std::endl;
        return;
    }

    // If there is only one node in the list
    if (head->next == nullptr) {
        delete head;
        head = nullptr;
        return;
    }

    // Traverse to the last node (tail)
    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }

    // Update the next pointer of the second-to-last node
    temp->prev->next = nullptr;
    
    // Delete the tail node
    delete temp;
}

// Function to print the list
void printList(Node* node) {
    while (node != nullptr) {
        std::cout << node->data << " ";
        node = node->next;
    }
    std::cout << std::endl;
}

int main() {
    // Create a doubly linked list: 10 <-> 20 <-> 30
    Node* head = new Node(10);
    head->next = new Node(20);
    head->next->prev = head;
    head->next->next = new Node(30);
    head->next->next->prev = head->next;

    std::cout << "Original List: ";
    printList(head);

    // Delete the tail node
    deleteTail(head);

    std::cout << "After deleting tail: ";
    printList(head);

    // Clean up remaining nodes
    deleteTail(head); // Deletes 20
    deleteTail(head); // Deletes 10
    deleteTail(head); // Tries to delete from an empty list

    return 0;
}

Complexity Analysis:

• Time Complexity: The time complexity for deleting the tail node is O(n), where n is the number of nodes in the list. This is because we need to traverse the list to find the tail node.
• Space Complexity: The space complexity is O(1), as we only use a constant amount of extra space (a few pointers).

3️⃣ Delete from Any Position

Problem Statement

Given the head of a doubly linked list and an integer k, remove the node at the kth position of the linked list and return the head of the modified list.

Examples:

Example 1:

Input: head -> 2 <-> 5 <-> 7 <-> 9, k = 2
Output: head -> 2 <-> 7 <-> 9

Explanation: The node with value 5 was removed.

Example 2:

Input: head -> 2 <-> 5 <-> 7, k = 1
Output: head -> 5 <-> 7

Explanation: The node with value 2 was removed.

Intuition:

In a doubly linked list, each node has two pointers: one pointing to the next node (next) and another pointing to the previous node (prev). This bidirectional connection allows us to efficiently traverse the list in both directions and perform insertions or deletions at any position with ease.

To delete a node at any position:

1. Update the pointers of the adjacent nodes: Set the next pointer of the previous node to point to the node after the one to be deleted. Similarly, set the prev pointer of the next node to point to the node before the one to be deleted.
2. Free the memory of the node to be deleted: This prevents memory leaks.

Approach:

1. Check if the list is empty: If the head is nullptr, there is nothing to delete.
2. Traverse to the desired node: Iterate through the list until you reach the node to be deleted.
3. Update pointers:
   • If the node to delete is the head, adjust the head pointer.
   • If the node to delete is in the middle, adjust both the previous and next pointers of the adjacent nodes.
   • If the node to delete is the tail, adjust the previous pointer of the tail node.
4. Delete the node: Free the memory occupied by the node.

Code:

#include <iostream>

// Definition for a Node in a doubly linked list
struct Node {
    int data;
    Node* prev;
    Node* next;

    // Constructor to initialize a new node
    Node(int value) : data(value), prev(nullptr), next(nullptr) {}
};

// Function to delete a node from any position in a doubly linked list
void deleteNode(Node*& head, int position) {
    // If the list is empty
    if (head == nullptr) {
        std::cout << "List is empty. Nothing to delete." << std::endl;
        return;
    }

    Node* temp = head;

    // If the node to be deleted is the head node
    if (position == 1) {
        head = temp->next;  // Move the head to the next node
        if (head != nullptr) {
            head->prev = nullptr;  // Set the new head's prev to nullptr
        }
        delete temp;
        return;
    }

    // Traverse to the node at the specified position
    for (int i = 1; temp != nullptr && i < position; ++i) {
        temp = temp->next;
    }

    // If the position is greater than the number of nodes
    if (temp == nullptr) {
        std::cout << "Position is greater than the number of nodes." << std::endl;
        return;
    }

    // If the node to be deleted is the tail node
    if (temp->next == nullptr) {
        temp->prev->next = nullptr;
    } else {  // Node is in the middle
        temp->prev->next = temp->next;  // Update the next pointer of the previous node
        temp->next->prev = temp->prev;  // Update the prev pointer of the next node
    }

    // Delete the node
    delete temp;
}

// Function to print the list
void printList(Node* node) {
    while (node != nullptr) {
        std::cout << node->data << " ";
        node = node->next;
    }
    std::cout << std::endl;
}

int main() {
    // Create a doubly linked list: 10 <-> 20 <-> 30 <-> 40
    Node* head = new Node(10);
    head->next = new Node(20);
    head->next->prev = head;
    head->next->next = new Node(30);
    head->next->next->prev = head->next;
    head->next->next->next = new Node(40);
    head->next->next->next->prev = head->next->next;

    std::cout << "Original List: ";
    printList(head);

    // Delete the node at position 2 (node with value 20)
    deleteNode(head, 2);

    std::cout << "After deleting node at position 2: ";
    printList(head);

    // Delete the node at position 1 (node with value 10)
    deleteNode(head, 1);

    std::cout << "After deleting node at position 1: ";
    printList(head);

    // Delete the node at position 2 (node with value 40)
    deleteNode(head, 2);

    std::cout << "After deleting node at position 2: ";
    printList(head);

    // Try deleting from an empty list
    deleteNode(head, 1);

    return 0;
}

Complexity Analysis:

• Time Complexity: The time complexity for deleting a node from any position is O(n), where n is the number of nodes in the list. This is because we may need to traverse the list to find the node at the specified position.
• Space Complexity: The space complexity is O(1) since we are using a constant amount of extra space (a few pointers).