Linked List and pointer clarification

Question

In the Cracking the Coding Interview Linked List question: Write code to remove duplicates from an unsorted linked list, the solution is

public static void deleteDups (LinkedListNode n){
  Hashtable table = new Hashtable();
  LinkedListNode previous = null;
  while(n!=null){
      if(table.containsKey(n.data)){
          previous.next = n.next;
      } else {
          table.put(n.data, true);
          previous = n;
      }
      n = n.next;
  }
}

My question is why does n = n.next not alter the linked list passed into the function, but doing previous.next = n.next and previous = n do alter the linked list passed in?

Aside: if you use a `Hashtable` in a modern Java interview, you will likely do poorly. — dimo414, Aug 17 '15 at 18:20

Florian Schaetz · Answer 1 · 2015-08-17T18:24:18.110

n is a reference to a LinkedListNode. By setting a different value there, you don't modify the original LinkedListNode, just change a reference from it to something else. In other words, you "remember" something new under the label "n", but you do not modify the original "n".

X x = new X();
x = new X(); // this does not modify the original x

previous is the LinkedListNode and by setting a value OF that LinkedListNode, you are modifying it.

X x = new X();
x.y = new Y(); // this does mofiy the original x

In other words, you are setting a property of the value you remembered as "previous".

And, as dimo414 already mentioned, using HashTable here is a bad idea. Clarity alone should be enough reason to use a simple (Hash-)Set.

score 1 · Answer 2 · answered Aug 17 '15 at 18:19

n is the pointer to the relevant linked list node.

n = n.next

simply moves the pointer to the next node.

previous.next = n.next

changes where the node "previous" points. previous.next is a value contained in object "previous", the node after previous. So previous.next = n.next modifies the "previous" node object.

Linked List and pointer clarification

2 Answers2