Deleting All Occurrences of a Key in a Doubly Linked List
Deleting All Occurrences of a Key in a Doubly Linked List (DLL)
Introduction
A Doubly Linked List (DLL) is a data structure consisting of nodes, where each node contains three components:
- A data field
- A pointer to the next node
- A pointer to the previous node.
This structure allows traversal in both directions and efficient insertion and deletion operations.
Video Explanation
Problem Statement
Given a DLL and a key, the task is to delete all nodes that contain the specified key.
Example
Input:
DLL: 10 <-> 20 <-> 30 <-> 20 <-> 40 Key: 20
Output:
DLL: 10 <-> 30 <-> 40
Approach
- Initialize Pointers: Start with a pointer at the head of the list.
- Traverse the DLL: Loop through the list and check each node's data against the key.
- Delete Nodes:
- If a node's data matches the key:
- Adjust the pointers of the previous and next nodes.
- If the node is the head, update the head pointer.
- Move to the next node after deletion.
- If a node's data matches the key:
- Continue Traversal: Keep traversing until the end of the list.
Implementation
Solutions
- C++
- Java
- Python
- JavaScript
#include <iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int data) {
this->data = data;
this->next = nullptr;
this->prev = nullptr;
}
};
class DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() {
head = nullptr;
}
// Method to append a node at the end of the list
void append(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
return;
}
Node* last = head;
while (last->next != nullptr) {
last = last->next;
}
last->next = newNode;
newNode->prev = last;
}
// Method to delete all occurrences of a key
void deleteAllOccurrences(int key) {
Node* current = head;
while (current != nullptr) {
if (current->data == key) {
// Node to be deleted
if (current->prev != nullptr) {
current->prev->next = current->next;
}
if (current->next != nullptr) {
current->next->prev = current->prev;
}
if (current == head) { // Move hea
class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
Node head;
// Method to append a node at the end of the list
public void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node last = head;
while (last.next != null) {
last = last.next;
}
last.next = newNode;
newNode.prev = last;
}
// Method to delete all occurrences of a key
public void deleteAllOccurrences(int key) {
Node current = head;
while (current != null) {
if (current.data == key) {
// Node to be deleted
if (current.prev != null) {
current.prev.next = current.next;
}
if (current.next != null) {
current.next.prev = current.prev;
}
if (current == head) { // Move head if needed
head = current.next;
}
// Move to next node
Node temp = current;
current = current.next;
temp = null; // Free the deleted node
} else {
current = current.next;
}
}
}
// Method to display the list
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " <-> ");
current = current.next;
}
System.out.println("null");
}
}
// Example Usage
public class Main {
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
dll.append(10);
dll.append(20);
dll.append(30);
dll.append(20);
dll.append(40);
System.out.println("Original DLL:");
dll.display();
dll.deleteAllOccurrences(20);
System.out.println("DLL after deleting 20:");
dll.display();
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
new_node.prev = last
def delete_all_occurrences(self, key):
current = self.head
while current:
if current.data == key:
# Node to be deleted
if current.prev:
current.prev.next = current.next
if current.next:
current.next.prev = current.prev
if current == self.head: # Move head if needed
self.head = current.next
# Move to next node
temp = current
current = current.next
del temp # Free the deleted node
else:
current = current.next
def display(self):
current = self.head
while current:
print(current.data, end=' <-> ')
current = current.next
print('None')
# Example Usage
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)
dll.append(20)
dll.append(40)
print("Original DLL:")
dll.display()
dll.delete_all_occurrences(20)
print("DLL after deleting 20:")
dll.display()
var deleteAllOccurrences = function(head, x) {
let curr = head;
while (curr !== null) {
if (curr.val === x) {
if (curr === head) {
head = head.next;
if (head !== null) head.prev = null;
} else {
if (curr.next !== null) curr.next.prev = curr.prev;
if (curr.prev !== null) curr.prev.next = curr.next;
}
}
curr = curr.next;
}
return head;
};
Track Your Progress
Done with this topic? Mark it as complete to track your progress.
Related Practice Problems
Handpicked problems sharing similar algorithmic topic tags
Easy
#Linked List
Finding loop in a linked list.
This document includes solution to problem finding loop in a linked list along with approach and implementation.
Solve Problem→
Easy
#Linked List
Intersection of Two Linked Lists
Solving the Intersection of Two Linked Lists problem using an optimal two-pointer approach.
Solve Problem→
Easy
#Linked List
Linked List Cycle
Solving the Linked List Cycle problem using Floyd's Cycle-Finding Algorithm.
Solve Problem→
💬 Discuss this page
Have a question or spot something confusing in "Deleting All Occurrences of a Key in a Doubly Linked List"? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.