Comp Sci CS: linked list confusion (Java)

[n00neimp0rtnt]

I just took my final for Data Structures and there was a question on it dealing with linked lists. A part of the question really threw me off. It looked something like this:

public class Node
{
     int contents;
     Node next;
}

public class LinkedList
{
     Node head, tail;
}

public void bar(int c)
{
     newNode = new Node();
     newNode.contents = c;
     [B]tail.next = newNode;
     tail = newNode;
     newNode.next = null;[/B]
}

The part of concern is in bold. When I read this, it looks like in the first line, tail.next is getting set to the Node that the reference "newNode" is pointing to. In the SECOND line, however, tail is getting set to the Node that "newNode" points to. If I'm not mistaken, doesn't that just nullify the first statement as if it was never executed? What happens to tail.next? After the second statement, isn't tail.next pointing to the same Node that newNode.next points to? I thought it was a typo so I asked my professor and he simply said that "tail.next is not 'inside' tail; they are two separate things," which didn't really help much.

 

[Filip Larsen]

If the precondition for the method is that tail points to the last Node on the list, then this method appends a new node to the end of a single-linked list without iterating through the whole list. Regarding your 3 highlighted lines:

Line 1: The previous tail node (pointed to by tail) is set to point to the new node, that is, the new node will now come after the previous tail node.
Line 2: The new node is then set as the new tail.
Line 3: The next node for the new node is set to null since this it is currently the tail (with the given code this line is for better readability rather than for necessity; the next field already has the value null).

 

[n00neimp0rtnt]

Hmm...so line 2 kinda "pushes back" the old tail and sets newNode as the NEW tail?

 

[Filip Larsen]

Thats one way of putting it. If you have trouble visualize it then make (or search for) a diagram that show what is pointing to what before and after the two lines.

 

[n00neimp0rtnt]

Ok, I think I get it now. I'm pretty sure I got the questions relating to it right because I had a hunch what the methods were supposed to do, it just bothered me that I didn't know how it worked.