Week 5: Ordered Lists

This week, we’ll get some more practice with lists. I’d like you to implement a class OrderedList<E>, which has a slightly unconventional interface:

public class OrderedList<E extends Comparable<E>> implements Iterable<E> {
    public OrderedList();

    public boolean isEmpty();
    public int size();

    public E get(int index);
    
    public Iterator<E> iterator();
    
    public int insert(E data);
}

An OrderedList keeps its elements sorted ascending. The only way to add an element is through the insert method, which takes the element and finds the correct place in the list. For example, the following code:

public static void main(String[] args) {
    OrderedList<String> l = new OrderedList<>();
    l.insert("c");
    l.insert("a");
    l.insert("b");

    for (String s : l) {
      System.out.println(s);
    }
  }

Produces the output:

a
b
c

That is, the elements of the list have been sorted ‘ascending’.

It’s up to you to decide what kind of list you want to build: should it be an array list, a singly-linked list, or a doubly-linked list?

Nothing Compares to You

You’ll notice that the type parameter in the declaration of our class has a constrain on it: we say OrderedList<E extends Comparable<E>>… what a mouthful! Unlike Python, Java makes it pretty complicated to compare values that aren’t integers.

The type Comparable<T> means “something that can be compared to something of type T. There’s a single method, int compareTo(T o). Here’s how the javadocs describe it:

Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

It’s a little confusing at first! The general idea is that (i) a.compareTo(b) returns a signed number (an int) and (ii) the sign of the number tells you how a relates to b. Concretely:

• a.compareTo(b) < 0 means a is less than b
• a.compareTo(b) == 0 means a is equal to b
• a.compareTo(b) > 0 means a is greater than b

Inserting in order

How should you insert an element e into an already ordered list? The general approach is:

• walk down the list until you find another element, f, such that f.compareTo(e) >= 0 (i.e., f is greater than or equal to e)
• insert e right before f

You’ll need some special-casing to handle updates when there are 0 or 1 elements in the list.

Good luck!