CODEWITHSUNDEEP
javadata-structureslinked-list
Noam Hacker
Noam Hacker

Reputation: 4825

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!

Upvotes: 1

Views: 10186

Answers (1)

DeepakV
DeepakV

Reputation: 2470

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

Upvotes: 5

Related Questions