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.

Post a Comment