Delete duplicates in a linked List I am reading Cracking the Code Interview and I am getting a bit confused at the bit using 'previous'. In this problem, the method deletes duplicate nodes in a Linked List. 

My assumption is that head is used to scan through the linked list while previous is used to update the linked list head because previous points to the same linked list. Not sure if my assumption is correct. Could someone verify this please?

Perhaps someone could also provide a method of increasing the efficiency or space of this program? I would love your input!

public static void deleteDups1(LinkedListNode head) {
    Hashtable&lt;Integer, Boolean&gt; table = new Hashtable&lt;Integer, Boolean&gt;();
    LinkedListNode previous = null;
    while(head != null) {
        if (table.containsKey(head.value)) previous.next = head.next;
        else {
            table.put(head.value, true);
            previous = head;
        }
        head = head.next;
    }
}
You are right about head, it is used to move through the list. previous is a temporary pointer that is needed to perform the delete. You need it because the delete process means taking the next value of the Node to the left, and making it 'skip' the deleted Node and point over to the right of the deleted Node.

The list is linked by each Node having a next pointer. It would look something like:

A -&gt; B -&gt; A -&gt; C -&gt; D -&gt;


Here the first A points to B, which points to a different A, which points to C, and so on.

You would call your method with the pointer to the first A as the argument head. There is no previous ....

So your system starts off looking like:

     A -&gt; B -&gt; A -&gt; C -&gt; D -&gt;
^    ^
P    H


Where H is the Head pointer, and P is the previous.

We add the value A to the HashMap, and advance our pointers:

    A -&gt; B -&gt; A -&gt; C -&gt; D -&gt;
    ^    ^
    P    H


B is not in the HashMap, so move on....

    A -&gt; B -&gt; A -&gt; C -&gt; D -&gt;
         ^    ^
         P    H


A is in the HashMap, so we have a duplicate. This is where P comes in to play....

We make the B (pointed to by previous) point to C....

    A -&gt; B  ---&gt;  C -&gt; D -&gt;
         ^      /
         |    A
         |    ^
         P    H


We do that by making the previous's next point to the head's next. We now have a kind of 'fork' in the list, with the second A dangling part way through....

We have now removed the A from the main link chain, and we need to advance the head pointer to C.... Sunce Nothing is pointing to the second A now, it can be garbage collected, etc... and the final result looks like:

    A -&gt; B  ---&gt;  C -&gt; D -&gt;
         ^        ^
         P        H


Now, about your other questions.....

This operation is about as fast as it can get. Not much you can do to improve performance.

Additionally, the operation essentially uses no stoage (there is some stack amount, but this is peanuts in the scheme of things....

If this list is able to cover your use cases, then I would say "Great, use it".