Linked Lists

The ListDeque Application

The examples in this, the previous, and the next document all part of the Java Application ListDeque. Download the source archive ListDeque.zip and install it as a Java Application with Existing Sources. See the Using NetBeans document for details.

Like others, the ListDeque project has multiple Main Classes intended to illustrate various independent features. The simplest way to run the various classes is to right-click the file and select Run File either in the file itself or from the listing in the Projects window.

Description

The goals and methods for creating user-defined Linked Lists are similar to those described in the Array Lists document. We will create a LListAdapter class from which we can derive our implementation classes. We are interested in linked lists created both from singly-linked (forward-only) node structures as well as doubly-linked node structures.

Comparison of LinkedList/ArrayList

The linking structure of linked lists creates different behavior from array lists, here are the key difference:
  ArrayList LinkedList
get/set access accessing an element (get/set) at an index is O(1); for this reason the ArrayList implements the RandomAccess interface accessing an element (get/set) at an index is O(n) because we must proceed through a sequence of node pointers to get to the correct position.
add/remove at first and last positions add at the last position is O(1) in general; an additional O(n) cost is incurred when the array's capacity is increase; if the capacity is maintained efficiently, the overall average cost is still O(1)

remove at the last position is always O(1)

add/remove at the first position is always O(n) because the entire array is shifted
add/remove at the first or last positions is O(1) (with doubly-linked lists)
add/remove at arbitrary position add/remove at arbitrary position is O(n) due to shifting add/remove at arbitrary position is O(n) due to sequencing through pointers
space usage wasted space varies according to the number of unused array positions; in order to keep average add time efficient, O(n) wasted space must be created at capacity increases the links are "wasted" by virtue of not holding data; thus there is always O(n) wasted space
In general terms, an ArrayList is a better choice when we're interested in "random positional" access of elements whereas a LinkedList is better suited for end-based access.

Member functions

The LinkedList implements these interfaces (and others): All of these methods are useful in practical situations, and so we most often declare one of these:
List<E> L  = new LinkedList<>();
Deque<E> L = new LinkedList<>();
Queue<E> L = new LinkedList<>();
Of course, we can also use the more obvious declaration:
LinkedList<E> L = new LinkedList<>();
which would give us access to all the relevant operations, but in practice one tends to focus on one the Queue, Deque, or List interface operations exclusively.

The Queue and Deque interfaces offer a bewildering array of choices of member functions, as described in the Java Data Structures (java.util) document. Here is a table of operation descriptions focusing on the non-index based operations. Keep in mind that first and last signify the leftmost and rightmost elements, respectively.
description versions
add to last void addLast(e), boolean add(e), boolean offerLast(e)
add to first void addFirst(e), boolean push(e), boolean offer(e), boolean offerFirst(e)
remove last element E removeLast(), E pollLast()
remove first element E removeFirst(), E remove(), E pop(), E poll(), E pollFirst()
get last element E getLast(), E peekLast()
get first element E getFirst(), E element(), E peek(), E peekFirst()
The main difference between the "remove_" and "get_" methods versus the "poll_" and "peek_" operations is that for the former ones, an exception is thrown if the list is empty, whereas for the latter, a null is returned.

Demo Programs

Start by observing and running the main classes demo.LListDemo1.
demo.LListDemo1  
and
demo.LListDemo2  

Linked List Types

Singly Linked

A singly-linked list represents a minimalistic linked representation. The entire list is accessed by the first pointer. A single next element within each node moves forward in the list and all nodes contain list element data. The list is null-terminated. The empty list is simply the null pointer. A list created in this way is recursive, and functions which act on it are well suited to using recursion.

 singly-linked, without header 
(8,4,9):
Empty List:

An alternative structure uses an always-present "dummy" node which first points to. The data in the dummy node is null and is ignored. The list is null-terminated. The empty list points to the dummy node which has next == null.

 singly-linked, with header 
(8,4,9):
Empty List:

Doubly Linked

A doubly linked list is accessed by first and last pointers. Going forward and backwards are treated symmetrically via node pointers next (forward) and prev (backward).

The first and last pointer always point to the respective dummy nodes at the beginning and end, respectively. Using this structure, insertions are treated equally, regardless of the position; the same is true of deletions.

 doubly-linked, with header/footer 
(8,4,9):
Empty List:

Singly-linked List Implementation

Our LListAdapter provides vacuous definitions for all the functions satisfied by LinkedList. The functions are all "unimplemented" in the sense that their only code is to throw an UnsupportedOperationException. Both of our user-defined versions will be extensions of LListAdapter. The Serializable implementation is listed, but the implementations we give are, in reality, not serializable, since they are based on Java memory references.
adapter.LListAdapter  
Our first stab at an implementation uses a singly-linked list. Both the with-header and without-header have advantages and disadvantages.

We'll implement a without-header version.
util.SingleLList  
This is the most bare-bones implementation based on this inner class:
private static class Node<E> {
  E data;
  Node<E> next;
 
  Node(E data, Node<E> next) {
    this.data = data;
    this.next = next;
  }
}
What is provided is the only really required data member:
private Node<E> first = null;
If we want to make the size() member function more efficient, an int size data member should also be maintained. A Node last data member could be added to make the addLast operation more efficient, but it would offer no support for the removeLast operation, since we cannot easily "back up" from the end. Furthermore, a last data member actually detracts from the simplicity of the class member functions.

Testing

Replace LinkedList by SingleLList in LListDemo1, changing the definition of L:
//    Deque<String> L = new LinkedList<>();
    Deque<String> L = new SingleLList<>();
Doing the same thing in LListDemo2 will fail, because it uses (currently) undefined operations.

The first access functions

Add to first is this:
public void addFirst(E elt) {
  first = new Node<>(elt, first);
}
This is effectively 3 steps in one. The getFirst function is:
public E getFirst() {
  if (first == null){
    throw new NoSuchElementException();
  }
  return first.data;
}
and the remove operation is this:
public E removeFirst() {
  if (first == null){
    throw new NoSuchElementException();
  }
  E data = first.data;
  first = first.next;
  return data;
}

Write your own method implementations

Use the examples package to write your own implementations and test them. Start with a barebones version of the Singly-linked list with no header node:

examples.SingleLList
package examples;
 
public class SingleLList<E>  {
 
  private static class Node<E> {
    E data;
    Node<E> next;
 
    Node(E data, Node<E> next) {
      this.data = data;
      this.next = next;
    }
  }
 
  // only a first node, with no size data member
 
  private Node<E> first = null;
 
  // implemented methods
 
  public void addFirst(E elt) {
    first = new Node<>(elt, first);
  }
 
}
Here is a starter main class:

examples.SingleLListTesting
package examples;
 
public class SingleLListTesting {
 
  public static void main(String[] args) {
    SingleLList<Integer> ints = new SingleLList<>();
 
    ints.addFirst(44);
    ints.addFirst(33);
    ints.addFirst(55);
    ints.addFirst(22);
    ints.addFirst(77);
  }
}
From this point, write additional methods in the SingleLList class (whether they are List interface methods or not), and test them by writing method calls in the SingleLListTesting main class. For example, if you write the print method, then add the following line to the main method:

demo.SingleLListTesting
  ints.print();

The Recursive Version

The iterative implementations we write iterate through some portion of the node chain. When you write a recursive version of a method, the node iteration is replaced by function calls to a helper function which has an additional Node parameter like this:
public myMethod(Type1 arg1, Type2 arg2, ...) {
  ...
  myMethod(first, arg1, arg2, ...);
  ...
}
 
private myMethod(Node<E> n, Type1 arg1, Type2 arg2, ...) {
  ...
}
You can overload the method name since the type signature will differ. The helper function must be private, since it should only ever be referenced internally, usually from the public version.

print

// iterative
public void print() {
  Node<E> n = first;
  while (n != null) {
    System.out.println(n.data);
    n = n.next;
  }
}
// recursive
public void print() {
  print(first);
}
private void print(Node<E> n) {
  if (n == null) {
    return;
  }
  System.out.println(n.data);
  print(n.next);
}

Note that you can easily print the list in reverse by switching the order of the last 2 statements, which illustrates a certain advantage of recursion over iteration.

size

Test in main class with:
  ints.print();
  System.out.println(ints.size());
// iterative
public int size() {
  Node<E> n = first;
  int count = 0;
  while (n != null) {
    ++count;
    n = n.next;
  }
  return count;
}
// recursive
public int size() {
  return size(first);
}
private int size(Node<E> n) {
  if (n == null) {
    return 0;
  }
  return 1 + size(n.next);
}

contains

Assume no nulls used.

Test in the main class with:
  ints.print();
  System.out.println(ints.contains(55));
  System.out.println(ints.contains(56));
// iterative
public boolean contains(Object obj) {
  Node<E> n = first;
  while(n != null) {
    if (obj.equals(n.data)) {
      return true;
    }
    n = n.next;
  }
  return false;
}
// recursive
public boolean contains(Object obj) {
  return contains(first, obj);
}
private boolean 
        contains(Node<E> n, Object obj) {
  if (n == null) {
    return false;
  }
  if (obj.equals(n.data)) {
    return true;
  }
  return contains(n.next, obj);
}

getLast

Test in the main class with:
  ints.print();
  System.out.println(ints.getLast());
// iterative
public E getLast() {
  if (first == null) {
    throw new NoSuchElementException();
  }
  Node<E> n = first;
  while (n.next != null) {
    n = n.next;
  }
  return n.data;
}
// recursive
public E getLast() {
  if (first == null) {
    throw new NoSuchElementException();
  }
  return getLast(first);
}
private E getLast(Node<E> n) {
  if (n.next == null) {
    return n.data;
  }
  return getLast(n.next);
}

addLast

Test in the main class with:
  ints.print();
  System.out.println("---------------");
  ints.addLast(99);
  ints.print();
// iterative
public void addLast(E elt) {
  if (first == null) {
    first = new Node<>(elt, null);
  }
  else {
    Node<E> n = first;
    while (n.next != null) {
      n = n.next;
    }
    n.next = new Node<>(elt, null);
  }
}
// recursive: version 1
public void addLast(E elt) {
  if (first == null) {
    first = new Node<>(elt, null);
  }
  else {
    addLast(first, elt);
  }
}
private void addLast(Node<E> n, E elt) {
  if (n.next == null) {
    n.next = new Node<>(elt, null);
  }
  else {
    addLast(n.next, elt);
  }
}

  // recursive: version 2
  public void addLast(E elt) {
    first = addLast(first, elt);
  }
  private Node<E> addLast(Node<E> n, E elt) {
    if (n == null) {
      return new Node<>(elt, null);
    }
    else {
      n.next = addLast(n.next, elt);
      return n;
    }
  }

contains with nulls allowed

Assume the list can contain nulls, and we can search for null.

Test in the main class with:
  ints.addLast(null);
  ints.print();
  System.out.println("---------------");
  System.out.println(ints.contains(55));
  System.out.println(ints.contains(56));
  System.out.println(ints.contains(null));
  // iterative
  public boolean contains(Object obj) {
    Node<E> n = first;
    if (obj != null) {
      while (n != null) {
        if (obj.equals(n.data)) {
          return true;
        }
        n = n.next;
      }
    }
    else {
      while (n != null) {
        if (n.data == null) {
          return true;
        }
        n = n.next;
      }
    }
    return false;
  }
  // recursive
  public boolean contains(Object obj) {
    if (obj != null)
      return containsNonNull(first, obj);
    else 
      return containsNull(first);
  }
  private boolean containsNonNull(Node<E> n, Object obj) {
    if (n == null) {
      return false;
    }
    if (obj.equals(n.data)) {
      return true;
    }
    return containsNonNull(n.next, obj);
  }
  private boolean containsNull(Node<E> n) {
    if (n == null) {
      return false;
    }
    if (n.data == null) {
      return true;
    }
    return containsNull(n.next); 
  }

removeLast

Test in the main class with:
  ints.print();
  System.out.println("---------------");
  Integer last = ints.removeLast();
  System.out.println("last removed = " + last);
  ints.print();
  // iterative
  public E removeLast() {
    if (first == null) {
      throw new NoSuchElementException();
    }
    if (first.next == null) { // one element
      E last = first.data;
      first = null;
      return last;
    }
    else {
      Node<E> n = first;
      while (n.next.next != null) {
        n = n.next;
      }
      E last = n.next.data;
      n.next = null;
      return last;
    }
  }
  // recursive: version 1
  public E removeLast() {
    if (first == null) {
      throw new NoSuchElementException();
    }
    if (first.next == null) { // one element
      E last = first.data;
      first = null;
      return last;
    }
    else {
      return removeLast(first);
    }
  }
  private E removeLast(Node<E> n) {
    if (n.next.next == null) {
      E last = n.next.data;
      n.next = null;
      return last;
    }
    else {
      return removeLast(n.next);
    }
  }
  // recursive: version 2
  public E removeLast() {
    if (first == null) {
      throw new NoSuchElementException();
    }
    E last = getLast(first);
    first = removeLast(first);
    return last;
  }
  // this is the helper function from getLast
  private E getLast(Node<E> n) {
    if (n.next == null) {
      return n.data;
    }
    return getLast(n.next);
  }
  private Node<E> removeLast(Node<E> n) {
    if (n.next == null) {
      return null;
    }
    n.next = removeLast(n.next);
    return n;
  }

Doubly-linked List

A realistic linked-list implementation must be doubly-linked so as to make going backward symmetric to forward.
util.DoubleLList  

Testing

Replace LinkedList by DoubleLList in LListDemo1 in and LListDemo2, changing the definition of L:
//    Deque<String> L = new LinkedList<>();
    Deque<String> L = new DoubleLList<>();

Description

The doubly-linked used uses an inner class:
private static class Node<E> {
  Node<E> prev;
  E data;
  Node<E> next;
 
  Node(Node<E> prev, E data, Node<E> next) {
    this.prev = prev;
    this.data = data;
    this.next = next;
  }
}
and the data members:
private Node<E> first = null;
private Node<E> last = null;
private int size = 0;
Establishing the initial state looks like this:
private void makeNewList() {
  first = new Node<>(null, null, null);
  last = new Node<>(null, null, null);
  first.next = last;
  last.prev = first;
  size = 0;    
}
 
public DoubleLList() { this.makeNewList(); }
 
@Override
public void clear() { this.makeNewList(); }

Helpers for add/remove operations

Using a doubly linked list with header nodes, all add and remove operations are derivable from these three operations:
// assume n in list, insert at n's position by pushing list towards last
private void addNode(Node<E> n, E elt) {
  Node<E> newNode = new Node<>(n.prev, elt, n);
  n.prev.next = newNode;
  n.prev = newNode;
  ++size;
}
 
// assume n in list, remove at n's position by shifting list down from last
private E removeNode(Node<E> n) {
  E data = n.data;
  n.prev.next = n.next;
  n.next.prev = n.prev;
  --size;
  return data;
}
 
// locate the node at index position by crawling from left to right
private Node<E> nodeAt(int index) {
  if (index > size || index < 0) {
    throw new IndexOutOfBoundsException(
      "Index: " + index + ", " + "Size: " + size);
  }
  Node n = first.next;
  for (int counter = 0; counter < index; ++counter) {
    n = n.next;
  }
  return n;
}

public add/remove operations

These are the add operations:
  @Override
  public void addFirst(E elt) { this.addNode(first.next, elt); }
 
  @Override
  public void addLast(E elt) { this.addNode(last,elt); }
 
  @Override
  public void add(int index, E elt) { this.addNode(nodeAt(index),elt); }
 
  @Override
  public boolean add(E elt) {
    this.addLast(elt);
    return true;
  }
These are the remove operations:
  @Override
  public E removeFirst() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    return this.removeNode(first.next);
  }
 
  @Override
  public E removeLast() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    return this.removeNode(last.prev);
  }
 
  @Override
  public boolean remove(Object obj) {
    Node<E> n = first.next;
    while (n != last) {
      if (n.data.equals(obj)) {
        this.removeNode(n);
        return true;
      }
      n = n.next;
    }
    return false;
  }
 
  @Override
  public E remove(int index) { 
    return this.removeNode( this.nodeAt(index) ); 
  }


© Robert M. Kline