Loop in a linked list

Question

I have the following code in Main.java trying to implement linked list taken from a book. It's a very basic question but makes me crazy. Would appreciate help!

class Node {
 Node next = null;
 int data;
 public Node (int d) {
 data = d;
 }
 void appendToTail (int d) {
 Node tailNode = new Node (d);
 Node currentNode = this;
 while (currentNode.next != null) { 
 currentNode = currentNode.next;
 }
 currentNode.next = tailNode;
 }
}
class Main {
 public static void main (String args[]) {
 Node n = new Node(10);
 n.appendToTail (11);
 n.appendToTail (12);
 n.appendToTail (13);
 }
}

So, on n.appendToTail(13); the following loop runs twice: while (currentNode.next != null) {... and on n.appendToTail(14); the same loop runs three times etc. Why? I don't understand.

I also don't understand the purpose of that loop - why isn't currentNode.next always null?

Any education would be appreciated.

Thank you.

• AxelH: Because of currentNode.next = tailNode;. Your loop go to the end of the list, and add your new node TailNode as the next of the currentTail. Meaning on each call, it will iterate to the end and add a new node to it

Answer 1

Simply beacuse currentNode.next = tailNode; is linking the new Node to the tail

> : represent a .next link

Node1 > Node2 > Node3

Calling appendToTail(4), the loop will gave currentNode the reference of Node3 (no > yet) and then put the new Node to this currentNode.next

Node1 > Node2 > Node3 > Node4

Calling appendToTail(5), same idea, currentNode will have Node4 because the is no next value

Node1 > Node2 > Node3 > Node4 > Node5

The loop is just here to find the end (represented by the absence of a next value)

Answer 2

n is pointing to the head of the list (Node(10)). Every time you add a node to the list by calling n.appendToTail(), the while loop will start at the head, and loop once for each node in the list, until it reaches the tail.

The first time you call it, it doesn't loop at all, because the condition on the while loop is false; there is only one node in the list, so it is already at the tail of the list (where currentNode.next == null). The second time, it runs once because there are now two items in the list: the first loop takes it from Node(10) to Node(11), and then it finds a null, which exits the loop.

For the third n.appendToTail(), it loops once to move from Node(10) to Node(11), and then a second time to move from Node(11) to Node(12). Only then is it at the tail of the list, exiting the loop.

• Vahe: Looks like I don't understand currentNode.next (lack of OO knowledge): why does that contain multiple (references) objects? I am sure it's simple, it's just I can't understand it and the book I'm using doesn't show that all. Would appreciate help!!
• Zak: currentNode.next doesn't contain multiple references, it just has one reference to the next node in the list. It is that node in turn that has a reference to another object. Each node in the list has one such reference, except the tail, which has a null for this value, because there is no node after it. This is the idea behind a linked list: it is a chain of objects, each with one reference to the next, rather than one object (the head of the list) that points to all the other elements.
• Vahe: Thanks. What about [Node n = this;] statement - does this always refer to the original (first) Node? Sorry, it must be a basic OO question, but i'm coming from a scripting world.
• Zak: this will always refer to the object that the method was called on. Because you called n.appendToTail(x), the use of this inside the method will refer to n. You only call the method on the head of the list in your code, so this happens to always refer to the first node, although you could equally call the method on any other node, and this would refer to that node instead (although calling append on any node other than the head is unusual for a linked list).

Answer 3

The reference n is always pointing to the first node. When you do

Node currentNode = this;

On every function call currentNode points to first Node. So when you do

n.appendToTail (11);

no loop will run because there is only one node. When you do

n.appendToTail (13);

there are already three node so it will loop twice