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

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

---

Given a Linked list and key to delete, Remove all the occurrences of a given key in singly linked list.

Lets understand what is the input and the expected output.

Algorithm 

---

There are multiple ways to delete all occurrences of an item in a linked list, we will see few of them.

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

---

package com.javabypatel.linkedlist;
/*

Input:
        Linked list = 10 -> 10 -> 20 -> 30 -> 40 -> 10
        occurrenceToDelete = 10
Output:
        20 -> 30 -> 40


Input:
        Linked list = 10 -> 10
        occurrenceToDelete = 10
Output:


Input:
        Linked list = 10 -> 10 -> 20 -> 30 -> 40 -> 10
        occurrenceToDelete = 60
Output:
        10 -> 10 -> 20 -> 30 -> 40 -> 10


 */
public class DeleteOccurrencesFromLinkedList {

    public static void main(String[] args) {
        Node startNode = new Node(10);
        startNode.setNext(new Node(10));
        startNode.getNext().setNext(new Node(20));
        startNode.getNext().getNext().setNext(new Node(30));
        startNode.getNext().getNext().getNext().setNext(new Node(40));
        startNode.getNext().getNext().getNext().getNext().setNext(new Node(10));

        int occurrenceToDelete = 10;

        printLinkList(startNode);

        Node occurrencesRemovedListMethod1 = deleteOccurrencesUsingExtraLinkedList(startNode, occurrenceToDelete);
        System.out.println();
        printLinkList(occurrencesRemovedListMethod1);

        Node occurrencesRemovedListMethod2 = deleteOccurrencesFromLinkedListInPlace(startNode, occurrenceToDelete);

        System.out.println();
        printLinkList(occurrencesRemovedListMethod2);

        Node occurrencesRemovedListMethod3 = deleteOccurrencesFromLinkedListInPlaceAnotherApproach(startNode, occurrenceToDelete);

        System.out.println();
        printLinkList(occurrencesRemovedListMethod3);
    }

    private static Node deleteOccurrencesFromLinkedListInPlace(Node startNode, int occurrenceToDelete) {

        Node tmp = startNode;

        //Except First Node remove all Node matching occurrenceToDelete.
        while (startNode != null && startNode.getNext() != null) {
            if (startNode.getNext().getData() == occurrenceToDelete) {
                startNode.setNext(startNode.getNext().getNext());
            }
            startNode = startNode.getNext();
        }

        //Only remaining item to check is the first node of linked list.
        //Check if first node contains data as to occurrenceToDelete, then return the next node of current node
        //else return the list
        if(tmp.getData() == occurrenceToDelete) {
            return tmp.getNext();
        }

        return tmp;
    }

    public static Node deleteOccurrencesFromLinkedListInPlaceAnotherApproach(Node startNode, int occurrenceToDelete) {

        //create dummy first node, so our actual list starts from dummy.next
        Node dummy = new Node();
        dummy.setNext(startNode);

        Node current = dummy;
        while (current.getNext() != null) {
            if (current.getNext().getData() == occurrenceToDelete) {
                current.setNext(current.getNext().getNext());
            } else {
                current = current.getNext();
            }
        }

        return dummy.getNext();
    }

    private static Node deleteOccurrencesUsingExtraLinkedList(Node startNode, int occurrenceToDelete) {

        Node tmpForIterating = null;
        Node tmpForRootNode = tmpForIterating;

        while (startNode != null) {
            if (startNode.getData() != occurrenceToDelete) {

                Node nodeToInclude = new Node(startNode.getData());

                if (tmpForIterating == null) {
                    tmpForIterating = nodeToInclude;
                    tmpForRootNode = nodeToInclude;
                 } else {
                    tmpForIterating.setNext(nodeToInclude);
                    tmpForIterating = tmpForIterating.getNext();
                }
            }
            startNode = startNode.getNext();
        }
        return tmpForRootNode;
    }

    private static void printLinkList(Node startNode) {
        Node tempNode = startNode;
        while (tempNode != null) {
            System.out.print(tempNode.getData() + " ");
            tempNode = tempNode.getNext();
        }
    }
}

class Node{

    private int data;
    private Node next;

    public Node() {}
    public Node(int data) {
        this.data = data;
    }
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
}

You may also like to see

---

Sort Linked list using Merge sort

Bubble Sort

Heap Sort

Selection Sort

Insertion Sort

---

How ConcurrentHashMap works and ConcurrentHashMap interview questions

How Much Water Can A Bar Graph with different heights can Hold

Interview Questions-Answer Bank

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.