Linked Lists

One disadvantage of using arrays to store data is that arrays are static structures and therefore cannot be easily extended or reduced to fit the data set. Arrays are also expensive to maintain new insertions and deletions. As such, we consider another data structure called a Linked List that addresses some of the limitations of arrays.

A linked list is a recursive data structure that is either empty (null) or a reference to a node that contains a data item and a reference to another node. Through this structure, a linked list creates a sequence of nodes chained together, where each node contains a data item and a reference to the next node.

Below is an example of a node class for a linked list:

class Node {
   Item item;  // <-- the data to be stored in this node
   Node next;  // <-- a link to the "next" node
}

The last node has a reference to null. Note, the node class is self-referential. That is to say, the node class contains a reference to itself.

A reference to a linked list could simply be a reference to the first node of that list. That said, one more often encapsulates the reference to the first node of a given linked list as an instance variable (often called head) in some enclosing linked list class, as shown below. (Recall, there are two kind of inner classes: static and non-static. A static inner class cannot refer directly to instance variables or methods defined in its outer class: it can use them only through an object reference. Below, we choose to make the Node class static.):

public class LinkedList {
    
    private static class Node {
        Item item;
        Node next;
    }
   
    // instance variables
    private Node head;
    
    ...
    

It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then head is a null reference.

Linked lists and arrays are the two fundamental ways in which sequential data can be stored. There are advantages and disadvantages to both:

Types of Linked Lists

There are many variations on a theme, when it comes to linked lists. The linked list previously described is known as a singly linked list, as each node only keeps a reference to its successor node.

In a doubly linked list is a list that has two references, one to the next node, and another to previous node.

A third variant of a linked list is called a circular linked list, where the last node of the list points back to the first node (or the head) of the list.

Using the "Next" Reference

Consider the effect of each fragment below on the singly linked list of 4 elements previously described. (Assume the list is restored to its initial state before each line is executed.)

  1. head = head.next;                     // deletes the first element of the list as
                                          // objects with no references to them
                                          // are subject to garbage collection
    
  2. head.next = head.next.next;           // deletes the second element of the list
                                          // again as objects with no references to
                                          // them are subject to garbage collection
    
  3. head.next.next.next.next = head;      // creates a circular linked list
                                          // in this case, as our initial list
                                          // is only 4 nodes long initially
    

Original images and some text by Victor S.Adamchik, CMU, 2009; adapted by P. Oser