Title: Collection List Interfaces
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

Collect List Interfaces

There are a number of standard Interfaces and classes that we now need to be aware of. These are sometime referred to as the Collections Framework.

Why Use the "Java Collections Framework"?

1. Reduces programming effort -methods such as sorting algorithms are already written.
2. Increases program speed and quality.
3. Standard interfaces make it easier to learn how to use the classes available.

Standard Interfaces in the Collections Framework

Java has defined some standard Interfaces that describe the standard datastructures needed. Many of these standard Interfaces and Classes are based on a top level Collection interface. There is also a Map interface that we will talk about later.

- interface Collection - This is the most generic interface. This interface defines some simple methods that are generic to a large number of datastructures. This interface does not impose many constraints on the type of datastructure. The Collection class is a parent interface to several other interfaces
  - interface List extends Collection- The List interface is derived from the Collection class. The List class represents an ordered Collection. Ordered does not imply sorted. An Array can be considered ordered because each element has a specific index that can be used to access the element. A List can store duplicate elements.
      - class ArrayList - This is a class which implements the List interface. ArrayList can be thought of as an array of Objects that can dynamically grow as needed. The ArrayList class is good if you have to index your datastructure similar to array accesses. The ArrayList matches the List interface pretty closely. There are a few extra methods in ArrayList, but no major deviation from the concept of a List. An ArrayList is good if you want to randomly access or set entries in the list with the get(index) or set(index, object) methods.
      - class Vector - This class implements the List interface and is very similar to ArrayList. The Vector class has been around longer than the ArrayList and carries some backwards compatible baggage. It's good to know about the Vector class, because many java examples use it because its well known and been around a long time.
      - class LinkedList - This class implements the List interface and is designed to work well with linked lists, especially Queues. Linked Lists will be discussed in a later set of notes.
  - interface Set extends Collection - The methods in Set are the same as in the Collection interface. However a Set adds the characteristic that you can't have duplicate objects in a Set. If you are a mathematician you may be familiar with the idea of Set operations. In math, you can do unions, and intersections of Sets. Although you won't see methods for union and intersection in the Set interface, it's easy to build it from the primitives.
        - class HashSet - an implementation of the Set interface.
      - interface SortedSet extends Set - A Set with the added constraint that the data stays sorted
        - class TreeSet - an implementation of SortedSet

Differences between Vector and ArrayList

The ArrayList is almost the same as the Vector class. One difference is that by default the Vector class is synchronized (we will cover this concept when we cover Threads) and the ArrayList is not. This means that by default the Vector class will work with multiple tasks accessing at the same time. However, this also means that the ArrayList is more efficient because it doesn't have the synchronization overhead. The Vector class was defined in 1.1 to be synchronized, so for backwards compatibility it has to stay that way in later releases.

If you really want a synchronized ArrayList, you can get it by invoking the synchronizedList method in the Collections class. This is the best of both worlds for ArrayList ---- run faster by default and add on synchronization when you really need it. So Normally you want to use ArrayList instead of the Vector class. The Vector class is mainly there for backwards compatibility with Java that has been around for a while.

Because Vector pre-dates the ArrayList and the definition of the List interface, there are some methods that do the same thing. Here is a small list of the duplicate names:

- addElement - new name is add
- elementAt - new name is get
- insertElementAt, new name is add --- the version with an index
- removeElement - new name is remove
- setElementAt - new name is set

interface Collection

Proto-Type | Description
boolean add(Object o) boolean add(E e) | Ensures that this collection contains the specified element (optional operation).
void clear() | Removes all of the elements from this collection (optional operation).
boolean contains(Object o) boolean contains(E e) | Returns true if this collection contains the specified element.
boolean isEmpty() | Returns true if this collection contains no elements.
Iterator<E> iterator() | Returns an iterator over the elements in this collection.
boolean remove(Object o) boolean remove(E e) | Removes a single instance of the specified element from this collection, if it is present (optional operation). boolean retainAll(Collection c) Retains only the elements in this collection that are contained in the specified collection (optional operation).
int size() | Returns the number of elements in this collection.
Object[] toArray() | Returns an array containing all of the elements in this collection.
String[] toArray(String[] a) | Returns an array containing all of the elements in this collection whose runtime type is that of the specified array. Note that Any class can replace String in this call.

interface Iterator

When working with Collections classes, its often good to be able to list all of the members of a collection. For a simple array type of collection, this is not a problem. However, some of our collections are trees, or hashmaps which do not have a simple array concept associated with them. For this reason, the Iterator class is a standard way to list all the elements in a Collection. It only has 3 methods ( the remove method is not used very often). We will demonstrate its usage in the first example.

The concept of an Iterator shows up a lot in advanced Java concepts. You will see it in Java Servlets, Jdbc, and XML.

One side note --- It's not a good idea to be half way through an iterator and decide to add another element to the Collection. This can cause problems.

There is also an older variation of an Iterator that was in used in Java 1.1 called Enumeration. The method names are a little different, but the concept is the same. An Enumeration contains the methods:
hasMoreElements()
nextElement()

Proto-Type | Description
boolean hasNext() | Returns true if the iteration has more elements.
E next() | Returns the next element in the interation.
void remove() | Removes from the underlying collection the last element returned by the iterator (optional operation).

Collection Example


package collections;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;


public class CollectionExample {


    public static void main(String[] args) {

        //Collection<String> collection = new ArrayList<String>();
        Collection<String> collection = new HashSet<String>();

        collection.add("one");
        collection.add("two");
        collection.add("three");
        collection.add("four");

        // Elements in the collection must implement equals method
        if (collection.contains("one"))
        {
            System.out.println("My Collection contains one");
        }

        Iterator<String> iter = collection.iterator();
        while (iter.hasNext())
        {
            String s = iter.next();
            System.out.println(s);
        }

        collection.remove("three"); // This also requires an implementation of equals
        System.out.println("************************************");

        Object[] obArr = collection.toArray();
        String[] arr = collection.toArray( new String[1]);

        for (int i=0; i < arr.length; i++)
        {
            System.out.println(arr[i]);
        }

        if (!collection.isEmpty())
        {
            System.out.println("Collection is NOT empty");
            collection.clear();
            if (collection.isEmpty())
                System.out.println("Collection is now empty");
        }

    }

}





interface List extends Collection

If your collection has some concept of order, then you might want to work with the List interface. ArrayLists, and LinkedLists are the standard datastructures that have some sense of order. This means that you can index the list by some index number.

An ArrayList is good if your primary operation is random accessing of the datastructure by index. Adding to the end of the ArrayList is fast , but adding or removing anywhere else is inefficient because you have to slide everything else down.

Another List based data-structure LinkedList is good for Queues. A LinkedList is not as fast for accessing elements by index. But a LinkedList is faster for inserting a new element anywhere in the list. LinkedLists are especially good when you primarily access data off the front or the end of the list.

Proto-Type | Description
void add(int index, E e) | Inserts the specified element at the specified position in this list (optional operation).
E get(int index) | Returns the element at the specified position in this list.
int indexOf(E e) | Returns the index in this list of the first occurrence of the specified element, or -1 if this list does not contain this element.
int lastIndexOf(E e) | Returns the index in this list of the last occurrence of the specified element, or -1 if this list does not contain this element.
ListIterator<E> listIterator() | Returns a list iterator of the elements in this list (in proper sequence).
ListIterator<E> listIterator(int index) | Returns a list iterator starting at the specified index
E remove(int index) | Removes the element at the specified position in this list (optional operation).
E set(int index, E element) | Replaces the element at the specified position in this list with the specified element (optional operation).
List<E> subList(int fromIndex, int toIndex) | Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.

Here is MyArrayList implementing the full List interface (I cheated and I throw an UnsupportedOperationException exception for the things I'm too lazy to finish)

interface listIterator extends Iterator

If your Collection is actually a List, then you can get a fancier Iterator than the simple one shown above. The listIterator has everything that a regular Iterator has plus the methods shown in the table below. The methods available in this interface allow you to move backwards as well as forward. Also you can change data as you walk through the iterator. Note the set, and add routines.

Proto-Type | Description
void add(E e) | Inserts the specified element into the list (optional operation).
boolean hasPrevious() | Returns true if this list iterator has more elements when traversing the list in the reverse direction.
int nextIndex() | Returns the index of the element that would be returned by a subsequent call to next.
E previous() | Returns the previous element in the list.
int previousIndex() | Returns the index of the element that would be returned by a subsequent call to previous.
void set(E e) | Replaces the last element returned by next or previous with the specified element (optional operation).

Collections Class

Note the difference between the Interface Collection and the Class Collections. One of the payoffs to using standard Java classes is that you can get standard code already written for you. If you have a class which implements List, you can get code to do sorts, shuffles, max, min, and binarySearch. This is best demo'ed in the example below:

Proto-Type | Description
static int binarySearch(List<E> list, E e) | Searches the specified list for the specified object using the binary search algorithm.
static E max(Collection<E> coll) | Returns the maximum element of the given collection, according to the natural ordering of its elements.
static E min(Collection<E> coll) | Returns the minimum element of the given collection, according to the natural ordering of its elements.
static void reverse(List<E> l) | Reverses the order of the elements in the specified list.
static void shuffle(List<E> list) | Randomly permutes the specified list using a default source of randomness.
static void sort(List<E> list) | Sorts the specified list into ascending order, according to the natural ordering of its elements.
static List<E> synchronizedList(List<E> list) | Returns a synchronized (thread-safe) list backed by the specified list.
static List<E> unmodifiableList(List<E> list) | Returns an unmodifiable view of the specified list.

Sample programs using some of the new concepts above


package collections;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ListExample {


    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        // List<String> list = new LinkedList<String>();
        // List<String> list = new Vector<String>();

        list.add("orange");
        list.add("bannana");
        list.add("apple");
        list.add("pear");
        list.add("grape");
        list.add("peach");
        list.add("avacado");

        System.out.println("Original list="+list.toString());
        Collections.shuffle(list);
        System.out.println("Shuffled list="+list.toString());
        Collections.sort(list);
        System.out.println("Sorted list="+list.toString());

        int index = Collections.binarySearch(list, "grape");
        System.out.println("index of grape = " + index);

        index = Collections.binarySearch(list, "strawberry");
        System.out.println("index of strawberry = " + index);

        String max = Collections.max(list);
        System.out.println("max="+ max);

        List<String> sublist = list.subList(2, 5);
        System.out.println("sublist[2,5)=" + sublist.toString());
    }

}



Using More Complicated Objects

I have kept it as simple as possible by using the String class for all of my stored Objects. This avoids some complicated issues.

A couple of issues to consider when you create your own object to store in a collection.

- If you have different kinds of classes, its useful to have a common class that all your classes are derived from. See the Pet, Dog, Cat family of classes below.
- Some of the methods in the collections classes assume certain methods are available in your Class. It's a good idea to override the toString in your class, if you want to print the collection like :
System.out.println(pets);
- If you want methods like contains to work, your object will need to have a valid equals method ---- see comments in the example below.

Pets.java



import java.util.*;
class Pet
{
    private String name;
    private double weight;
    Pet(String name, double weight)
    {
        this.name = name;
        this.weight = weight;
    }
    public String getName()
    {
        return name;
    }
    public double getWeight()
    {
        return weight;
    }
    public String toString()
    {
        return name + " " + weight;
    }
    public void increment_weight(double delta)
    {
        weight += delta;
    }
    /*
    public boolean equals(Object obj)
      {
          if (obj==null || obj.getClass() != this.getClass()) return false;
          Pet pet = (Pet)obj;
          return (weight==pet.weight) && name.equals(pet.name);
      }
      */

}

class Cat extends Pet{
  Cat(String name, double weight)
  {
    super(name,weight);
  }
  public String toString(){
      return "Cat: "+super.toString();
  }
  /*
  public boolean equals(Object obj)
  {
      if (obj==null || obj.getClass() != this.getClass()) return false;
      return super.equals(obj);
  }
  */
}

class Dog extends Pet{

    Dog(String name, double weight) {
      super(name,weight);
    }
    public String toString() {
        return "Dog: " + super.toString();
    }
/*
      public boolean equals(Object obj)
      {
          if (obj==null || obj.getClass() != this.getClass()) return false;
          return super.equals(obj);
      }
      */
}
// -----------------------------------------------

public class Pets {
public static void main(String[] args) {
      ArrayList<Pet> pets = new ArrayList<Pet>();
      Dog d;

      pets.add(  new Dog("Tiger", 20.0) );
      pets.add(  new Dog("Fido", 50.0)  );
      pets.add(  new Dog("Maya", 10.0)  );
      pets.add(  new Dog("Benji", 80.0) );

      // After trying this once, uncomment the equals method in Dog
      // recompile and rerun and see the difference.
      d = new Dog("Fido", 50.0);
      if (pets.contains(d))
        {
          System.out.println(" We already have a " + d);
        }
      else
        {
            System.out.println("We don't have " + d + "  Adding ...");
            pets.add(d);
        }
      // What happens with the following statement
      Cat c = new Cat("Maya", 10.0);
      if (pets.contains(c))
      {
        System.out.println(" We already have a " + c);
      }
      else
      {
          System.out.println("We don't have " + c + "  Adding ...");
          pets.add(c);
      }

      System.out.println("********** All of my pets gained weight ************");
      Iterator<Pet> iter = pets.iterator();
      while(iter.hasNext())
      {
          Pet p = iter.next();
          p.increment_weight(1.0);
          // Calls appropriate toString method
          System.out.println(p);
      }


      System.out.println("Here is my collection :");
      // The following requires you to override toString in the Dog and Cat
      // classes to get something meaningful
      System.out.println(pets);

      // Uncomment the following and fix it and print out the sorted list
      //Collections.sort(pets);
	
	   System.out.println("Sorted version of pets:");
      System.out.println(pets.toString());

      //Collections.sort(pets, new SortByWeight());
      System.out.println("Sorted by weight:");
      System.out.println(pets.toString());

  }

}





Comparable Interface to fix sort

If you want to sort, use binarySearch , max, min or any other method that needs to be aware of how to compare objects, you will run into the problem described above. The solution is to have our Pet class implement the Comparable interface. This means that we need to add a method called compareTo, which returns 0 if the 2 objects match and positive or negative depending on which object is larger.

Uncomment the line above:

//Collections.sort(pets);

Redefine the Pet class as follows:

class Pet implements Comparable

Add the method to the Pet class:


public int compareTo(Object obj)
    {
    		Pet p = (Pet)obj;
    		int retVal = name.compareTo(p.name);
    		if (retVal != 0) return retVal;
    		if (weight > p.weight) return 1;
    		return -1;    	
    }


Other sorts other than:

sort(List<T> list) // This sorts list according to the natural order of the T objects ... Note that T needs to implement Comparable for this to work.

Suppose that you had multiple ways that you want to sort your Pets class. Once you have implemented the Comparable interface in the Pet class, its awkard to provide another way of defining Comparable. Note you could keep some parameters that control how your compareTo method works.

A cleaner way is to recognize that in the Collections class there is another sort routine that is defined as follows:

sort(List<T> list, Comparator<? super T> c)

We can have redefine the sort by providing another class which implements Comparator. See if you can sort your Pets by weight by using the following class:


class SortByWeight implements Comparator<Object>
{
    public int compare(Object o1, Object o2)
    {
        Pet p1 = (Pet)o1;
        Pet p2 = (Pet)o2;
        if (p1.getWeight() < p2.getWeight())
            return -1;
        if (p1.getWeight() > p2.getWeight())
            return 1;
        return p1.getName().compareTo(p2.getName());
    }
    public boolean equals(Object obj) // Not sure why this is necessary????
    {
        return false; ///????
    }
}


The final version of our Pets.java will look like:


package collections;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;

class SortByWeight implements Comparator<Object>
{
    public int compare(Object o1, Object o2)
    {
        Pet p1 = (Pet)o1;
        Pet p2 = (Pet)o2;
        if (p1.getWeight() < p2.getWeight())
            return -1;
        if (p1.getWeight() > p2.getWeight())
            return 1;
        return p1.getName().compareTo(p2.getName());
    }
    public boolean equals(Object obj) // Not sure why this is necessary????
            {
        return false; ///????
            }
}


class Pet implements Comparable
{
    private String name;
    private double weight;
    Pet(String name, double weight)
    {
        this.name = name;
        this.weight = weight;
    }
    public String getName()
    {
        return name;
    }
    public double getWeight()
    {
        return weight;
    }
    public int compareTo(Object obj)
    {
        Pet p = (Pet)obj;
        int retVal = name.compareTo(p.name);
        if (retVal != 0) return retVal;
        if (weight > p.weight) return 1;
        return -1;
    }
    public String toString()
    {
        return name + " " + weight;
    }
    public void increment_weight(double delta)
    {
        weight += delta;
    }

    public boolean equals(Object obj)
    {
        if (obj==null || obj.getClass() != this.getClass()) return false;
        Pet pet = (Pet)obj;
        return (weight==pet.weight) && name.equals(pet.name);
    }


}

class Cat extends Pet{
    Cat(String name, double weight)
    {
        super(name,weight);
    }
    public String toString(){
        return "Cat: "+super.toString();
    }

    public boolean equals(Object obj)
    {
        if (obj==null || obj.getClass() != this.getClass()) return false;
        return super.equals(obj);
    }

}

class Dog extends Pet{

    Dog(String name, double weight) {
        super(name,weight);
    }
    public String toString() {
        return "Dog: " + super.toString();
    }

    public boolean equals(Object obj)
    {
        if (obj==null || obj.getClass() != this.getClass()) return false;
        return super.equals(obj);
    }

}
// -----------------------------------------------

public class Pets {
    public static void main(String[] args) {
        ArrayList<Pet> pets = new ArrayList<Pet>();
        Dog d;

        pets.add(  new Dog("Tiger", 20.0) );
        pets.add(  new Dog("Fido", 50.0)  );
        pets.add(  new Dog("Maya", 10.0)  );
        pets.add(  new Dog("Benji", 80.0) );

        // After trying this once, uncomment the equals method in Dog
        // recompile and rerun and see the difference.
        d = new Dog("Fido", 50.0);
        if (pets.contains(d))
        {
            System.out.println(" We already have a " + d);
        }
        else
        {
            System.out.println("We don't have " + d + "  Adding ...");
            pets.add(d);
        }
        // What happens with the following statement
        Cat c = new Cat("Maya", 10.0);
        if (pets.contains(c))
        {
            System.out.println(" We already have a " + c);
        }
        else
        {
            System.out.println("We don't have " + c + "  Adding ...");
            pets.add(c);
        }

        System.out.println("********** All of my pets gained weight ************");
        Iterator<Pet> iter = pets.iterator();
        while(iter.hasNext())
        {
            Pet p = iter.next();
            p.increment_weight(1.0);
            // Calls appropriate toString method
            System.out.println(p);
        }


        System.out.println("Here is my collection :");
        // The following requires you to override toString in the Dog and Cat
        // classes to get something meaningful
        System.out.println(pets);

        // Uncomment the following and fix it and print out the sorted list
        Collections.sort(pets);

        System.out.println("Sorted version of pets:");
        System.out.println(pets);

        Collections.sort(pets, new SortByWeight());
        System.out.println("Sorted by Weight:");
        System.out.println(pets);

    }

}



Last Updated: July 22, 2014 9:48 PM