Nodes

In the main part of the lab, you’re going to be implementing linked lists so we’re going to walk through writing a simple linked list data structure. A linked list consists of a sequence of nodes. A node is a very simple data structure that contains an element and a link to the next node in the sequence.

Nodes

Open the LinkedNode.java file from the Lab 4 repository.

We want to be able to use our LinkedNode class to hold any given type of object, so change:

public class LinkedNode

to

public class LinkedNode<E>

Add two public instance variables E data and LinkedNode<E> next inside the LinkedNode class. Add a public constructor public LinkedNode(E data, LinkedNode<E> next) that sets the this.data and this.next fields to data and next.

The next field of the LinkedNode class is what forms the link in our linked list. This link is also called a pointer or a reference (but note that those words have specific meanings in other programming languages). We could create three nodes and chain them together like this:

LinkedNode<String> thirdNode = new LinkedNode<String>("third", null);
LinkedNode<String> secondNode = new LinkedNode<String>("second", thirdNode);
LinkedNode<String> firstNode = new LinkedNode<String>("first", secondNode);

Add this code to your main method in LinkedNode.java

Notice that:

  • firstNode.next is secondNode;
  • firstNode.next.next and secondNode.next are thirdNode (this is true because firstNode.next is secondNode, so firstNode.next.next is literally the same thing as secondNode.next); and
  • firstNode.next.next.next, secondNode.next.next, and thirdNode.next are null.

That null in thirdNode.next is really important. That’s how we know it’s the last element in the list. We’ll shortly see how we can use the next fields to walk down the list, one element at a time using a loop.

Walking through a linked list

Let’s add code to our main method that will walk through all of the elements and print them out.

How can we do that? We know that we can use firstNode.data to get the data of the first node in the list and firstNode.next.data to get the data of the second node in the list and firstNode.next.next.data to get the data of the third node in the list and so on. But (a) this is terrible; and (b) we’d need to know how many elements were in the list to be able to print it out!

Instead, we can use a loop Here’s an example using a while loop.

LinkedNode<String> node = firstNode;
while (node != null) {
    System.out.println(node.data);
    node = node.next;
}

What’s happening here is that node is initially set to the first element of the list (or null if the list is empty). Then, at the end of each iteration of the loop, node is set to the next node in the list. See how we used null to recognize that we’ve reached the end of the list?

We can actually do the same thing slightly more concisely using a for loop!

for (LinkedNode<String> node = firstNode; node != null; node = node.next) {
    System.out.println(node.data);
}

Which one you use is often a matter of preference.

Add code to your main method that prints out the set of LinkedNodes you just created.