1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: CS: linked list confusion (Java)

  1. Apr 28, 2010 #1
    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:

    Code (Text):


    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.
     
  2. jcsd
  3. Apr 28, 2010 #2

    Filip Larsen

    User Avatar
    Gold Member

    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).
     
  4. Apr 28, 2010 #3
    Hmm...so line 2 kinda "pushes back" the old tail and sets newNode as the NEW tail?
     
  5. Apr 28, 2010 #4

    Filip Larsen

    User Avatar
    Gold Member

    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.
     
  6. Apr 28, 2010 #5
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook