CODEWITHSUNDEEP
javalinked-list
vubo
vubo

Reputation: 45

How this Java code works? Remove duplicates from an unsorted linked list

I have a LinkedList Node class: 

public static class Node {
    int value;
    Node next;

    Node(int value){
        this.value = value;
        this.next = null;
    }
}

And the delete duplicates method:

public static void deleteDups(Node n) {
    Hashtable<Integer, Boolean> table = new Hashtable<Integer, Boolean>();
    Node previous = null;
    while (n != null) {
        if (table.containsKey(n.value)) previous.next = n.next;
        else {
            table.put(n.value, true);
            previous = n;
        }
        n = n.next;
    }
    }

public static void printList(Node list) {
    Node currentNode = list;
    while(currentNode != null) {
        System.out.print(currentNode.value + ", ");
        currentNode = currentNode.next;
    }
    System.out.println("");

}

It works. But how? In the method I delete the list n and at the end n is null. But why it is not null here:

Node list = new Node(5);
list.next = new Node(2);
list.next.next = new Node(3);
list.next.next.next = new Node(2);
list.next.next.next.next = new Node(1);
list.next.next.next.next.next = new Node(3);

printList(list);    
deleteDups(list);
printList(list);

Output: 

5, 2, 3, 2, 1, 3
5, 2, 3, 1

What I missed?

If I print n and previous:

  public static void deleteDups(Node n) {
    Hashtable<Integer, Boolean> table = new Hashtable<Integer, Boolean>();
    Node previous = null;
    while (n != null) {
        if (table.containsKey(n.value)) previous.next = n.next;
        else {
            table.put(n.value, true);
            previous = n;
        }
        n = n.next;

        System.out.println("");
        System.out.println("");
        System.out.print("previous is ");
        printList(previous);            
        System.out.print("n is ");
        printList(n);
    }
    }

The output is:

previous is 5, 2, 3, 2, 1, 3, 
n is 2, 3, 2, 1, 3, 


previous is 2, 3, 2, 1, 3, 
n is 3, 2, 1, 3, 


previous is 3, 2, 1, 3, 
n is 2, 1, 3, 


previous is 3, 1, 3, 
n is 1, 3, 


previous is 1, 3, 
n is 3, 


previous is 1, 
n is

At the end n and previous are null! How it works then?

Upvotes: 3

Views: 175

Answers (2)

Aron_dc
Aron_dc

Reputation: 863

Simply said it iterates the linked list and remembers each value it encountered. If it encounters a value it has already seen it breaks off the duplicate entry in the chain by connecting the previous node (the one it encountered before the duplicate) with the next one (the one after the duplicate one).

Just imagine it like taking a link out of chain.

This whole algorithm works in situ thus there is no need to recreate the list afterwards. You just throw away nodes that aren't needed anymore.

This is a bit dangerous as there could still be references to Nodes that aren't part of the filtered linked list anymore. It would be better to invalidate them somehow.

On the other hand the Nodes next properties will always lead to either a Node of the filtered linked list (after n steps) if there is still a value in the list the algorithm did not yet see or to null if the duplicate Node was at the end of the linked list already. Nevertheless the next Nodes will still have duplicates in it until it arrives at a Node that is part of the duplicate free linked list again but one could change the algorithm so that even this won't happen.

edit for answering why printList prints nothing/null at the end:

This is because n isn't your start node anymore at this point, it's always the "next" node. So at the end n is actually "null" because "null" is the element after the last node. You have to hold on your starting Node n (the one you passed into the deleteDups method, because this node depicts the starting node of your filtered list. You printList method only prints all the next nodes after the node you passed to it. So the last call that happens is your printList(previous) (this contains the last element) and printList(n) that does nothing because n is "null" at that point.

Just try to create a linked list of your nodes. Then pass the first Node into deleteDups and afterwards call printList with the Node you passed into it.

 Node start = new Node(...);

 //Initialize and connect more nodes consecutively here

 printList(start); //unfiltered List will be printed     
 deleteDups(start);
 printList(start); //filtered List will be printed, all duplicates have been unhinged from your linked list

Upvotes: 3

fluminis
fluminis

Reputation: 4079

The list is "re-created" with this : previous.next = n.next; The Node are altered and the item to skip is remove with this operation

2 --> 3 --> 2
previous.next = n.next;
2 --------> 2

Upvotes: 0

Related Questions