A Class to Hold a Sorted List

Just as with List, the SortedList ADT can be fulfilled in more than one way. One implementation is array-backed. It is essentially the SortedArray we already built in Chapter 3, which keeps its array in order and uses binary search. We will not rewrite it, because we have seen it before. If I were to write it again, I would call it SortedArrayList, following the naming convention we established earlier in this chapter.

The other implementation stores its elements in linked nodes. We will build this one here to further practice with linked lists. We will call it SortedLinkedList.

Start with the shape of the class, its fields, its node type, and its constructor:

public class SortedLinkedList<T extends Comparable<T>> implements SortedList<T> {
  private Node<T> head;  // front sentinel
  private Node<T> tail;  // back sentinel
  private int size;  // number of real nodes

  private static class Node<T> {
    T value;
    Node<T> next;
    Node<T> prev;

    Node(T value) {
      this.value = value;
    }
  }

  public SortedLinkedList() {
    head = new Node<>(null);
    tail = new Node<>(null);
    head.next = tail;
    tail.prev = head;
    size = 0;
  }

  public int size() {
    return size;
  }
}

As with LinkedList, we are using a doubly linked list with sentinels.