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

1. Create two pointer say current and previous
2. Set current on head and previous as NULL
3. While current is not NULL and current.data is equal to given node
   • head = current.next
   • current = head
4. Now for traversing remaining linked list,while current is not NULL and current.data is not eqaul to given node
5. Make previous = current and current = current.next
6. After loop terminate,if current is NULL then return
7. 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