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 random access accessing an element (get/set) at an index is O(1) 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 the Queue and Deque interfaces in addition to the List interface. All of these interface/implementation declarations are useful in practical situations:
Deque<E> L = new LinkedList<>();
Queue<E> L = new LinkedList<>();
List<E> L  = new LinkedList<>();
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 getLast(), peekLast()
get first element getFirst(), element(), peek(), peekFirst()
The main difference between the "remove_" and "get_" operations 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.

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.

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 addFirst and removeFirst functions

Add to first is very simply this:
public void addFirst(E elt) {
  first = new Node<>(elt, first);
}
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 member function implementations

You can use the SingleLList class to write your own member function implementations for better understanding of how to use Nodes. For example, the size function is currently undefined. A starter main class has already been created:

demo.SingleLListTesting
package demo;
 
import util.SingleLList;
 
public class SingleLListTesting {
 
  public static void main(String[] args) {
    SingleLList<String> strings = new SingleLList<>();
    SingleLList<Integer> ints = new SingleLList<>();
  }
}
To write and test your own function, edit both util.SingleLList and this program.

print

Start with the iterative version of a member function print, which prints a list, one element per line. Give yourself something to work with:

demo.SingleLListTesting
  public static void main(String[] args) {
    SingleLList<String> strings = new SingleLList<>();
    SingleLList<Integer> ints = new SingleLList<>();
 
    ints.addFirst(22);
    ints.addFirst(33);
    ints.addFirst(44);
    ints.addFirst(55);
 
    ints.print();
  }
Then edit util.SingleLList and add the print member function anywhere within this class.

util.SingleLList
...
public class SingleLList<E> extends LListAdapter<E> {
  ...
  public void print() {
    Node<E> n = first;
    while (n != null) {
      System.out.println(n.data);
      n = n.next;
    }
  }
  ...
}
The recursive version of this function requires a recursive helper function.
  public void print() {
    print(first);
  }
 
  private void print(Node<E> n) {
    if (n == null) {
      return;
    }
    System.out.println(n.data);
    print(n.next);
  }

size

You'll want to use a call within the main function of demos.SingleLListTesting:
  System.out.println(ints.size());
Here are the iterative and recursive solutions of the size function.

size: iterative
  public int size() {
    Node<E> n = first;
    int count = 0;
    while (n != null) {
      ++count;
      n = n.next;
    }
    return count;
  }

size: recursive
  public int size() {
    return size(first);
  }
 
  private int size(Node<E> n) {
    if (n == null) {
      return 0;
    }
    return 1 + size(n.next);
  }

Doubly-linked List

A realistic linked-list implementation must be doubly-linked in the manner indicated above.
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<>(elt, n.prev, 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