CS111 IntList Contract

The IntList class describes immutable linked lists of integers. An integer list is defined recursively as either

• the empty list, or
• a (non-empty) list node with a head component that is an integer and a tail component that is another integer list.

Integer lists are immutable in the sense that the head or tail of a list node cannot be changed after the list node has been created (via the prepend() method).

There are no public constructor or instance methods for integer lists; they are created and manipulated by the class methods below. By default, an IntList class method is invoked via IntList.methodName(args), but this can be abbreviated to IL.methodName(args) by including the following "magical" declaration in the body of a class:

public static IntList IL; // declare but never initialize this variable.

Class Methods

public static IntList empty()
Returns an empty integer list.

public static IntList prepend (int n, IntList L)
Returns a new integer list node whose head is n and whose tail is L. From another perspective, returns a list whose length is one more than the length of L and whose elements are n followed by the elements of L, in order.

public static boolean isEmpty (IntList L)
Returns true if L is an empty integer list and false if L is an integer list node.

public static int head (IntList L)
Returns the integer that is the head component of the integer list node L. Signals an exception if L is empty.

public static IntList tail (IntList L)
Returns the integer list that is the tail component of the integer list node L. Signals an exception if L is empty.

public static String toString (IntList L)
Returns a string representation of the integer list L in which the integer list elements are separated by commas and delimited by square brackets. For example, if L1 is a list containing the sequence of integers 6, -17 and 42, then toString(L1) returns "[6,-17,42]".

public static IntList fromString (String s)
If s is the printed representation of an integer list (i.e., comma separated integers delimited by square brackets), returns an IntList with that representation. For example, fromString("[7,-2,4]") returns an 3-element integer list with elements 7, -2, and 4. If s is not the printed representation of an integer list, signals an error.