Java's Collections Framework

Java Lists

If you look at the complete Java documentation, you will see the extra operations which LinkedList has and ArrayList does not. In particular, there are some concerned with accessing the first and last items of the list. This reflects the fact that LinkedList is implemented using a doubly-linked list, so these operations are particularly suited to this implementation. But also, ArrayList has some operations which LinkedList does not have. One is removeRange which takes two integers as its arguments and changes the object so that all elements starting with the one indexed by the first argument and going up to but not including the one indexed by the second argument are removed. The others reflect the underlying implementation of ArrayList using the array and count technique. The method trimToSize changes the array in the object so that it is of the exact size of the object with no spare capacity. The method ensureCapacity takes an integer argument and changes the array in the object so that it is of the size of the integer argument if it was previously smaller. Using these operations would only make sense if you had a particular concern about efficiency.

You will note that the Java documentation refers to the types ArrayList<E> and LinkedList<E> as being subtypes of other types, and implementing various interface types. The reason for this is to allow generalised code to be written. The various classes and interfaces of which these are part are referred to as the Java Collections Framework. We will cover the most important aspects of this in this and the following section of notes, but if you are interested you can find a full guide here. For our purpose now, the main thing to note is that both ArrayList<E> and LinkedList<E> implement the interface List<E>. You can find the full documentation for this type here. This means that if you write a method whose parameter type is List, you can use that same method for arguments that are of type ArrayList or LinkedList. This is the best thing to do unless the code in the method really needs to use methods which are only found in ArrayList or LinkedList. To make your code as general as possible you should always use the type List rather than the types ArrayList or LinkedList except when you are actually creating objects using new. As List is an interface type, you cannot create an object whose actual type is List, you can only make a variable of type List refer to an object whose actual type is one of those which implements List. Apart from ArrayList and LinkedList, another type which implements List is Vector, which you may see referred to in some older Java textbooks. You can find the full reference to this type here, but the intention of Java's supplier is that though it is still made available for old code, the type ArrayList is a replacement for it.

The type List provides all the operations needed to manage a collection of items stored in a way so that each has a position in the collection. As a simple example, here is one program:

import java.util.*;

class BiggestInt
{
 public static void main(String[] args) throws Exception
 {
  Scanner input = new Scanner(System.in);
  System.out.println("Enter some integers (all on one line):");
  String line = input.nextLine();
  String[] words = line.split(" ");
  List<Integer> a = new ArrayList<Integer>();
  for(int i=0; i<words.length; i++)
     a.add(Integer.parseInt(words[i]));
  int pos = ListOps.posBiggest(a);
  System.out.print("The biggest integer is "+a.get(pos));
  System.out.println(" at position "+pos);
 }
}

import java.util.*;

class LastAlphabetically
{
 public static void main(String[] args) throws Exception
 {
  Scanner input = new Scanner(System.in);
  System.out.println("Enter some words (all on one line):");
  String line = input.nextLine();
  String[] words = line.split(" ");
  List<String> a = new LinkedList<String>();
  for(int i=0; i<words.length; i++)
     a.add(words[i]);
  int pos = ListOps.posBiggest(a);
  System.out.print("The last word alphabetically is \""+a.get(pos));
  System.out.println("\" at position "+pos);
 }
}

 public static <T extends Comparable<? super T>> int posBiggest(List<T> ls)
 {
  int pos = 0;
  for(int i=1; i<ls.size(); i++)
     if(ls.get(i).compareTo(ls.get(pos))>0)
        pos=i;
  return pos;
 }

You can find all the code examples given here in the directory

~mmh/DCS128/code/collections

Java Collections, Sets and Iterators

The type Set (documented here) is an alternative extension of Collection which does not have any concept of items being in a position in the collection, but which enforces the rule that an item may be in a set only once at most. So if s is of type Set<T> and t is of type t, then if s.contains(t) returns true (meaning t is already in s) then s.add(t) will have no effect on s. Like List, the type Set is itself an interface which is implemented by two actual classes, HashSet and TreeSet (documented here and here) which implement the underlying concept in two completely different ways. For the purposes of this course, you need not be concerned with how those two classes work underneath, but you would be able to find details in any good book on algorithms and data structures: one uses hash tables, the other uses trees. Using the "big-O" notation we considered previously, accessing a particular data item is O(1) with HashSet, but O(log N) with TreeSet. This suggests that HashSet should be used rather than TreeSet, unless we particularly need to use the extra operations and conditions which TreeSet provides, as HashSet gives more efficient access.

Here are two simple programs which use these two classes:

import java.util.*;

class HashSetTest
{
 public static void main(String[] args) throws Exception
 {
  Scanner input = new Scanner(System.in);
  System.out.println("Enter some words (all on one line):");
  String line = input.nextLine();
  String[] words = line.split(" ");
  Collection<String> a = new HashSet<String>();
  for(int i=0; i<words.length; i++)
     a.add(words[i]);
  System.out.println("The words are: "+a);
 }
}

import java.util.*;

class TreeSetTest
{
 public static void main(String[] args) throws Exception
 {
  Scanner input = new Scanner(System.in);
  System.out.println("Enter some words (all on one line):");
  String line = input.nextLine();
  String[] words = line.split(" ");
  Collection<String> a = new TreeSet<String>();
  for(int i=0; i<words.length; i++)
     a.add(words[i]);
  System.out.println("The words are: "+a);
 }
}

Now suppose you wanted to go through all the items in a TreeSet or HashSet object to find which is the largest according to their own sense of ordering (last alphabetically if the items are strings). The problem is that since sets have no sense of items being in a particular position, there is no method get which takes an integer argument i and returns the ith element of the set. So we could not use a for-loop in a way similar to that we used in generalised code for List objects above. The Java collections framework gives us a way round this using the concept of an iterator.

The method iterator is provided in the Collection interface, it is documented here. So for any object whose actual type is a subtype of Collection<E>, if a is a reference to the object, a.iterator() returns an object of type Iterator<E>. So this can be used for objects of type HashSet, TreeSet, ArrayList or LinkedList. If it refers to an object of type Iterator<E> and was produced by the call it=a.iterator() then each time it.next() is called it will return a different item from the collection referenced by a until all the items in that collection have been returned exactly once. You can also call a.hasNext() which will return a boolean value, true if there are some items in a which have not yet been returned by a call of a.next() and false otherwise. Attempting to call a.next() when a.hasNext() would return false causes an exception of type NoSuchElementException to be thrown. Using this idea of an iterator, the following loop:

for(Iterator<E> it=a.iterator(); it.hasNext(); )
    {
     E element = it.next();
     ...
    }

for(E element: a)
   {
    ...
   }

Here, for example, is code which reads some words, stores them in a TreeSet and prints them out using a for-each loop:

import java.util.*;

class TreeSetPrint2
{
 public static void main(String[] args) throws Exception
 {
  Scanner input = new Scanner(System.in);
  System.out.println("Enter some words (all on one line):");
  String line = input.nextLine();
  String[] words = line.split(" ");
  Collection<String> a = new TreeSet<String>();
  for(int i=0; i<words.length; i++)
     a.add(words[i]);
  int count=1;
  System.out.println("The words (duplicates deleted) are: ");
  for(String str: a)
      {
       System.out.println(count+": "+str);
       count++;
      }
 }
}

As another example of the use of an iterator, here is a static method which returns the biggest item (according to the items' own natural ordering) from any collection of items:

 public static <T extends Comparable<? super T>> T biggest(Collection<T> coll)
 {
  Iterator<T> it = coll.iterator();
  T biggest = it.next();
  while(it.hasNext())
     {
      T nextItem = it.next();
      if(nextItem.compareTo(biggest)>0)
         biggest = nextItem;
     }
  return biggest;
 }

import java.util.Comparator;

class LengthComparer implements Comparator<String>
{
 public int compare(String str1,String str2)
 {
  return str1.length()-str2.length();
 }
}

Now here is a version of the method biggest which takes a comparator object as an argument:

 public static <T> T biggest(Collection<T> coll,Comparator<T> comp)
 {
  Iterator<T> it = coll.iterator();
  T biggest = it.next();
  while(it.hasNext())
     {
      T nextItem = it.next();
      if(comp.compare(nextItem,biggest)>0)
         biggest = nextItem;
     }
  return biggest;
 }

import java.util.*;

class Longest
{
 public static void main(String[] args) throws Exception
 {
  Scanner input = new Scanner(System.in);
  System.out.println("Enter some words (all on one line):");
  String line = input.nextLine();
  String[] words = line.split(" ");
  List<String> a = new ArrayList<String>();
  for(int i=0; i<words.length; i++)
     a.add(words[i]);
  Comparator<String> comparer = new LengthComparer();
  String longest = CollectionOps.biggest(a,comparer);
  System.out.println("The longest word is \""+longest+"\"");
 }
}

import java.util.*;

class BestScrabble1
{
 public static void main(String[] args) throws Exception
 {
  Scanner input = new Scanner(System.in);
  System.out.println("Enter some words (all on one line):");
  String line = input.nextLine();
  String[] words = line.split(" ");
  List<String> a = new ArrayList<String>();
  for(int i=0; i<words.length; i++)
     a.add(words[i]);
  Comparator<String> comparer = new Scrabble();
  String best = CollectionOps.biggest(a,comparer);
  System.out.print("The word with the highest Scrabble score is \""+best);
  System.out.println("\" with score "+Scrabble.score(best));
 }
}

import java.util.Comparator;

class Scrabble implements Comparator<String>
{

 public static final int[] scores = {1,3,3,2,1,4,2,4,1,8,5,1,3,1,1,3,10,1,1,1,1,4,4,8,4,10};

 public static int score(String str)
 {
  String str1 = str.toUpperCase();
  int score = 0;
  for(int i=0; i<str1.length(); i++)
     score+=scores[str1.charAt(i)-'A'];
  return score;
 }

 public int compare(String str1,String str2)
 {
  return score(str1)-score(str2);
 }
}

Comparator objects may also be used to vary the behaviour of TreeSet objects. As we saw above, a TreeSet object stores a collection of data (with no duplicates) and has the property that if we go through the data using an iterator, it will be given in its natural ordering. But the class TreeSet<E> has, besides its zero-argument constructor which gives this sort of behaviour, another constructor which takes an argument of type Comparator<E>. If a TreeSet is constructed using this constructor, when its data is gone through using an iterator, the items will be given in the order determined by the comparator object given as the argument to the constructor. The following shows some code which demonstrates using a TreeSet constructed using a comparator of type LengthCompararer as given above:

import java.util.*;

class TreeSetPrint3
{
 public static void main(String[] args) throws Exception
 {
  Scanner input = new Scanner(System.in);
  System.out.println("Enter some words (all on one line):");
  String line = input.nextLine();
  String[] words = line.split(" ");
  Collection<String> a = new TreeSet<String>(new LengthComparer());
  for(int i=0; i<words.length; i++)
     a.add(words[i]);
  int count=1;
  System.out.println("The words in order of length with duplicates deleted are: ");
  for(String str: a)
      {
       System.out.println(count+": "+str);
       count++;
      }
 }
}

import java.util.Comparator;

class LengthComparer1 implements Comparator
{
 public int compare(String str1,String str2)
 {
  if(str1.length()==str2.length())
     return str1.compareTo(str2);
  else
     return str1.length()-str2.length();
 }
}

We noted previously that Collections.sort(a) would cause the elements in an arrayList referenced by a to be sorted in their natural ordering (with the arrayList being changed destructively). Note Collections (with a final s) in the java.util package is a separate class from Collection (without a final s). You can find the documentation for the class Collections here. It contains a number of static methods (hence they are called attached to the name Collections and not to an object reference) which deal with collections. Apart from the single argument sort discussed previously, there is a double argument sort which takes a Java List object (so an object of type ArrayList or LinkedList) and a comparator, and sorts the list in the ordering given by the comparator. Many of the other operations in the class Collections are ones we could write ourselves, but it makes sense to use the code already provided as part of the Java system, both because that code can be guaranteed to be correct and it helps to standardise the names used for these common operations. For example, the two methods max are the exact equivalents of the methods we have called biggest here. One takes a collection and returns the biggest element of the collection according to its natural ordering, the other takes a collection and a comparator and returns the biggest element of the collection according to the ordering given by the comparator. This means that in the program above we could replace the line:

String best = CollectionOps.biggest(a,comparer);

String best = Collections.max(a,comparer);