8.2. The Node Class

Remember: A linked list is not a Node. Instead, it is a sequence of connected nodes - each of which is a separate object. Typically, a linked list object contains a Node reference to the head (front) of the list along with a size variable indicating how many items are in the list. Linking together Node objects is an alternative way to store related data items.

Before diving into the concept of linked lists, we will explore the Node class to better understand how it works. To do this, we will trace through some code that uses the Node class shown in the UML diagram below. This version of the Node class stores a String reference along with a reference to another Node object.

Fig. 8.2 UML diagram showing the fields, constructors, and methods of the Node class. [svg] [png]

Let's take at some code we might use to generate a shopping list with three items using the Node class:

Listing 8.2 Creating and linking three Node objects for a shopping list.

Node head = new Node("Cheese");
head.setNext(new Node("Bread"));
head.getNext().setNext(new Node("Milk"));

Here, we are storing our shopping list with three separate Node objects instead of using an array. The resulting memory diagram looks like this:

Memory state after linking the Cheese, Bread, and Milk nodes into a shopping list. [download] [open]

To store the list, we needed to create one Node object for each item on the list - similar to how you would create one index for each of the items in an array.

At first glance, you probably think the code is trickier, and that's fair. However, that's only true when using the Node class directly. Later in this chapter, we will see how to implement the linked list class that hides the complexity from the programmer so that using linked lists becomes as easy as using an array.

Why have both linked lists and arrays? Well, each has their own benefits and drawbacks as we will see later in this chapter. Ultimately, which one you choose to store your data comes down to the type of application you are building and how you plan on using that data. More details soon.

Test Yourself

Fig. 8.3 The Node class used in the reference-tracing exercise. [svg] [png]

Using the Node diagram above, draw the complete memory map for the code below.

Once you are done, check your answer against the step-by-step solution given in the dropdown box.

Node finish = new Node("Hello");
finish.setNext(new Node("World"));
Node n = finish.getNext();
finish.setNext(new Node(","));
finish.getNext().setNext(new Node("!"));

Solution - Open After Completing Exercise

Use the stepper controls to follow execution through the exercise code in the generated Driver.java file. Calls to Node constructors and methods execute without pausing inside Node.java. Each caption identifies the line where execution is paused; that line is the next to execute and has not yet executed.

|< < Prev

Step 1 of 6: Driver.java:4

Next > >|

123456

Memory state while tracing changes to node links through finish and n. Note: The debugger breakpoint is on line 4 in Driver.java. [download] [open]

Memory state while tracing changes to node links through finish and n. Note: The debugger breakpoint is on line 5 in Driver.java. [download] [open]

Memory state while tracing changes to node links through finish and n. Note: The debugger breakpoint is on line 6 in Driver.java. [download] [open]

Memory state while tracing changes to node links through finish and n. Note: The debugger breakpoint is on line 7 in Driver.java. [download] [open]

Memory state while tracing changes to node links through finish and n. Note: The debugger breakpoint is on line 8 in Driver.java. [download] [open]

Memory state while tracing changes to node links through finish and n. Note: The debugger breakpoint is on line 9 in Driver.java. [download] [open]

Using your memory diagrams from the last step, write the output for the last seven lines of code. You should assume this code is in the same scope and has access to all the variables in your diagram.

System.out.println(finish.getItem());
System.out.println(finish.getNext().getItem());
System.out.println(finish.getNext().getNext().getItem());
System.out.println(finish.getNext().getNext().getNext());
System.out.println(n.getItem());
System.out.println(n.getNext().getItem());
System.out.println(n.getNext().getNext());