A linked list is a list of data items where each item only knows about the next item in the list if there is one. Figure 2.5 shows one such example. Each box in the figure represents a container for a data item we need to store. This container, called a node, contains our data values and a pointer to the next node in the list. As the diagram shows, the node on the front of the list is called the head of the list and the last item of the list is called the tail.

Separate pointers to these nodes are stored for easy access of the data structure:

The advantage of using a linked list as opposed to an array is that a linked list can grow dynamically. When using an array, you allocate space in the start and that space remains fixed. If you allocate too much and the space remains unused, you're wasting resources. On the other hand, if you make your array too small, the data might not ft. In a linked list, however, the space is not fixed. The structure grows dynamically as you add more data and it shrinks, freeing memory space as you remove it.

Using an object-oriented language, such as Java, let's model the linked list using separate node instances that are connected together to build our linked list. The following code shows how we can model a linked list node in a Java class.

The class contains a self-reference so we can link multiple nodes in list fashion, as shown in the Figure 2.5.

public class LinkedListNode<V> {
  private V value;
  private LinkedListNode<V> next;  
  public LinkedListNode(V value, LinkedListNode<V> next) {
    this.value = value;
    this.next = next;
  }
  public Optional<LinkedListNode<V>> getNext() {
    return Optional.ofNullable(next);
  }
} 

Notice how we use Java's optional classes (instead of returning null pointers) to represent whether there is a link to the next node. The tail node of a linked list will always have an empty optional. We also make use of generics to model the type of data we want to store. This way, we can keep the structure as general as possible so that it can used by any data type.