Delete all Occurrences of a Key in a Doubly Linked List Python Solution

In this problem, we will be given a doubly linked list and a key x. Our task is to delete all the occurrences of the key x from the given doubly linked list.

Let us see an example to understand the problem

Example:

Input: 2 ó 3 ó 6 ó 3 ó 5 ó 3 ó 7 ó 1 ó 8 ó 3, x = 3

Output: 2 ó 6 ó 5 ó 7 ó 1 ó 8

We have deleted all the nodes with value 3

Approach - 1

The idea of this approach is simple. We will loop over the given doubly linked list. For each node, we will check if the value of this node is the same as x. If the value is the same, then we will access the previous node using the prev pointer and point it to the next node of the current node. Then, we will point the previous pointer of the next node to the previous node of the current node. In this way, the current node whose value is the same as x will be deleted.

Code

Output:

The original Doubly linked list:
4 8 1 7 3 5 3 6 3 2 None
The modified Doubly linked list after the deletion of the key 3 :
4 8 1 7 5 6 2 None

Time Complexity: We used a linear loop to traverse the linked list. Therefore, the time complexity of this approach is linear, i.e., O(n).

Auxiliary Space: We have not used any extra space for this program; therefore, the space complexity is constant, i.e., O(1).