Delete all occurrences of a given key in a doubly linked list

The problem involves deleting all occurrences of a given key in a doubly linked list. A doubly linked list is a data structure where each node contains a data element and two pointers, one pointing to the next node and another pointing to the previous node. Your task is to remove all nodes containing a specific value (key) from this doubly linked list.

Problem Statement

Given a doubly linked list and a key, you need to delete all occurrences of the key from the list.

Example

Consider the following example:

Initial doubly linked list:

9 <-> 2 <-> 3 <-> 9 <-> 5 <-> 6 <-> 9

Key to be deleted: 9

After deleting nodes with key 9:

2 <-> 3 <-> 5 <-> 6

Idea to Solve

To solve this problem, you can iterate through the doubly linked list and whenever you encounter a node with the given key, you remove it by updating the prev and next pointers of the adjacent nodes. If the node to be deleted is the head or tail node, you need to update the head or tail pointers accordingly.

Pseudocode

deleteOccurrences(key):
    if head is null:
        print "Empty linked list"
    else:
        found = false
        temp = head
        while temp is not null:
            if temp.data == key:
                found = true
                if temp == head:
                    head = head.next
                    if head is null:
                        tail = null
                    else:
                        head.prev = null
                else:
                    temp.prev.next = temp.next
                    if temp.next is null:
                        tail = temp.prev
                    else:
                        temp.next.prev = temp.prev
            temp = temp.next
        if not found:
            print "Key not found"

Algorithm Explanation

1. Check if the head is null. If yes, print "Empty linked list".
2. If the head is not null, initialize found as false and create a temporary pointer temp pointing to head.
3. Iterate through the doubly linked list using the temp pointer until it becomes null.
4. Inside the loop, check if the data of the current node (temp.data) is equal to the given key. If yes:
   • Set found to true.
   • Check if the current node is the head node. If yes, update the head pointer to the next node. If the head becomes null, update the tail pointer as well. Otherwise, update the prev pointer of the new head to null.
   • If the current node is not the head, update the next pointer of the previous node to skip the current node. If the current node is also the tail, update the tail pointer. Otherwise, update the prev pointer of the next node to skip the current node.
5. Move the temp pointer to the next node.
6. After the loop, if found is still false, print "Key not found".

Code Solution

1) Remove all node of given key in doubly linked list in java 2) Remove all node of given key in doubly linked list c++ 3) Remove all node of given key in doubly linked list in c 4) Remove all node of given key in doubly linked list in golang 5) Remove all node of given key in doubly linked list in c# 6) Remove all node of given key in doubly linked list in vb.net 7) Remove all node of given key in doubly linked list in php 8) Remove all node of given key in doubly linked list in node js 9) Remove all node of given key in doubly linked list in typescript 10) Remove all node of given key in doubly linked list in python 11) Remove all node of given key in doubly linked list in ruby 12) Remove all node of given key in doubly linked list in scala 13) Remove all node of given key in doubly linked list in swift 14) Remove all node of given key in doubly linked list in kotlin

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the doubly linked list. This is because in the worst case, you need to traverse the entire list once to delete all occurrences of the given key. The operations performed inside the loop are constant time operations, so they don't affect the overall time complexity.