how is the linked list actually being changed

i was wondering if anyone could help me with this question. i believe i understand the code and logic for the most part. i can trace code and it makes sense, but one thing i don't get is....how does the LinkedListNode previous actually change the LinkedListNode n that is passed in?

it seems to me that the function loops through n, and if the element is not yet found puts it into a hashtable. but when it is found again, it uses this newly created LinkedListNode previous to skip over the duplicate and link to the following element, which is n.next. How does that actually disconnect LinkedListNode n? It seems like previous would be the LinkedListNode that has no duplicates, but since nothing gets returned in this function, n must be the one that changes. I guess I'm not seeing how n actually gets changed.

Clear and thorough help would be much appreciated. Thank you = )

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开发者_如何学C;
    }
}

doesn't the line...

LinkedListNode previous = null;

create a new LinkedListNode?

so this is my logic of how i'm doing it... lets say the argument, n, gets passed in as

5 -> 6 -> 5 -> 7

when the code first runs, previous is null. it goes into the else statement, and previous is now 5? and then the line n = n.next makes n 6? now the hashtable has 5, and it loops again and goes into the else. prev is now 6 and the hastable has 6. then n becomes 5. it loops again but this time it goes into the if, and prev is now 7. and n will become 7. i see that prev skipped over 5, but ...how is prev unlinking n? it seems like prev is the LinkedListNode that contains no duplicates

---

how does the LinkedListNode previous actually change the LinkedListNode n that is passed in?

Look at the line

n = n.next;

This line causes the passed node n to change - effectively moving it one node forward with each iteration.

it uses this newly created LinkedListNode previous to skip over the duplicate and link to the following element

No, no node is newly created here. The node previous always points to a node in the existing LinkedList of which the passed node n is one of the nodes. ( may be the starting node ). What makes you think it is newly created ?

It looks like you are confused in your understanding of how nodes and references ( and so a LinkedList as a whole ) works in Java. Because all modifications occur on the Node's data , and not the reference itself , ( ugh.. thats not entirely correct ), the original LinkedList passed to the method does get modified indeed after the method returns. You will need to analyse the LinkedList structure and workings in details to understand how this works. I suggest first get clarity about what pass by value and pass by references are in Java.

edit :

Your analysis of the run is correct , however your confusion still remains because you are not conceptually clear on certain things.

Towards the end of your analysis , you ask "..how is prev unlinking n? it seems like prev is the LinkedListNode that contains no duplicates "

This is a mess - first , you need to differentiate between a LinkedListNode and a LinkedList itself. prev and n are two instances of LinkedListNode, not LinkedList itself. In your example , the LinkedList is unnamed ( we dont have a name to refer to it ). This is the original list - there is no other list.

Second , in your illustration , the numbers you show are only one part of the node , called the node data. The other part, that you have missed out, is the next LinkedListNode reference that is implicit in every node. The link that you draw -> is actually the next reference in each node.When you say that prev skips 5 , what actually happens is that the next of node with data 6 is made to point to node with data 7.

At start : 5|next -> 6|next -> 5|next -> 7|next->NULL

After 5 is skipped : 5|next -> 6|next -> 7|next->NULL

As you see , the linkedlist is changed ! It does not matter if it was changed using prev or n, the change remains in the list.

---

if(table.containsKey(n.data))
            previous.next = n.next

Is the section which does the deletion. It assigns the reference of the prior node's next field to the node after the current node, in effect unlinking the current node.