Noam Hacker Noam Hacker - 1 month ago 12
Java Question

References to nodes in Java linked list

I need some help understanding how a method works.

I have a basic

Node
class defined like this:

class Node {
Node next = null;
int data;
public Node(int d){
data = d;
}
}


Now I'm looking at how this
deleteDuplicates
method is working. I understand that we are passing through each node iteratively and storing its value in a set. If the value is already in the set, I believe we are setting the previous node's
next
pointer to skip the current node. Here's the method:

public static Node deleteDuplicates(Node head){
Node n = head;
HashSet<Integer> set = new HashSet<Integer>();
Node previous = null;
while(n != null) {
if (set.contains(n.data)){
// skip this node
previous.next = n.next;
}
else {
set.add(n.data);
previous = n;
}
n = n.next;

}
return head;
}


I'm confused about the variables
previous
and
n
. When we set
previous = n;
, isn't that making them reference the same object? If they reference the same object, one change you make to
n
will be the same in
previous
. So how does the line
previous.next = n.next;
work?

Thanks!

Answer

read these 2 lines together,

previous = n;  
n = n.next;

So, once a node is processed, the pointers for previous and n are moved forward. n is next node after previous, thus previous is set to n, and n is moved to its next node, which is n.next

For the deletion part, hope the diagram below helps

enter image description here

Comments