# Doubly Linked List: Program to delete all occurrence of a node from DLL

Write a program to delete all occurences of a given node from the doubly linked list

A doubly linked list is a type of linked list that consist of nodes and bi-directional edges

- There are 2 edges/links between any two nodes - lets call them 'next' & 'prev'
- 'next' pointer points to next node and 'prev' pointer points to the previous node
- These bi-directional edges help us to navigate forward and backward in a linked list

##### Approach

- To remove all occurence of a node we traverse the doubly linked list
- Check each node against the given node
- If the data is matching we remove that node by changing the links of its previous and next node
- Then move to next node for comparison

##### Algorithm

- Create two pointer say current and previous
- Set current on head and previous as NULL
- While current is not NULL and current.data is equal to given node
- head = current.next
- current = head

- Now for traversing remaining linked list,while current is not NULL and current.data is not eqaul to given node
- Make previous = current and current = current.next
- After loop terminate,if current is NULL then return
- And make previous.next = current.next and current = previous.next to delete node

##### Complexity

Time Complexity : O(n) , where n is the size of doubly linked list

Space Complexity : O(1)

##### Java Code

```
import java.util.*;
class DeleteNodeDLL{
class Node {
int data;
Node next, prev;
Node(int d) {
this.data = d;
this.next = null;
this.prev = null;
}
}
Node head;
// creating a linked list using array
public void buildLinkedlist(int A[], int noOfNodes) {
Node temp, last;
temp = new Node(A[0]);
temp.next = temp.prev = null;
head = temp;
last = head;
for (int i = 1; i < noOfNodes; i++) {
temp = new Node(A[i]);
temp.next = null;
temp.prev = last;
last.next = temp;
last = temp;
}
}
// printing of linkedList
public void printLinkedlist() {
List allNodesList = new ArrayList<>();
Node temp = head;
while (temp != null) {
allNodesList.add(Integer.toString(temp.data));
temp = temp.next;
}
System.out.println(String.join(" <-> ", allNodesList));
}
public void deleteAllOccurances(int node) {
Node current = head, previous = null;
while (current != null && current.data == node) {
head = current.next;
current = head;
}
while (current != null) {
while (current != null && current.data != node) {
previous = current;
current = current.next;
}
if (current == null)
return;
previous.next = current.next;
current = previous.next;
}
}
public static void main(String[] args) {
int[] linkedlistElements = new int[] { 1, 2, 2, 3, 2, 4 };
int numberOfNodes = linkedlistElements.length;
// initializing object of linkedlist class
DeleteNodeDLL dll = new DeleteNodeDLL();
dll.buildLinkedlist(linkedlistElements, numberOfNodes);
System.out.println("Given Doubly Linked List ");
dll.printLinkedlist();
int toDelete = 2;
System.out.println("Doubly Linked List after deleting all occurances of node " +
toDelete);
dll.deleteAllOccurances(toDelete);
dll.printLinkedlist();
}
}
```

##### Output

Given Doubly Linked List

1 <-> 2 <-> 2 <-> 3 <-> 2 <-> 4

Doubly Linked List after deleting all occurances of node 2

1 <-> 3 <-> 4

Thanks for feedback.