Linked Lists

Install the App

Download the source archive
MyLinkedList.zip
Extract and install it into NetBeans as a Java Project with Existing Sources.

Linked Structures

Linked structures are common in Computer Science. In the most general sense they are graphs, consisting of nodes (or vertexes) and edges. Specializations of such graphs are linked lists in which the nodes form a linear chain. Java has the LinkedList class:
public class LinkedList<T> 
       implements List<T>, Deque<T>, Cloneable, Serializable
We have discussed all these interfaces in Generic Lists except for the new Deque interface which adds these important prototypes:
T getFirst()               T getLast()
void addFirst(T elt)       void addLast(T elt)
T removeFirst()            T removeLast()
In particular, the LinkedList class is commonly used to provide the end-only access methods of the Deque interface in addition to the position-based access methods of the List interface, and the aggregate access methods of the Collection interface.

A notable implements omission is the RandomAccess interface which is implemented by ArrayList, but not by LinkedList. This means that the get/set method access speeds, as you will see, are dependent on the size of the list.

A Java generic class which uses linked structures has the general form:
public class LinkedStructure<T> {
  ...
  private static class Node<T> {
    T item;
    Node<T> links-to-other-nodes;
  }
}
The Node class is a private inner class which is self-contained, accessing no internal parent class data, and so is static. The Node class has no member function structure whatsoever. The fields are meant to be manipulated directly as data members.

Equality in Java Linked Lists

This example confirms that object equality must be written correctly in LinkedList as well as in ArrayList. The class User is exactly the same as in Generic Lists:
mylinkedlist.User  
The driver class uses LinkedList instead of ArrayList and tests the search operations in a LinkedList.
mylinkedlist.UserInterfaces  

Overloaded equals cannot work in template classes

Here's a demo that aims to show that equals must use the overriden, not the overloaded version to ever work in a template class.

mylinkedlist.CompareCheck
package mylinkedlist;
 
public class CompareCheck<T> {
 
  private User u = new User("Jill",20);
 
  public void testEquals(T obj) {
    System.out.println(u.equals(obj));
    System.out.println(obj.equals(u));
  }
}

mylinkedlist.TestCompare
package mylinkedlist;
 
public class TestCompare {
 
  public static void main(String[] args) {
    CompareCheck<User> cc = new CompareCheck<>();
 
    cc.testEquals(new User("Jill", 33));
  }
}
The TestCompare driver illustrates the point by calling the internal testEquals method within the template class CompareCheck. The output correctly gives 2 true values when the overridden equals is used in User, and 2 false values when the overloaded equals is used.

Singly-linked Lists

The place to begin understanding linked lists is with so-called singly-linked lists which use the following internal Node structure:
  private static class Node<T> {
    T item;
    Node<T> next;
 
    Node(T item, Node<T> next) {
      this.item = item;
      this.next = next;
    }
  }
Like any Java object, an instantiated Node is a pointer to the instantiated content. Thus,
Node<T> n = new Node<>(item,next);
looks like this:
Diagrammatically, a singly-linked list might look like this:
The groupings show each Node and suggest the idea on linking. A null value for Node, indicated by the diagonal line, represents an end of the chain. This linked node structure suggests that the list it is modeling is
[59, 33, 22, 47, 19]

Data members

The only data member really necessary in a singly-linked list is
Node<T> first;
Given the depiction above, the initial empty list is represented by:
first = null;
The other common data member is:
int size;
This is initially set to 0 and it is modified whenever a node is added or removed.

List with header node

An alternative singly-linked list structure representing the same list [59,33,22,47,19] could be this:
The initial node, called a header node, serves as a place-holder. Its content, blacked-out, does not participate in the list. We have depicted position numbers for each of the node elements and the header node logically would be position -1. An empty list is depicted like this:
and is represented by the code:
first = new Node<>(null,null);
The header linked list has an advantage over the no-header version in that every node participating in the actual list has a node before it, making the access more uniform.

Add a node at a position

The key to understanding linking operations is to draw diagrams which depict the statements to be executed. Adding a node at a specific position, pos, requires that we have access to the node at position pos-1. Here is the intended operation:
pos = 2;
add(pos, 63);
Here is how you would depict it:
The operations to achieve this are as follows:
pos = 2;
 
Node<T> n = /* the node at position (pos-1) */;
 
Node<T> newNode = new Node<>(63,null);   // A
newNode.next = n.next;                   // B
n.next = newNode;                        // C
++size;
Step (C) must be done before (B) because it breaks the original link.

For addition, the position, pos, ranges between 0 and size where size counts the number of nodes omitting the header node. The node n points to the node at position pos - 1. We can add a node at all size+1 positions.

Remove at an arbitrary position

The positional remove operation is quite simple. Consider this depiction in which we want to remove the node at position 2. The generic operation should be like this:
T removed = remove(2)
As with add, we need to have access to the node at the position before:
The idea is to route around the node we want removed; the rerouting line is this:
n.next = n.next.next;
The actual code must capture the item to be removed and return it.
  @Override
  public T remove(int pos) {
    if (size == 0) {
      throw new java.util.NoSuchElementException();
    }
    // move node n to point to the node at pos-1
    T item = n.next.item;
    n.next = n.next.next;
    --size;
    return item;
  }

Exercises

Write these functions in simple ways without helper functions and without using the size member:
addFirst
toString
getFirst
removeFirst -- use getFirst
size
getLast
addLast 
indexOf     -- without or with nulls
contains    -- use indexOf
The dedicated package, samples, has the following 2 starter classes. Proceed by un-commenting lines in main of Driver and writing the corresponding member functions in the SingleLinkedList class.

samples.SingleLinkedList
package samples;
 
public class SingleLinkedList<T> {
  private static class Node<T> {
    T item;
    Node<T> next;
 
    Node(T item, Node<T> next) {
      this.item = item;
      this.next = next;
    }
  }
 
  private final Node<T> first;
 
  public SingleLinkedList() {
    first = new Node<>(null, null); 
  }
}
select

samples.Driver
package samples;
 
public class Driver {
 
  public static void main(String[] args) {
    SingleLinkedList<String> list = new SingleLinkedList<>();
 
    System.out.println(list);
 
/*
    list.addFirst("AA");
    list.addFirst("BB");
    list.addFirst("CC");
 
    System.out.println(list);
 
    String first = list.getFirst();
 
    System.out.println("first = " + first);
 
    String removed = list.removeFirst();
 
    System.out.println("removed: " + removed);
 
    System.out.println(list);
 
    System.out.println(list.size());
 
    String last = list.getLast();
 
    System.out.println("last = " + last);
 
    list.addLast("XXX");
 
    System.out.println(list);
 
    String search;
    int found_at;
 
    search = "AA";
    found_at = list.indexOf(search);
    System.out.printf("indexOf(%s) = %s\n", search, found_at);
 
    search = "AAA";
    found_at = list.indexOf(search);
    System.out.printf("indexOf(%s) = %s\n", search, found_at);
 
    // allowing nulls
    list.addFirst(null);
    list.addFirst("YYY");
    list.addLast(null);
 
    System.out.println(list);
 
    search = "AA";
    found_at = list.indexOf(search);
    System.out.printf("indexOf(%s) = %s\n", search, found_at);
 
    search = null;
    found_at = list.indexOf(search);
    System.out.printf("indexOf(%s) = %s\n", search, found_at);
 
    search = "XXX";
    System.out.printf("contains(%s) = %s\n", search, list.contains(search));
 
    search = "CC";
    System.out.printf("contains(%s) = %s\n", search, list.contains(search));
 
*/
  }
}
select

Solutions

  @Override
  public String toString() {
    Node<T> n = first.next;
    String output = "";
    while (n != null) {
      // we want to avoid using n.item.toString() 
      // because n.item could be null
      output += "" + n.item + " ";
      n = n.next;
    }
    return output;
  }
 
  public void addFirst(T item) {
    Node<T> node = new Node<>(item, null);
    node.next = first.next;
    first.next = node;
  }
 
  public T getFirst() {
    if (first.next == null) {
      throw new RuntimeException("no such element");
    }
    return first.next.item;
  }
 
  public T removeFirst() {
    T item = this.getFirst();
    first.next = first.next.next;
    return item;
  }
 
  public int size() {
    Node<T> n = first.next;
    int count = 0;
    while (n != null) {
      n = n.next;
      ++count;
    }
    return count;
  }
 
  public T getLast() {
    if (first.next == null) {
      throw new RuntimeException("no such element");
    }
    Node<T> n = first.next; // or just "n = first"
    while (n.next != null) {
      n = n.next;
    }
    return n.item;
  }
 
  // What I came up with in class wasn't quite correct, 
  // because we want to allow addLast to an empty list.
  // Here is the correct version:
  public void addLast(T item) {
 
    Node<T> n = first; // not "n = first.next"
 
    while (n.next != null) {
      n = n.next;
    }
    n.next = new Node<>(item, null);
  }
 
  // ----- no nulls assumption
//  public int indexOf(Object obj) {
//    Node<T> n = first.next;
//    int pos = 0;
//    while (n != null) {
//      if (obj.equals(n.item)) {
//        return pos;
//      }
//      n = n.next;
//      ++pos;
//    }
//    return -1;
//  }  
 
  public int indexOf(Object obj) {
    Node<T> n = first.next;
    int pos = 0;
 
    if (obj != null) {
      while (n != null) {
        if (obj.equals(n.item)) {
          return pos;
        }
        n = n.next;
        ++pos;
      }
    }
    else { // obj == null
      while (n != null) {
        if (n.item == null) {
          return pos;
        }
        n = n.next;
        ++pos;
      }
    }
 
    return -1;
  }
 
  public boolean contains(Object obj) {
    return this.indexOf(obj) >= 0;
  }

Singly-linked list class and Driver

This version of the singly-linked list is in the mylinkedlist package. It maintains the size member, making operations both more efficient and somewhat simpler.

mylinkedlist.SingleLinkList
package mylinkedlist;
 
import java.util.Arrays;
 
public class SingleLinkList<T> {
  private static class Node<T> {
    T item;
    Node<T> next;
 
    Node(T item, Node<T> next) {
      this.item = item;
      this.next = next;
    }
  }
 
  private final Node<T> first;
  private int size = 0;
 
  public SingleLinkList() {
    first = new Node<>(null, null); // header node, item ignored
  }
 
  /**
   * @param pos: -1 to size-1 (-1 = header position)
   * @return the node at that position
   */
  private Node<T> moveToPosition(int pos) {
    Node<T> n = first;
    for (int i = 0; i <= pos; ++i) {
      n = n.next;
    }
    return n;
  }
 
  public void add(int pos, T elt) {
    if (pos < 0 || pos > size) {
      throw new IndexOutOfBoundsException(pos + " is out of bounds");
    }
    Node<T> n = moveToPosition(pos-1);
    Node<T> newNode = new Node<>(elt, null);
    newNode.next = n.next;
    n.next = newNode;
    size++;
  }
 
  public void addFirst(T elt) {
    add(0, elt);
  }
 
  public void addLast(T elt) {
    add(size, elt);
  }
 
  public boolean add(T elt) {
    addLast(elt);
    return true;
  }
 
  public T removeFirst() {
    if (size == 0) {
      throw new java.util.NoSuchElementException();
    }
    Node<T> n = first.next;
    T item = n.item;
    first.next = n.next;
    --size;
    return item;
  }
 
  public T get(int pos) {
    if (pos < 0 || pos > size-1) {
      throw new IndexOutOfBoundsException(pos + " is out of bounds");
    }
    Node<T> n = moveToPosition(pos);
    return n.item;
  }
 
  public T set(int pos, T elt) {
    if (pos < 0 || pos > size-1) {
      throw new IndexOutOfBoundsException(pos + " is out of bounds");
    }
    Node<T> n = moveToPosition(pos);
    T prev = n.item;
    n.item = elt;
    return prev;
  }
 
  public Object[] toArray() {
    Object data[] = new Object[size];
    Node<T> n = first.next;  // first real node (or null)
    int i = 0;
    while (n != null) {
      data[i++] = n.item;
      n = n.next;
    }
    return data;
  }
 
  @Override
  public String toString() {
    return Arrays.toString(this.toArray());
  }
}
A key helper function for the add(int,T) operation is the one which obtain the node at an arbitrary position:
  /**
   * @param pos: -1 to size-1 (-1 = header position)
   * @return the node at that position
   */
  private Node<T> moveToPosition(int pos) {
    Node<T> n = first;
    for (int i = 0; i <= pos; ++i) {
      n = n.next;
    }
    return n;
  }
As noted in the docs, we want to be able to position n anywhere within the structure, including the header node. In particular if pos = -1, then the loop correctly does not do any steps.

The positional add function uses it in the way we have indicated:
  public void add(int pos, T elt) {
    ...
    Node<T> n = moveToPosition(pos-1);
    ...
  }

Driver Program

This driver program, also in the mylinkedlist package will serve to illustrate behaviors both for the singly-linked list that we have discussed as well as the doubly-linked list that we will discuss below.

mylinkedlist.Driver
package mylinkedlist;
 
public class Driver {
 
  public static void main(String[] args) {
    SingleLinkList<String> list = new SingleLinkList<>();
    //DoubleLinkList<String> list = new DoubleLinkList<>();
 
    list.add("Carol");
    list.add("Ted");
    list.add("Alice");
 
    System.out.println("list = " + list);
    System.out.println();
 
    list.add(0, "Jim");
    System.out.println("after list.add(0,\"Jim\"), list = " + list);
 
    list.add(2, "Laura");
    System.out.println("after list.add(2,\"Laura\"), list = " + list);
    System.out.println("");
 
    String str = list.get(3);
    System.out.println("list.get(3) = " + str);
 
    String prev = list.set(3, "Joe");
    System.out.println("list.set(3, \"Joe\") = " + prev);
    System.out.println("list = " + list);
    System.out.println("");
 
    list.addLast("Zorro");
    System.out.println("list.addLast(\"Zorro\")");
    System.out.println("list = " + list);
    System.out.println("");
 
    String first = list.removeFirst();
    System.out.println("list.removeFirst() = " + first);
    System.out.println("list = " + list);    
    System.out.println("");
 
  } 
}

Comparison with ArrayList

As you can see, linked lists have no issue with expanding their size. They also provide efficient add/remove from the first positiion, in constrast to an ArrayList which must shift the elements one way or the other.

The down side of linked lists is the overhead of positional access, i.e. you have to crawl through the pointer chains to get to the right position. For this reason the Java LinkedList does not implement the RandomAccess interface.

Exercises

Using the SingleLinkList and Driver classes from the mylinkedlist package,
  1. Write and test the positional remove function:
    T remove(int pos)
  2. Use the indexOf and the positional remove methods to write Object remove method:
    boolean remove(Object obj)
Do the testing by adding statements into the mylinkedlist.Driver class.

Solutions

  public T remove(int pos) {
    if (pos < 0 || pos >= size) {
      throw new IndexOutOfBoundsException(pos + " is out of bounds");
    }
    Node<T> n = moveToPosition(pos-1);
    T saved = n.next.item;
    n.next = n.next.next;
    size--;
    return saved;
  }
 
  /**
   This implementation of remove(Object) is, of course, inefficient 
   in a linked list because we have to crawl up the list twice if 
   we actually remove the object.
 
   Doing the removal in one pass up the list is tricky, because
   we have to keep track of the position before where obj is found.
  */
 
  public boolean remove(Object obj) {
    int pos = indexOf(obj);
    if (pos >= 0) {
      remove(pos);
      return true;
    }
    return false;
  }

Doubly-linked Lists

The problem with singly-linked lists is that it treats access to first different than access to last. Java really wants to use a structure which treats these operations symmetrically:
getFirst, getLast 
addFirst, addLast 
removeFirst, removeLast
indexOf, lastIndexOf
The way to achieve this end is to Here is the Node class we'll use:
  private static class Node<T> {
    T item;
    Node<T> next;
    Node<T> prev;
 
    Node(Node<T> prev, T elt, Node<T> next) {
      this.prev = prev;
      this.item = elt;
      this.next = next;
    }
  }
Here is a list depiction of the list [33,19,25]:
As you can see, the list is completely symmetric with respect to going up by next or going down by prev. The issue now becomes the extra complexity of managing two pointers. Here is the depiction of an empty doubly-linked list:

Adding at a position

The logic is the same as with singly-linked lists, but you have the extra complexity of managing the prev link. Here is a depiction of the add operation:
pos = 2;
add(pos, 19);
Because of the symmetry, we could move n either before (as we have done here) or at the insertion position, which would seen as after the insertion when completed.
It makes it easier to write this if you identify and use this auxiliary Node variable:
Node<T> n1 = n.next;
With this in place we have:
newNode = new Node<>(null,elt,null);  // A
newNode.prev = n;    // B
newNode.next = n1;   // C
n1.prev = newNode;   // D
n.next = newNode;    // E

Doubly-linked list class

Here is the doubly-linked class. You can test it using the same Driver program above. Simply switch the comments on initial statements from
    SingleLinkList<String> list = new SingleLinkList<>();
to
    DoubleLinkList<String> list = new DoubleLinkList<>();
Some points about the code are these:

mylinkedlist.DoubleLinkList
package mylinkedlist;
 
import java.util.Arrays;
 
public class DoubleLinkList<T>  {
  private static class Node<T> {
    T item;
    Node<T> next;
    Node<T> prev;
 
    Node(Node<T> prev, T elt, Node<T> next) {
      this.prev = prev;
      this.item = elt;
      this.next = next;
    }
  }
 
  private final Node<T> first;
  private final Node<T> last;
  private int size = 0;
 
  public DoubleLinkList() {
    first = new Node<>(null, null, null); // header node, item ignored
    last = new Node<>(null, null, null);  // footer node, item ignored
    first.next = last;
    last.prev = first;
  }
 
  /**
   * @param pos: -1 to size-1 (-1 = header position)
   * @return 
   */
  private Node<T> moveUpToPosition(int pos) {
    Node<T> n = first;
    for (int i = 0; i <= pos; ++i) {
      n = n.next;
    }
    return n;
  }
 
  public void add(int pos, T elt) {
    if (pos < 0 || pos > size) {
      throw new IndexOutOfBoundsException(pos + " is out of bounds");
    }
    Node<T> n = moveUpToPosition(pos-1);
    Node<T> newNode = new Node<>(null, elt, null);
    newNode.prev = n;
    newNode.next = n.next;
    n.next.prev = newNode;
    n.next = newNode;
    size++;
  }
 
  public void addFirst(T elt) {
    add(0, elt);
  }
 
  public void addLast(T elt) {
    Node<T> n = last.prev;
    Node<T> newNode = new Node<>(null, elt, null);
    newNode.prev = n;
    newNode.next = n.next;
    n.next.prev = newNode;
    n.next = newNode;
    size++;
  }
 
  public boolean add(T elt) {
    addLast(elt);
    return true;
  }
 
  public T removeFirst() {
    if (size == 0) {
      throw new java.util.NoSuchElementException();
    }
    Node<T> n = first.next;
    T item = n.item;
    n.next.prev = first;
    first.next = n.next;
    --size;
    return item;
  }
 
  public T removeLast() {
    if (size == 0) {
      throw new java.util.NoSuchElementException();
    }
    Node<T> n = last.prev;
    T item = n.item;
    n.prev.next = last;
    last.prev = n.prev;
    --size;
    return item;
  }
 
  public T get(int pos) {
    if (pos < 0 || pos > size-1) {
      throw new IndexOutOfBoundsException(pos + " is out of bounds");
    }
    Node<T> n = moveUpToPosition(pos);
    return n.item;
  }
 
  public T set(int pos, T elt) {
    if (pos < 0 || pos > size-1) {
      throw new IndexOutOfBoundsException(pos + " is out of bounds");
    }
    Node<T> n = moveUpToPosition(pos);
    T prev = n.item;
    n.item = elt;
    return prev;
  }
 
  public Object[] toArray() {
    Object data[] = new Object[size];
    Node<T> n = first;
    for (int i = 0; i < size; ++i) {
      n = n.next;
      data[i] = n.item;
    }
    return data;
  }
 
  @Override
  public String toString() {
    return Arrays.toString(this.toArray());
  }
}

Exercise

The positional add, as well as the get and set members use the private moveUpToPosition member. The intention is to make explicit the fact that we move "up" the node chain from first through next pointers. Symmetrically, we could write a moveDownToPosition member which goes "down" the node chain from last through prev pointers.

How could you use both to make the positional operations more efficient than what they are now?


© Robert M. Kline