But First, What is a Node?#

The building block of a linked list is a node. Every item of data, or the record, is stored as one or more main instance fields of the node, called the node’s value. Often in textbook problems we simply store ID numbers or simple values. In reality, we should be thinking that this value is a large structure such as a complete employee record. The other required instance field of a node is another node.

Read that again: a node consists of a node. This is a recursive definition, as the word we are defining is included in the definition. A node is a recursive data structure.

In Java the code for a node is:

public class Node{
   //Instance Fields ===========================
   private Object value;
   private Node next;   

   //Constructors ==============================
   public Node(Object inValue,  Node toNode) {
      value = inValue;
      next = toNode;
   }
   public Node(Object inValue){
      this(inValue, null);
   }
   public Node(){
      this(null, null);
   }

   //Getters ====================================
   public Object getValue() {
      return value;
   }
   public Node getNext() {
      return next;
   }

   //Setters =====================================
   public void setValue(Object value) {
      this.value = value;
   }
   public void setNext(Node next) {
      this.next = next;
   }
}

Visualization of a Node:









A node with two fields, value and next

null#

null is a reserved word in Java, and it means “nothing”. When we set next = null, we are saying that next refers to nothing, “to null”.

Generic Data Type#

Did you notice the data type of the value in the node? Object. This was used because we didn’t know what the actual data type would be, so we left it most general, but in reality, we might use the actual data type in place of Object. This means, though, that we would be rewriting our Node class every time we wanted a different type of value in the node. Remember we don’t like code repetition, yet keeping the data type of the value as Object means we have lost the type-checking capability of our compiler or IDE.

Java allows generic data types. These are data types that can vary, also called variable data types, which allow a data type to be different depending on the problem we are solving. Generic data types are appended onto the class name, written inside angle brackets <>, typically named with a single capital letter, and separated with commas if there is more than one. Here is the Node class again, now with a generic data type V:

public class Node<V>{
   //Instance Fields ===========================
   private V value;
   private Node<V> next;   
   
   //Constructors ==============================
   public Node(V inValue,  Node<V> toNode) {
      value = inValue;
      next = toNode;
   }
   public Node(V inValue){
      this(inValue, null);
   }
   public Node(){
      this(null, null);
   }

   //Getters ====================================
   public V getValue() {
      return value;
   }
   public Node<V> getNext() {
      return next;
   }
   
   //Setters =====================================
   public void setValue(V value) {
      this.value = value;
   }
   public void setNext(Node<V> next) {
      this.next = next;
   }
}

Examples of Nodes#

If we want to make a Node that contains an integer, 12, then we could do this:

Node<Integer> myNode = new Node<>(12);

See how the data type of the value inside the node is set as part of the data type of the node. Note that we cannot use int as the variable data type because all variable data types must bind with a reference data type, also called an abstract data type. This is a data type defined as its own class. This means we cannot do:

Node<int> myNode = new Node<>(12); //Error

Recall that all of the primitive data types have a wrapper class in Java, for example, Integer wraps int, Character wraps char, and Boolean wraps boolean.

Without using a different definition for Node, we can also make a node that contains an Employee, assuming that we have an employee defined in a class:

Node<Employee> oneEmployeeNode = new Node<>(new Employee());

Explicitly Build a Linked List#

Let’s make three nodes to hold names and link them together. Here is the potential Java code:

Node<String> node1 = new Node<>("Santa Claus");
Node<String> node2 = new Node<>("Tooth Fairy");
Node<String> node3 = new Node<>("Mickey Mouse");
        
node1.setNext(node3);
node3.setNext(node2);

We have made the following in the computer’s memory:

Three nodes in Memory

more commonly this is drawn as:

Three nodes in Memory
This is our first linked list. We made it manually, one node at a time, and linked those nodes together by setting the next fields. Each time a node was made, the computer dynamically, at run-time, grabbed just enough memory for each node.

Practice Questions#

  1. Make four nodes in this order: a node with the value 100, a node with the value 15, a node with the value 150, and a node with the value 75.

  2. Link the nodes from question 1) so that they are in order from smallest to largest.

  3. In your code from questions 1) and 2), how would you access the value 150 by sending dot messages using only the name of the node containing the 15.

  4. Make a node for each letter in your first name, and link those nodes so that your name is spelled in order from left to right.

To Solutions