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