The (Unsorted) List ADT

Comparing Objects-- Revisited

Many list operations require us to compare the values of objects. Examples include

• check whether a given item is on our to-do list
• insert a name into a list in alphabetical order
• delete the entry with the matching serial number from a parts inventory list

We need an equality test (==)and relational tests (<, >, <=, >=)

Recall the equality comparison (==) operator checks if the variable contents are equal.   If the variables are references to objects, are they pointing to the same object?  e.g. are the addresses equal?

Using the equals method

Since equals(), a boolean method, is exported from the Object class it can be used with objects of any Java class. For example, If c1 and c2 are objects of the class Circle, then we can compare them using c1.equals(c2)

As defined in the Object superclass, equals acts much the same as the comparison operator. By default, it returns true if and only if the two variables reference the same object.  However, we can redefine (override) the equals method to fit the goals of the class.

A reasonable definition for equality of Circle objects is that they are equal if they have equal radii. We could alternatively define it according to position, or both.

To realize this equal radii approach we define the equals method of our Circle class to use the radius attribute:

 public boolean equals(Circle circle)
   // Precondition: circle != null
   // 
   // Returns true if the circles have the same radius,
   // otherwise returns false.
{
   return (this.radius == circle.radius);
}

Ordering objects

To support a sorted list we need to be able to tell when one object is less than, equal to, or greater than another object.

The Java library provides an interface, called Comparable, which can be used to ensure that a class provides this functionality.

The Comparable Interface consists of exactly one abstract method:

 public int compareTo(Object o);
   // Returns a negative integer, zero, or a positive 
   // integer as this object is less than, equal to, 
   // or greater than the specified object.

The compareTo method returns an integer value that indicates the relative "size" relationship between the object upon which the method is invoked and the object passed to the method as an argument.

• a.compareTo(b) returns a negative value if a<b
• returns 0 is a==b
• return a postive value if a>b
• the actual negative or positive values are typically unimportant.  -1 and 1 are often used.

Objects of a class that implements the Comparable interface are called Comparable objects.

To ensure that all elements placed on our sorted list support the compareTo operation, we require them to be Comparable objects.

A compareTo Example

  public int compareTo(Object o)
  // Precondition: o != null
  //
  // Returns a negative integer, zero, or a positive integer as this object 
  // is less than, equal to, or greater than the parameter object.
  {
    if (this.radius < ((Circle)o).radius)
      return -1;
    else if (this.radius == ((Circle)o).radius)
      return 0;
    else
      return 1;
  }

Note that the equals method and the compareTo method of our Circle class are compatible with each other.

To simplify discussion we sometimes refer to the attribute, or combination of attributes, of an object used by the compareTo method to determine the logical order of a collection as the key of the collection.

General List Definitions

Linear relationship: Each element except the first has a unique predecessor, and each element except the last has a unique successor.

Length or Size: The number of items in a list; the length can vary over time.

Unsorted list: A list in which data items are placed in no particular order; the only relationship between data elements is the list predecessor and successor relationships.

Sorted list: A list that is sorted by the value in the key; there is a semantic relationship among the keys of the items in the list. Unless otherwise stated we'll assume ascending

Indexed list: A list in which each element has an index value associated with it

Key The attribute(s) that is(are) used to determine the logical order of the list. A key is a subset of attributes that uniquely determine the element of the collection.

Formal Specification

Assumptions for our Lists

• Lists are unbounded
• Duplicate elements are allowed on our lists
• Null elements are not supported
• Other than prohibiting null elements, we have minimal preconditions on our operations
• Our sorted lists are sorted in increasing order, as defined by the compareTo operation applied to list objects
• The equals and compareTo methods of our sorted list elements are consistent (they compare the same attributes)
• In our indexed lists, the indices in use at any given time are contiguous, starting at 0.

Define a small, complete, but useful, set of operations for use with our lists.

Capture the formal specifications of our List ADT using a hierarchy of the Java interface construct. All the common list method descriptions are together into a single interface, called ListInterface.

We extend the ListInterface with three separate interfaces, one for each of our list variations.

The intent is that classes should implement one of these latter three interfaces, and therefore by extension, implement the ListInterface.

List Operations

All three of our list variations provide the following operations:

boolean contains(Object): Passed an Object argument and returns a boolean indicating whether the list contains an equivalent element.

boolean remove(Object): Passed an Object argument and, if an equivalent element exists on the list, removes one instance of that element. Returns a boolean value indicating whether an object was actually removed.

Object get(Object): Passed an Object argument, it returns an equivalent object if one exists on the list. If not, returns null.

String toString(): Returns a nicely formatted string representing the list.

void reset(): Initializes the list for iteration. Sets the current position (the position of the next element to be processed) to the first element on the list.

Object getNext(): Returns the next element, and updates the current position.

List Iteration

• Because a list has a linear relationship among its elements, we can support iteration through a list.
• Iteration means that we provide a mechanism to process the entire list, element by element, from the first element to the last element.
• Each of our list variations provides the operations reset and getNext to support this activity.

List Operations

The Unsorted List also supports the operation

• add(Object): Passed an Object argument that it adds to the list

The Sorted List also supports the operation

• add(Comparable): Passed a Comparable argument that it adds to the list

The Indexed List also supports the operations

• void add(Object,int): Passed an Object element and an integer index it adds the element to the list at the position index
• Object set(Object,int): Passed an Object element and an integer index it replaces the current element at the position index with the argument element
• Object get(int): Passed an integer index it returns the element from the list at that position
• int indexOf(Object): Passed an Object element it returns the index of the first such matching element (or -1)
• Object remove(int): Passed an integer index it removes the element at that index

Each method that accepts an index as an argument throws an exception if the index is invalid.

Examples Uses

Implementation of the Unsorted Array List ADT:

The List interface (ListInterface.java)

The Unsorted List interface (UnsortedListInterface.java)

The List class (List.java)

The Array Unsorted List class (ArrayUnsortedList.java)

Implementation of the Sorted Array List ADT

The Sorted List interface (SortedListInterface.java)

The Array Sorted List class (ArraySortedList.java)

Implementation of the Array Indexed List ADT

The Indexed List interface (IndexedListInterface.java)

The Array Indexed list class (ArrayIndexed.List.java)