Linked Lists

Introduction

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 data;
   Node next;
}

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
    
  2. head.next = head.next.next;           // deletes the second element of the list
    
  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
    

Common Linked List Operations

Adding an Item/Node to the Front of a List

To add an item/node to the front of the list (i.e., the end referenced by head), one can use code similar to the following. Note, in combination with a method to remove the first item/node previously discussed, you have the basic elements for a linked list implementation of a stack.

public void addFirst(Item item) {
   Node n = new Node();
   n.item = item;
   n.next = head;
   head = n; 
}

Traversing a List

To do something to each element of a list (inspect it, modify it, etc.), we can traverse the list using something similar to the modified for-loop below.

for (Node n = head; n != null; n = n.next) {
   // process n.item
}

Adding an Item/Node to the End of a List

To add an item/node to the end of the list will require traversing the entire list (unless you also keep a reference to the last element as an instance variable). The trick is to remember to stop on the last node, and not on null, as it is this last node whose reference must be changed to accomplish the addition.

public void addLast(Item item) {
   Node newEnd = new Node();
   newEnd.item = item;
   newEnd.next = null;
   
   if (head == null) 
      head = newEnd;
   else {
      Node tmp = head;
      while (tmp.next != null) 
         tmp = tmp.next;
      tmp.next = newEnd; 
   }
}

Note, having to traverse the entire list is very inefficient -- just think of how much wasted time would be involved if your list was a million nodes long! Truly, the better way to do this is to add an instance variable (perhaps called tail) to the LinkedList class that keeps a reference to the last element of the list, as the below code demonstrates:

public void addLast(Item item) {
   Node newEnd = new Node();
   newEnd.item = item;
   newEnd.next = null;
   
   if (head == null)
      head = newEnd;
   else 
      tail.next = newEnd;
   
   tail = newEnd;    // don't forget to update tail!
}

Expanding the instance variables of any class should always be done cautiously, however! One must consider the cost and potential inefficiencies of having to update this new instance variable in all of the other methods the class employs.


Adding an Item/Node After a Key Item

To insert a node/item just after the first node in our list that contains some key item, we can traverse the list until the key is found and then adjust the references appropriately, as the below accomplishes. Note, if the key is not found -- for simplicity's sake -- the method below simply doesn't insert anything. One could let the client know this by returning a boolean to indicate whether or not the insertion happened. One could also throw an exception upon a failed insertion, if that was more appropriate.

public void insertAfter(Item key, Item itemToInsert) {
   Node nodeToInsert = new Node();
   nodeToInsert.item = itemToInsert;
   
   Node tmp = head;
   while ((tmp != null) && (! tmp.item.equals(key)) 
      tmp = tmp.next;
   
   if (tmp != null) {
      nodeToInsert.next = tmp.next;
      tmp.next = nodeToInsert;
   }
}

Adding an Item/Node Before a Key Item

Suppose one wished to insert a node/item just before the first node in our list that contains some key item. In this case we could, for the sake of convenience, maintain two references previous and current, so that as we traversed the list, looking for the key, we shifted these two references in tandem, always keeping previous one node before current. Then upon current reaching the node containing the key, we use both of these references to accomplish the insertion between them, as the code below indicates. (Note, in the code below -- as with the previous example -- if the key is never found, no insertion is made.)

public void insertBefore(Item key, Item itemToInsert) {
   Node nodeToInsert = new Node();
   nodeToInsert.item = itemToInsert;
   
   Node previous = null;
   Node current = head;
   
   while (current != null && (! current.item.equals(key))) {
      previous = current;
      current = current.next;
   }
   
   if (current != null) {
      previous.next = nodeToInsert;
      nodeToInsert.next = current;
   }
}

Deleting an Item/Node

To delete some key item (and its corresponding node) from the list, we again find it convenient to maintain two references previous and current. However, one should note that things must be handled differently when the key is found at the head of the list, as previous will still be null. (Here again, for simplicity's sake -- if the key is never found, nothing happens.)

public void removeFirstOccurrence(Item key)
{
   Node previous = null;
   Node current = head;
   
   while (current != null && (! current.item.equals(key))) {
      previous = current;
      current = current.next;
   }
   
   if (current != null) {
      if (current == head) 
         head = head.next;
      else 
         previous.next = current.next;
   }
}

Adding an Iterator

One can provide (sequential) access to the data stored in the list, while still hiding the underlying representation by adding an inner class that implements the Iterator interface and a iterator method, so that the LinkedList class can implement the Iterable interface, as the below code demonstrates.

public class LinkedList implements Iterable {

   private static class Node {
       Item item;
       Node next;
   }

   private Node head;
   
   ...
   
   public class HeadToTailIterator implements Iterator {
   
      Node node = head;
      
      public boolean hasNext() {
         return (node != null);
      }
      
      public Item next() {
         Item itemToReturn = node.item;
         node = node.next;
         return itemToReturn;
      }
   }
   
   public Iterator iterator() {
      return new HeadToTailIterator();
   }
}

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