CSC236 Data Structures

Lists

A list is a container: it stores a group of objects.
All elements in the list are the same type.
There are many different list ADTs, but they generally fall into three categories:
- Unsorted/unordered lists: these lists are similar to Collections; the order of items in the list doesn't matter.
- Indexed lists: each item has a position, like a subscript. Items can be added and removed based on their position in the list.
- Sorted/ordered lists: the items in the list are kept in order. The add and remove methods make sure that the list is always sorted.
Lists can be implemented with arrays or using links.
List classes provide iteration through the elements in the list.
The list classes presented in our book are an indexed list and a sorted list.
The list classes in our book are unbounded. The array based list has an enlarge method. This method is called if the array is full; it gets a bigger array to hold the list. This was also done in the ArrayQueue class.
The equals method is used to compare the key field and find a matching object in the list.
Duplicate elements are allowed in a list. Elements are considered to be equal if the equals method returns true when comparing the two elements.
Null elements are not supported.

List Interface

The List interface extends the Collection interface. That means that it includes all the Collection methods, so List classes will include these methods. The additional methods required for the list are specified in the List interface. The additional methods are all "indexed" operations: they allow the client code to manipulate the list elements based on their positions. All require that the position be valid.

void add(int index, T element): add an element at the specified position. This means that we will need to add elements in the middle, which we haven't done in any of our previous data structures. Adding in the middle is more complex for both arrays and linked lists.
void remove(int index): remove element at the specified position. Elements that followed will fill the gap, so their position numbers will change. This means that we will need to remove elements in the middle while maintaining the order of the elements.
T set(int index, T newElement): change the element at the specified position.
T get(int index): return a reference to the element at the specified position.
int indexOf(T element): return the first position of the element passed as the parm, if a match is found in the list; if not return -1.

ABList: Array Based List

The fields of the array based list are very similar to the fields of the ArrayCollection. The only difference is the field to hold the original capacity, which is used in the enlarge method:

  protected final int DEFCAP = 100; // default capacity
  protected int origCap;            // original capacity
  protected T[] elements;           // array to hold this list’s elements
  protected int numElements = 0;    // number of elements in this list

List Representation Practice

Suppose we have

ABList<String> myStrings = new ABList();

Draw the list (the fields elements and numElements) after each of the following, and show any return value or output:

myStrings.add("spring");
myStrings.add("bloom");
myStrings.add("red");
myStrings.add(1, "flowers");
myStrings.add("yellow");
myStrings.add(4, "and");
int loc = myStrings.indexOf("yellow");
String str = myStrings.remove(0);
str = myStrings.get(2);

List Implementation Practice

Suppose you have the ABList fields elements and numElements. Assume that loc is a value between 0 and numElements, and element is a value of type T. Write the code to move the items in the array and then insert element into position loc.

Now suppose you have the ABList fields elements and numElements. Assume that loc is a value between 0 and numElements-1. Write the code to remove the item in position loc from the array.

LBList: Linked Based List

The fields of the linked based list are very similar to the fields of the LinkedCollection. Notice that the list has a reference to the last element in the list (like the LinkedQueue). Also the targetIndex field is set by find to the position of the element which is being located.

  protected LLNode<T> front;     // reference to the front of this list
  protected LLNode<T> rear;      // reference to the rear of this list
  protected int numElements = 0;       // number of elements in this list

  // set by find method
  protected boolean found;              // true if target found, else false
  protected int targetIndex;            // list index of target, if found
  protected LLNode<T> location;   // node containing target, if found
  protected LLNode<T> previous;   // node preceding location

List Representation Practice

Suppose we have

LBList<String> myStrings = new LBList();

Draw the list (the fields front, rear, numElements, and the list nodes) after each of the following, and show any return value or output:

myStrings.add("spring");
myStrings.add("bloom");
myStrings.add("red");
myStrings.add(1, "flowers");
myStrings.add("yellow");
myStrings.add(4, "and");
int loc = myStrings.indexOf("yellow");
String str = myStrings.remove(0);
str = myStrings.get(2);

Suppose you have a linked list with numElements items. Given an element of type T and loc which is between 0 and numElements, write the code to add the new element in position loc.

Now suppose you have a linked list with numElements-1 items. Given loc between 0 and numElements, write the code to remove the element in position loc.

Iterators

The List interface also extends Iterable<T>. This is a Java interface used to provide a standard method for iteration (accessing all values in order) through a container. The Iterable interface requires the following method:

    Iterator<T> iterator();

That is, the list must have a method called iterator that returns an Iterator object. What is an Iterator object? It is an object that is "linked" to a collection object; that is, it is able to access the fields of the collection object. Using its methods allows client code to iterate through all of the objects in the collection. It must implement the Iterator interface, which requires the following two methods:

boolean hasNext(): this method returns true if there are more elements to iterate through.
T next(): this method returns the next element in the collection.

Given a collection, such as a list, the following code will go through all elements in the list:

   // mylist is a collection of T objects
   T item;
   listIter = mylist.iterator();
   while (listIter.hasNext()) {
      item = listIter.next();
      // do something to item
   }

And, perhaps even more conveniently, you can use a foreach loop, which uses the iterator for you:

   // mylist is a collection of T objects
   for (T item : mylist) {
      // do something to item
   }

The iterator() method creates and returns an Iterator object. Thus we need a class that defines the iterator for our list class. Then the iterator() method will create an object of this class. This iterator class needs to access the fields of our list so that it can return the elements in the list.

There are three ways to create an iterator: a separate class, an inner class (inside the collection class) and an anonymous inner class (also inside the collection class).

Consider an array based list class called ABList with the following fields:

   protected T[] elements;
   protected int numElements;

The array elements holds the items in the list and numElements has the number of items that are stored in the list. The items in the list are stored in the array starting at location [0] and going up to location [numElements-1].

Iterator in a Separate Class

Here is the iterator defined in a separate class:

public class ABListIterator<T> implements Iterator<T> {
   private ABList<T> theList;   // reference to the list we are iterating over
   private int previousPos = -1;      // last position we have returned in the iteration

   // create the iterator by passing the list to the constructor
   public ABListIterator(ABList<T> target) {
      theList = target;
   }

   public boolean hasNext() {
   // Returns true if the iteration has more elements; otherwise returns false.
   // if previousPos is at the end of the list, we are done
      return (previousPos < (theList.size() - 1)) ;
   }

   public T next() {
   // Returns the next element in the iteration.
   // Throws NoSuchElementException: if the iteration has no more elements
      if (!hasNext())
         throw new IndexOutOfBoundsException("Illegal invocation of next " +
                         " in ABList iterator.\n");
      previousPos++;
      return theList.elements[previousPos];
   }
}

With this class, the iterator() method in the ABList class is:

public Iterator<T> iterator() {
   return new ABListIterator(this);
}

Notice that the iterator() method passes a reference to the list (this) to the constructor of the iterator object. This is how the iterator object has access to the fields of the list.

Iterator in an Inner Class

An inner class is a non-public class that is inside the same file as a public class. One thing that is bad about having the iterator in a separate public class is that the two classes are closely coupled. The iterator is using the fields contained in the list. If those fields are defined as protected (as in our class), then they can be accessed by any class in the same package, or any subclass. But if the fields of the list are changed then the iterator class also needs to be changed. So perhaps it's not the best design.

Instead we can put the iterator class inside the file with the ABList class. The inner class is inside the list class, so as a member of the ABList class it has access to the fields in the ABList class.

Creating an inner class means that there are a couple of changes to our iterator:

Since the inner class has access to the fields in the enclosing class, we don't have to pass the object to the constructor of the iterator.
The inner class inherits the generic parm of the enclosing class, so the inner class doesn't have a generic in the class definition. The generic parm can still be used within the statements of the iterator class, as needed.

Here is an outline of the iterator with an inner class:

public class ABList<T> implements ListInterface<T> {

   // fields and methods of the class

   // the method that returns the Iterator object
   ABListIterator<T> iterator() {
      return new ABListIterator();
   }

   // the class that creates the Iterator
   // note that the class does not have a generic parm; it inherits
   // the generic from the enclosing class
   
   class ABListIterator implements Iterator {

      // the code of the iterator class

   }
   

}

And here is a more complete example:

// ListInterface extends Collection and Iterable
public class ABList<T> implements ListInterface<T> {
   protected final int DEFCAP = 100; // default capacity
   protected int origCap;            // original capacity
   protected T[] elements;           // array to hold this list’s elements
   protected int numElements = 0;    // number of elements in this list

   // the other list methods

   // iterator method that returns an iterator
   Iterator<T> iterator() {
      return new ABListIterator();
   }

   // this is the class that creates the iterator
   // again, no generic parm on the class definition
   
   class ABListIterator implements Iterator {
      private int previousPos = -1;  // last position we have returned in the iteration

      // create the iterator
      public ABListIterator() {  }

      public boolean hasNext() {
      // Returns true if the iteration has more elements; otherwise returns false.
      // if previousPos is at the end of the list, we are done
         return (previousPos < (numElements - 1)) ;
      }

      public T next() {
      // Returns the next element in the iteration.
      // Throws NoSuchElementException - if the iteration has no more elements
         if (!hasNext())
            throw new IndexOutOfBoundsException("Illegal invocation of next " +
                         " in ABList iterator.\n");
         previousPos++;
         return elements[previousPos];
      }
   }  // end of ABListIterator class
   

} // end of ABList class

Iterator in an Anonymous Inner Class

The inner class in the previous example is only referenced in the iterator() method of the ABList class. Thus we can use an anonymous inner class. The anonymous class doesn't have a name. It is defined inside the iterate method, right where it is instantiated. Here is an outline:

public class ABList<T> implements ListInterface<T> {

   // fields and methods of the class

   // the iterator() method
   Iterator<T> iterator() {
      return new Iterator<T>() {

         // code for the ABListIterator class that creates the Iterator

      };  // end of the ABListIterator class and end of the return stmt
   } // end of the iterator() method

} // end of the ABList class

And here is a more complete example:

public class ABList<T> implements ListInterface<T> {
   protected final int DEFCAP = 100; // default capacity
   protected int origCap;            // original capacity
   protected T[] elements;           // array to hold this list’s elements
   protected int numElements = 0;    // number of elements in this list

   // other methods

   // the iterator method which returns an iterator
   public Iterator<T> iterator() {
      // the return statement creates a new iterator and the definition
      // of the Iterator class starts with the {
      return new Iterator<T>() {
         private int previousPos = -1;

         public boolean hasNext() {
         // Returns true if the iteration has more elements; otherwise returns false.
            return (previousPos < (size() - 1)) ;
         }

         public T next() {
         // Returns the next element in the iteration.
         // Throws NoSuchElementException - if the iteration has no more elements
            if (!hasNext())
               throw new IndexOutOfBoundsException("Illegal invocation of next " +
                             " in ABList iterator.\n");
            previousPos++;
            return elements[previousPos];
         }

      }; // end of return statement (that's why it ends with a ;)
   } // end of iterator() method
} // end of ABList class

The Iterator interface also defines a remove method, which allows the client code to remove the current item without messing up the iteration. Otherwise no changes can be made to an object while it is being iterated. The results are undefined if changes are made.

Complexity

Look at the code for the ABList and LBList methods. For each of the following methods, consider an ABList containing N elements and an LBList containing N elements. For each of them, what is the best case and worst case? Count the number of times each statement executes as a function of N, then get the big O.

add(T element)

add(int index, T element)

remove(int index)

remove (T target)

get(int index)

get(T target)