Chapter 14

Introduction to Collections

So far you’ve been introduced to only one way of storing a collection of objects — with Java arrays, which are good for storage, but fall short when you need to dynamically add or remove data, or to sort or traverse your collection. There are a number of classes and interfaces in the package java.util that are quite handy when multiple instances of some objects have to be co-located in memory. This lesson will introduce you to several of them.

You can find more collections in the java.util.concurrent package, but those will be reviewed in Lesson 21 after you become familiar with the concept of multi-threading. Together, the collection classes and interfaces located in java.util and java.util.concurrent are often called the Java Collection Framework.

Arrays Revisited

Java collection classes enable the storing of handles of related data in one place. Here a handle is a reference to the location of an object in memory. You were introduced to arrays in Lesson 5: Arrays let you store and access a group of variables of the same type. Let’s go over the steps you follow to declare and populate an array.

First, declare a variable of the type that matches the types of the objects that will be stored in the array, and reserve enough memory to accommodate all objects. For example, to reserve memory enough for storing 10 instances of class Customer you can declare a variable cust, as follows:

   Customer cust[] = new Customers[10];

At this point you’ve allocated enough space for the storage of 10 handles, not for the actual objects.

Next, create instances of the objects and store their handles in the array. Only the memory addresses of these instances will be stored in the array cust:

Customer[] cust = new Customer[10];
 
cust[0] = new Customer("David","Lee");
cust[1] = new Customer("Ringo","Starr");
     ... 
cust[9] = new Customer("Lucy","Mann");

Now let’s give a 15 percent discount to all customers who spent more than $500 in our online store:

for (Customer c: cust){
  if (c.getTotalCharges() > 500){
      c.setDiscount(15);
  }
}

Note the use of the for-each loop here. It safely iterates through this array without trying to access elements beyond its boundaries. You could’ve used another syntax of the for loop to access array elements by index. If a programmer forgot to check the size of the array and tried to access, say, eleven’s element like cust[10].setDiscount(15), Java would throw a run-time ArrayIndexOutOfBoundsException. Remember, if an array has n elements the last element’s index is n -1.

Classes ArrayList and Vector

Arrays offer the fastest access to the collection of data, but you have to know in advance the number of elements to be stored there. Luckily Java has classes that don’t have this restriction, and you can add more elements to a collection during the run time if needed. Classes Vector and ArrayList belong to this group.

Internally both collections use the array for storage, but when you keep adding elements to these collections they internally increase the size of the array (ArrayList increases the size by smaller increments), and as elements are deleted these collections shrink.

In both Vector and ArrayList you can store only objects — only primitives are allowed. Having said this, keep in mind that Java supports autoboxing (see Lesson 3), and if you’ll try to add a primitive to a collection, it’ll be automatically converted into he corresponding wrapper object.

You have to pay a price for this convenience: ArrayList is a little slower than the array as it needs to do internal array copying to change the collection’s size, and Vector is even slower because it supports thread synchronization (which will be explained in Lesson 21). But after the introduction of more efficient concurrent collections, Vector became less popular and you can achieve its synchronized functionality by using the method Collections.synchronizedList() on an ArrayList object. All further code samples in this section use only ArrayList.

To create and populate an ArrayList object you should first instantiate it, and then add instances of other objects to the ArrayList by calling the method add():, as in Listing 14-1.

Listing 14-1: Populating ArrayList

ArrayList customers = new ArrayList();
Customer cust1 = new Customer("David","Lee");
customers.add(cust1);
Customer cust2 = new Customer("Ringo","Starr");
customers.add(cust2);

The method add() doesn’t copy the instance of the object into the customers collection, it just stores the memory address of the object being added. The element numbering in ArrayList starts with 0. If you know that an ArrayList will store, say, 10 objects, instantiate it with the constructor that will allocate the right amount of memory on creation:

ArrayList customers = new ArrayList(10);

You can still add more than 10 elements, but JVM will allocate additional memory as needed.

The method get() is used to extract a particular element from ArrayList. Because ArrayList is generic storage for any type of object, the method get() returns elements as Object data types. It’s the responsibility of the programmer to provide proper casting, such as the following:

Customer theBestCustomer=(Customer) customers.get(1);

To illustrate a possible run-time error that will occur if the casting was not properly done, let’s add an object of another type to our customers collection from Listing 14-1:

Order ord = new Order(123, 500, "IBM");
customers.add(ord); 

The Java compiler will not complain because ArrayList can store any objects. At this point we have the elements in customers — two customers and one order. As a matter of fact, in Lesson 15 you’ll see another way of working with a collection capable of storing objects of unspecified type aka generics. I may be jumping ahead here, but the proper (generic) way of declaring collection for storing customers is shown below:

ArrayList<Customer> customers = new ArrayList(10);

The following code will throw the IllegalCastException on the third iteration of the loop:

int totalElem = customers.size(); // number of elements 
for (int i=0; i< totalElem;i++){
  Customer currentCust = (Customer) customers.get(i);
  currentCust.doSomething();          
}

Listing 14-2 shows how the operator instanceof helps you avoid this exception. But before using instanceof, see if you can come up with a more elegant solution, as you learned to do in the section “Polymorphism” in Lesson 7. You’ll find more samples of working with vectors in Lesson 21.

Listing 14-2: ArrayList and instanceof

ArrayList customers = new ArrayList(3);
 
// The code to populate customers with instances of Customer and Order 
// objects is omited for brevity 
 
int totalElem = customers.size();
 
// Iterate through the list customers and do something with each 
//  element of this collection 
 
for (int i=0; i<totalElem;i++){
  Object currElement = customers.get(i);
  if (currElement instanceof Customer){
    Customer currentCust= (Customer)customers.get(i);
    currentCust.doSomething();          
  }
  else if (currElement instanceof Order){
    Order currentOrder = (Order) customers.get(i);
    currentOrder.doSomething();          
  }
}

Collection Interfaces from java.util

A typical collection class implements several interfaces, which represent a well-designed hierarchy. For example, ArrayList implements the List interface, which extends Collection. Just reading the comments in the source code for java.util habitats can give you a good idea of what they are for.

Collection extends Iterable; there are no classes that directly implement this interface. Only its descendent interfaces are implemented. You can use a for-each loop (see the “Arrays Revisited” section earlier in this lesson) with classes that implement Iterable.

The List interface is defined for the ordered collections: ArrayList, Vector, and LinkedList. It allows duplicate elements. For example, the following code snippet will create two elements in ArrayList:

myArrayList.add("Mary");
myArrayList.add("Mary");

The Set interface is implemented by collections that don’t allow duplicate elements, e.g., HashSet and SortedSet. For example, the following code snippet will create one element in HashSet. The second line will find out that Mary already exists, and won’t change it and will return false:

myHashSet.add("Mary");
myHashSet.add("Mary");

The Map interface is for storing key/value pairs. A map can’t contain duplicate keys and each key can be mapped to only one value (object). You’ll see some relevant code examples in the next section.

The Queue interface is mainly for collections that require first-in-first-out (FIFO) operation (so-called priority queues are the exception). Every new element is added to the tail of the queue and the elements are retrieved from the head of the queue. You can restrict the size of the queue if need be. LinkedList is one of the classes that implement the Queue interface.

Now let’s look at some of the classes that implement these interfaces.

Classes Hashtable and HashMap

The classes Hashtable and HashMap implement the Map interface storing key/value pairs. These classes offer a convenient way of storing and accessing the elements of a collection: by key. You can assign a key to an instance of some Java object and use it as a reference. The collections store objects as key/value pairs. Let’s say we need to store instances of the classes Customer, Order, and Portfolio in the same collection. The code snippet from Listing 14-3 creates these instances first, and then puts them in the collection under some identifiers (keys).

Listing 14-3: Hashtable for key/value pairs

Customer cust = new Customer("David", "Lee");
Order ord = new Order(123, 500, "IBM");
Portfolio port = new Portfolio(123);
 
Hashtable data = New Hashtable();
data.put("Customer", cust);
data.put("Order",ord);
data.put("Portfolio", port);

The values in double quotes represent keys by which the objects could be retrieved. In this example the keys are represented by the Java class String, but you can use any objects as keys. The keys are selected based on the application needs, e.g. the code in Listing 14-3 could be written in some order management application.

If you have an idea of how many elements you are planning to store in a Hashtable, use another constructor:

Hashtable data = new Hashtable(10); // 10-element capacity

The method get() provides access to these objects via the key. You need to either perform the proper casting as shown below or use generics (explained in Lesson 15):

Order myOrder = (Order) data.get("Order");

The method size() returns the number of elements in the Hashtable:

int totalElem = data.size();

Methods containsKey() and containsValue() help you to find out if the collection contains a specific key or value. You can find an example of Hashtable usage in Lesson 31.

The class HashMap is similar to Hashtable, but it allows null as a key or value and is not synchronized. If you are writing code that attempts to access the same element concurrently without using multi-threading, use HashMap, as it performs faster than Hashtable.

To speed up the table lookup, both HashMap and Hashtable index the data by applying a so-called hash function that (based on the contents of the object) generates a hash code, one number that represents a large object. There’s a slight chance that two different objects will generate the same hash code, but the same object will always produce the same hash code. You can read more about hash functions in Wikipedia at http://en.wikipedia.org/wiki/Hash_function.

Class Properties

Pretty often a desktop application offers you a way to specify and store user preferences such as fonts and colors. This is a use case in which storage of key/value pairs is exactly what’s needed. You can store such preferences locally or on remote servers. In Lesson 16 you’ll learn how to work with files and other data streams, but from a data structure perspective you’ll be dealing with a collection of key/value pairs, such as color=red, font=verdana.

Windows-based applications often store some configurable parameters in the .ini files. In general, Java applications store their properties in plain text files, XML files, database tables, and others.

In this section you’ll see some code fragments illustrating how the Java class Properties, which extends Hashtable, can be used to manipulate with properties using key/value pairs. The class Properties has one restriction that Hashtable does not: Both the key and the value have to be of type String. In Lesson 19 you’ll see a complete application called MailMan that reads the data needed for sending emails from the mailman.properties file, which has the following contents:

SmtpServer=mail.xyz.com
[email protected]
[email protected]
from=yakov @xyz.com

To load this file into the Properties object, just define an input stream on this file (see Lesson 16) and call the method load(), as shown in Listing 14-4. After the file has been loaded into the Properties object, each individual property can be obtained with the method getProperty().

Listing 14-4: Reading file mailman.properties into the Properties object

Properties prop=new Properties();
FileInputStream in =null;
try{
  new FileInputStream ("mailman.properties");
  prop.load(in);
}catch(Exception e){...}
finally{... in.close();...}
 
String from = prop.getPropery("from") 
String mailServer=prop.getProperty("SmtpServer");
...

Java does not have global variables, but as a workaround you can make these properties available to any object in your application by turning them into system properties available from any class in your application:

System.setProperties(prop);

But keep in mind that the preceding line will also replace the existing system properties, which you may or may not want to do. Now you can get these values from any other class in your application, for example:

String mailServer = System.getProperty("SmtpServer");

If you decide to store properties in XML files, the class Properties offers you the method loadFromXML() to read properties and the method storeToXML() to store them in a simple XML format.

Enumeration and Iterator

In general, enumerations are sets of items that are related to each other. For example, shipment options or ice cream flavors — such enumerations are supported by the Java keyword enum (see Lesson 20). But because we are talking about collections, the meaning of the term enumeration is somewhat different. If a collection object implements the interface Enumeration, you can traverse its elements sequentially, without even knowing the total number. You just need to obtain the enumeration of all elements and use the methods hasMoreElements() and nextElement(). For example, to process all elements of Vector customers do the following:

Vector customers = new Vector();
...
Enumeration enum=customers.elements();//returns Enumeration  
 
while(enum.hasMoreElements()){
   Customer currentCust = (Customer)enum.nextElement());
   currentCust.doSomething();
}

If you’re using ArrayList customers, the utility class Collections comes in handy, as it has a method that returns enumeration:

Enumeration enum = Collections.enumeration(customers);

You can also obtain the enumeration of a Hashtable’s keys or elements. For example:

Hashtable data = new Hashtable();
...
// Get the keys
Enumeration enumKeys = data.keys();
while(enum.hasMoreElements()){
...
}
// Get the elements
Enumeration enumElements = data.elements();
...

In a way the Enumeration interface is similar to Iterator, which was introduced as a part of the Java Collections Framework years after. It also offers a standard way to process elements of a collection sequentially. The main difference between the two is that Enumeration is a read-only means of traversing a collection, while Iterator has a method called remove() that enables you to delete unwanted elements of the collection. Enumeration is considered a legacy interface and you should use Iterator. For example, you can iterate through the ArrayList customers as follows:

Iterator iCust = customers.iterator();
while (iCust.hasNext()){
   System.out.println(iCust.next())
}

Class LinkedList

Java collection classes differ in how you can retrieve and insert objects. If you need to work with a sequential list of objects and often insert the object into the list, the data structure called linked list can fit the bill. Java has a class called LinkedList that stores elements so that each contains a reference to the next (aka node). Each element in a doubly linked list also contains a reference to the previous element. These features of the doubly-linked class LinkedList allow you to create queues (FIFO), and stacks (last-in-first-out or LIFO).

Insertion of a new object inside the list comes down to a simple update of two references: The previous element of the list has to be pointed to the newly inserted object, which will have to include a reference to the next element, if any. Compare this to the complexity of lots of memory allocations and object moving in memory to increase the size of an ArrayList or Vector, and you’ll appreciate the value that linked lists bring to the table. On the other hand, collections that use arrays for the underlying data storage offer random access to the data elements, while linked lists can be processed only sequentially.

You can navigate through the list using the class ListIterator, which supports going through the list in both directions via its methods next() and previous(). Listing 14-5 shows you an example, in which a standby passenger list is created at the boarding gate of some airline company.

Listing 14-5: LinkedList example

import java.util.LinkedList;
import java.util.ListIterator;
 
public class TestLinkedList {
 
 public static void main(String[] args) {
 
  LinkedList passengerList = new LinkedList();
 
  passengerList.add("Alex Smith");
  passengerList.add("Mary Lou");
  passengerList.add("Sim Monk");
 
  // Get the list iterator and print every element of the list 
  ListIterator iterator = passengerList.listIterator();
 
  System.out.println(iterator.next());
  System.out.println(iterator.next());
  System.out.println(iterator.next());
 }
 
}

The code in Listing 14-5 will iterate and print all the objects from the list using ListIterator. You might be wondering how the println() method knows how to print an object returned by the iterator. It tries to find the method toString() defined on the object and call it. In our example the object is a string itself, but in a real-world situation you might need to print objects, and defining the toString() method is the right way to do so.

If you use add() or remove() while iterating through the list, the new element will be either inserted or removed at the iterator’s current position.

Class BitSet

The class BitSet stores a sequence of bits. It’s a pretty efficient class when you need to pass to a program a number of flags that indicate certain conditions. Think of a financial trading application that must be extremely fast. One way to improve the performance is to represent the maximum amount of information in a minimal number of bytes.

Another use case for BitSet are programs that send signals with information about the state of a certain device. For example, some vending machines have smart chips that can automatically dial their owner’s phone number and send a signal containing status information. Sending a set of flags (bits that are set to 1 or 0) instead of text or numbers is the most economical way to do this.

The BitSet class does not have a size limit and can grow as needed. Depending on which bit is set (e.g., has the value of 1) the class could indicate the following:

• Bit 0: The coin box is empty.
• Bit 1: The coin box is half full.
• Bit 2: The coin box is full.
• Bit 3: The coin box has been removed.
• Bit 4: The Coca-Cola row is empty.

One instance of a BitSet object carries multiple parameters describing its status. The program that receives this signal could print a nice report, and the owner of this remote machine could decide if he or she needs to send a technician to look at the machine.

The Java class BitSet is nothing more than a vector of bits. The following code prepares a signal indicating that the coin box is full and there are no Coca-Cola bottles left.

import java.util.BitSet;
class VendingMachineSender {
   public static void main(String args[]){
       BitSet report = new BitSet();
       report.set(2);   // box is full
       report.set(4);   // no Coca Cola
   }
} 

When the phone call comes in, the callback method phoneRings() is invoked and the signal can be decoded like this:

import java.util.BitSet;
class VendingMachineListener {
   public void phoneRings(BitSet signal)
      int size = signal.size();
 
      for (int i=0;i<size;i++){
          if (signal.get(i)){
            switch (i){
               case 0:
                 System.out.println("Box is empty");
                 break;
               case 1:
                 System.out.println("Box is half full");
                 break;
               case 2:
                 System.out.println("Box is full");
                 break;
               // more cases come here 
            }
          }
      }       
   }
} 

Try It

Modify the LinkedList example from Listing 14-5 to add an arbitrary object, say the VIP customer after the very first element of the list. You must do this while iterating through the list. When the program is ready it should print the following:

Alex Smith
VIP Customer
Mary Lou
Sim Monk

Lesson Requirements

You should have Java installed.

You can download the code and resources for this Try It from the book’s web page at www.wrox.com. You can find them in the Lesson14 folder in the download.

Step-by-Step

Run the program now. It’ll print the first element of the linked list and then produce a run-time exception:

Alex Smith
Exception in thread "main" java.util.ConcurrentModificationException
       at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:761)
       at java.util.LinkedList$ListItr.next(LinkedList.java:696)
       at TestLinkedList.main(TestLinkedList.java:20)

The reason for this concurrent modification exception is that one thread of execution was iterating through a collection, and at the same time another thread was trying to modify the underlying collection in an unsafe way. The concept of threads will be introduced in Lesson 20.

Please select Lesson 14 on the DVD with the print book, or watch online at www.wrox.com/go/fainjava to view the video that accompanies this lesson.