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
 Check if the
head
is null. If yes, print "Empty linked list".  If the
head
is not null, initializefound
as false and create a temporary pointertemp
pointing tohead
.  Iterate through the doubly linked list using the
temp
pointer until it becomes null.  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 thehead
pointer to the next node. If thehead
becomes null, update thetail
pointer as well. Otherwise, update theprev
pointer of the newhead
to null.  If the current node is not the
head
, update thenext
pointer of the previous node to skip the current node. If the current node is also thetail
, update thetail
pointer. Otherwise, update theprev
pointer of the next node to skip the current node.
 Set
 Move the
temp
pointer to the next node.  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.
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.
New Comment