# 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:

``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):
else:
found = false
while temp is not null:
if temp.data == key:
found = true
tail = null
else:
else:
temp.prev.next = temp.next
if temp.next is null:
tail = temp.prev
else:
temp.next.prev = temp.prev
temp = temp.next

## 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".

## 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.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.