appending to linked list

Question

i was wondering how the while loop ever executes. since we set 'next' to be null when we first declare it, when does it get changed to not null? and also what does ' Node n = this; ' mean? Is that meaningful for this code? Whenever we declare a new instance of the object Node, does it make a copy of its own separate fields from the class? Thanks a bunch! I would definitely appreciate clear and easy to understand explanations. Thanks again = )

class Node {
    Node next = null;
    int data;
    public Node(int d) { data = d; }
    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) { n = n.next; }
        n.next = end;
    }
}

Answer 1

To answer your questions:

Q: "since we set 'next' to be null when we first declare it, when does it get changed to not null?"

When you have only one item in the list, the 'next' value of that Node will be set to NULL.

Q: "and also what does ' Node n = this; ' mean?"

This statement means that the reference variable 'n' takes the reference of the current object, which is specified by 'this'.

Q: "Whenever we declare a new instance of the object Node, does it make a copy of its own separate fields from the class?"

Instance variables will be created for each individual class that you make an instance of. This means that every Node will have 'next' and 'data'.

Thus, in your creation process, you will probably have something like this:

Also, the while loop iterates to the end of the list and appends the item after the last node in the list.

Hope it helps (: If you have any questions, do post back (:

Answer 2

So you have a class called Node with two instance variables called next and data. They are called instance variables because they belong to the instances of this class rather than to the class itself. That is, your class is basically a template (or blueprint) for objects that each willhave their own data value and next value.

In order to create an instance of the Node class you need to call the constructor and pass the necessary parameters. In your case the constructor is;

  public Node(int d) { 
       data = d; 
  }

To call this constructor you use the new keyword (in Java I assume) like this;

   Node x = new Node(10);

And notice that you must supply an integer value to the constructor. In the body of the constructor (between the {}) you see that the variable data is assigned to the value in d which is the value that you pass to the constructor, in this example the value 10. You now have an object of type Node with the value 10 as it's data and a null next Node.

On that object you can now call the method appendToTail(). Lets say we do this:

   x.appendToTail(20);

Lets trace what happens.

    Node end = new Node(d);

A new node named end is created and we set the value 20 to data (remember that d has the value 20 for now because that is the value we passed when we were calling the method). This is a completely independednt node from x with its own unique value for data.

    Node n = this;

this is a self reference to the current object. Since we called this method on x then this is the same object as x.

    while (n.next != null) { 
        n = n.next; 
    }

This while loop is going to start looking for the end of the list by going from the current node to the next node until the next node is null. Since the only node we created so far is x then n.next is actually null so the while loop does not execute this time.

    n.next = end;

Now we are setting the next value of n (which is x) to the node end that was created. You now have a list like this:

  10 -> 20 -> null

Suppose you were to make the following call:

  x.appendToTail(30);

Then a similar thing happens except when you get to the while loop the value n.next is not null so you go into the body of the loop and assign n to point to n.next which in our example is the node with 20. The next iteration of the loop would yield the null so the loop will quit and the new node with data 30 will be set to the next value of the last node in the list. So you will have :

  10 -> 20 -> 30 -> null

Answer 3

No the node does not copy itself. The point of the linked list is to have a node refer to the next in line. So if you have 3 items in a linkedlist, the first node has a reference to the second, and the second to the third.

Node one = new Node(1);
one.appendToTail(2);

will result in node one, having created a new node, and put it in it's next field one.next.data will be equal to 2.

one.appendToTail(3)

will result in node one referring to node 2, and node 2 will create node 3, and set it as it's next field.

one.data == 1
one.next.data == 2
one.next.next.data == 3

The loop is basically to search the last node in line (because it has it's next set to null).