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

Last Updated on November 18, 2022 by Prepbytes

Removing occurrences in a linked list is quite different than removing occurrences through a is different. So, lets just look into the approach on how to delete all occurrences of a key in doubly linked list

Problem Statement on how to delete all occurrences of a key in doubly linked list

We will be given a doubly linked list, and a key X, and our task will be to delete all occurrences of a given key X from the linked list.

Problem Statement Understanding on how to delete all occurrences of a key in doubly linked list

Let’s try to understand the problem statement with the help of examples.

According to the problem statement, we will be given a doubly linked list and a key X. We have to delete all occurrences of a given key X from the linked list.

If the given doubly linked list is: head → 1 ←→ 2 ←→ 5 ←→ 2 ←→ 2 and key X = 2.

• As we can see that there are 3 occurrences of key X=2 in the given doubly linked list, so we will have to remove all these occurrences of X=3 from the linked list.
• Our output linked list after removing all the occurrences of 2 will be: head → 1 ←→ 5.
• Removing all the occurrences of a given key X from the linked list means removing all the nodes from the linked list with data equal to X.

If the given doubly linked list is: head → 2 ←→ 3 ←→ 3 ←→ 5 ←→ 3 ←→ 2 ←→ 5 ←→ 2 ←→ 2 and key X=3.

• Our doubly linked list after removal of all the occurrences of X=3 will be: head → 2 ←→ 5 ←→ 2 ←→ 5 ←→ 2 ←→ 2

Some more examples

Sample Input 1: head → 1 ←→ 3 ←→ 5 ←→ 3 ←→ 4, X = 3
Sample Output 1: head → 1 ←→ 5 ←→ 4.

Sample Input 2: head → 1 ←→ 3 ←→ 5 ←→ 7 ←→ 9 ←→ 1 ←→ 3 ←→ 5 ←→ 7, X = 5
Sample Output 2: head → 1 ←→ 3 ←→ 7 ←→ 9 ←→ 1 ←→ 3 ←→ 7.

Now I think from the above examples, the problem statement is clear. So let’s see how we will approach it. Any Ideas?

• If not, it’s okay. We will see in the next section thoroughly how we can approach this problem.

Let’s move to the next section.

Approach on how to delete all occurrences of a key in doubly linked list

Our approach will be simple:

• We will start traversing through the list and if the current node’s data is equal to X, we will join the current’s previous node to its next node and will delete the current node.

How to delete a node from a doubly linked list?

To see throughly how we can delete a node from a doubly linked list visit our article Delete a node in Doubly Linked List.

Algorithm on how to delete all occurrences of a key in doubly linked list

1. Initialize pointer variable curr with head node.
2. We will start traversing the linked list using pointer curr.
   • While traversing the list, if the current node’s data (curr->data) is not equal to X, we will move forward.
   • While traversing, if the current node’s data (curr->data) is equal to X, then we will delete this node and will join the immediate previous node of the current node to current’s next node.
3. Our linked list after the traversal will be the final resultant linked list free from nodes having data equal to X.

Dry Run on how to delete all occurrences of a key in doubly linked list

Code Implementation on how to delete all occurrences of a key in doubly linked list

#include 
using namespace std;

/* Node structure of doubly linked list */
struct Node {
	int data;
	struct Node* next;
	struct Node* prev;
};

/* Function to delete a node from Doubly Linked List.*/
void deleteNode(struct Node** head, struct Node* curr)
{
	if (*head == NULL || curr == NULL){
		return;
    }

	if (*head == curr){
        *head = curr->next;
    }

	if (curr->next != NULL){
        curr->next->prev = curr->prev;
    }

	if (curr->prev != NULL){
        curr->prev->next = curr->next;
    }

	free(curr);
}

/* Using this function we will delete all nodes from linked list having data equal to X */
void removeXoccurrences(struct Node** head, int X)
{
	if ((*head) == NULL)
		return;

	struct Node* curr = *head;
	struct Node* next;

	while (curr != NULL) {
		if (curr->data == X) {
			next = curr->next;
			deleteNode(head, curr);
			curr = next;
		}
		else
			curr = curr->next;
	}
}

/* Using this function we will insert a node at the beginning of List */
void push(struct Node** head, int data)
{
	struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
	new_node->data = data;
	new_node->prev = NULL;
	new_node->next = (*head);

	if ((*head) != NULL)
		(*head)->prev = new_node;

	(*head) = new_node;
}

/* Printing linked list */
void printList(struct Node* head)
{
	if (head == NULL)
		cout << "Doubly Linked list empty";

	while (head != NULL) {
		cout << head->data << " ";
		head = head->next;
	}
}

int main()
{
	struct Node* head = NULL;
	push(&head, 2);
	push(&head, 2);
	push(&head, 5);
	push(&head, 2);
	push(&head, 1);

	cout << "Original Doubly linked list before deletion: ";
	printList(head);

	int X = 2;
	removeXoccurrences(&head, X);

	cout << "\nDoubly linked list after deletion of all occurrences of "
		<< X << ": ";
	printList(head);

	return 0;
}

Output

Original Doubly linked list before deletion: 1 2 5 2 2
Doubly linked list after deletion of all occurrences of 2: 1 5

Time complexity: O(N), Since we have traversed through the list once.

Conclusion

So, In this blog, We have learned how to delete all occurrences of a key in doubly linked list. We tried to understand how an element actually can be fetched using a key parameter and how it can return the values.Interested in solving more linked list questions which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

FAQs

1. What is next in the doubly linked list?


In a doubly linked list each link consists of a link for the next link which is called Next.


2. What function is used to remove all instances of a linked list?


Using clear() method we can remove all elements from the linked list.


3. What is the time complexity of deletion in doubly linked list?


The time complexity of deletion in doubly linked list is O(n).