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

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

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

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

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

  • Initialize pointer variable curr with head node.
  • 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.
  • Our linked list after the traversal will be the final resultant linked list free from nodes having data equal to X.

Dry Run

Code Implementation

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

So, In this blog, We have learned how to delete all occurrences of a given key from a doubly linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Arrange consonants and vowels nodes in a linked list
Next post How to Get a Value from LinkedHashMap by Index in Java

Leave a Reply

Your email address will not be published. Required fields are marked *