Java Collections Framework Overview

Case Study: Building A Dynamic Array

Imagine, for a moment, that you are working on a Java project and you’re deep into the code. You’re in the flow and you don’t want to stop to read no stinkin’ API documentation. The problem at hand dictates the need for an array with special powers — one that can automatically grow itself when one too many elements are inserted. To solve your problem you hastily crank out the code for a class named DynamicArray shown in example 17.1 along with a short test program shown in example 17.2. Figure 17-1 gives the results of running the test program.

Example 17.1: DynamicArray.java

 1     public class DynamicArray { 2       private Object[] _object_array = null; 3       private int _next_open_element = 0; 4       private int _growth_increment = 10; 5       private static final int INITIAL_SIZE = 25; 6 7       public DynamicArray(int size){ 8         _object_array = new Object[size]; 9       } 10 11      public DynamicArray(){ 12        this(INITIAL_SIZE); 13      } 14 15      public void add(Object o){ 16        if(_next_open_element < _object_array.length){ 17           _object_array[_next_open_element++] = o; 18        }else{ 19        growArray(); 20        _object_array[_next_open_element++] = o; 21         } 22      } // end add() method; 23 24 25      private void growArray(){ 26        Object[] temp_array = _object_array; 27        _object_array = new Object[_object_array.length + _growth_increment]; 28        for(int i=0, j=0; i<temp_array.length; i++){ 29          if(temp_array[i] != null){ 30            _object_array[j++] = temp_array[i]; 31          } 32          _next_open_element = j; 33        } 34        temp_array = null; 35     } // end growArray() method 36 37 38     public Object get(int index){ 39       if((index >= 0) && (index < _object_array.length)){ 40          return _object_array[index]; 41       }else return null; 42     } 43 44     public int size(){ return _object_array.length; } 45 46  } // end DynamicArray class definition

Example 17.2: ArrayTestApp.java

 1     public class ArrayTestApp { 2       public static void main(String[] args){ 3         DynamicArray da = new DynamicArray(); 4         System.out.println("Array size is: " + da.size()); 5         da.add(new String("Ohhh if you loved Java like I love Java!!")); 6         System.out.println(da.get(0).toString()); 7         for(int i = 1; i<26; i++){ 8           da.add(new Integer(i)); 9         } 10        System.out.println("Array size is: " + da.size()); 11        for(int i=0; i<da.size(); i++){ 12           if(da.get(i) != null){ 13         System.out.print(da.get(i).toString() + ", "); 14          } 15        } 16        System.out.println(); 17      }//end main() method 18    }// end ArrayTestApp class definition

Figure 17-1: Results of Testing DynamicArray

Referring to example 17.1 — the data structure used as the basis for the DynamicArray class is an ordinary array of Objects. Its initial size can be set via a constructor or, if the default constructor is called, the initial size is set to 25 elements. Its growth increment is 10 elements, meaning that when the time comes and the array must expand, it will expand by 10 elements. Besides its two constructors the DynamicArray class has four additional methods: add(), growArray(), get(), and size().

The add() method inserts an Object reference into the next available array element which is pointed to by the _next_open_element variable. If there’s no room left in the array the growArray() method is called to grow the array. The growArray() method must create a temporary array of Objects and copy each element to the temporary array. It must then create a new, larger Object array and copy the elements to it from the temporary array.

The get() method allows you to access each element of the array. If the index argument falls out of bounds the method returns null. The size() method simply returns the number of elements (references) contained in the array, which is the value of the _next_open_element variable.

Referring to example 17.2 — the ArrayTestApp class is a short program that tests the functionality of the DynamicArray class. On line 3 an instance of DynamicArray is created using the default constructor. This will result in an initial array length of 25 elements. Initially, its size will be zero because no references have yet been inserted. On line 5 a String object is added to the array and then printed to the console on line 6. The for statement on line 7 will insert enough Integer objects to test the array’s growth capabilities. The for statement on line 11 prints all the non-null elements to the console.

Evaluating DynamicArray

The DynamicArray class works well enough for your immediate needs but it suffers several shortcomings that will cause serious problems should you try to employ the DynamicArray class in more demanding situations. For example, although you can access each element of the array you cannot remove elements. You could add a method called remove() but what happens when the number of remaining elements falls below a certain threshold? You might want to shrink the array as well.

Another point to consider is how to insert references into specific element locations. When this happens you must make room for the reference at the specified array index location and shift the remaining elements to the right. If you plan to frequently insert elements into your custom-built DynamicArray class you will have a performance issue on your hands you did not foresee.

At this point you would be well served to take a break from coding and dive into the API documentation to study up on the Java Collections Framework. There you will find that all this work, and more, is already done for you!

The ArrayList Class To The Rescue

Let’s re-write the ArrayTestApp program with the help of the List interface and the ArrayList class, both of which belong to the Java collections framework. Example 17.3 gives the code. Figure 17-2 shows the results of running this program.

Example 17.3: ArrayTestApp.java (Mod 1)

 1     import java.util.*; 2 3     public class ArrayTestApp { 4       public static void main(String[] args){ 5         List da = new ArrayList(); 6         System.out.println("Array size is: " + da.size()); 7         da.add(new String("Ohhh if you loved Java like I love Java!!")); 8         System.out.println(da.get(0).toString()); 9         for(int i = 1; i<26; i++){ 10          da.add(new Integer(i)); 11        } 12        System.out.println("Array size is: " + da.size()); 13        for(int i=0; i<da.size(); i++){ 14           if(da.get(i) != null){ 15         System.out.print(da.get(i).toString() + ", "); 16          } 17        } 18        System.out.println(); 19       }//end main() method 20     }// end ArrayTestApp class definition

Figure 17-2: Results of Running Example 17.3

Referring to example 17.3 — only three changes were made to the original ArrayTestApp program: 1) the import statement now appears on line 1 to provide shortcut naming to the interfaces and classes of the java.util package, 2) the da reference declared on line 5 has been changed from a DynamicArray type to a List type, and 3) also on line 5, an instance of ArrayList is created instead of a DynamicArray.

If you compare figures 17-1 and 17-2 you will see that the output produced using an ArrayList is exactly the same as that produced using the DynamicArray. However, the ArrayList class provides much more ready-made functionality.

The use of a Java collections framework interface in the revised ArrayTestApp program also provides another point of flexibility. Because the da reference declared on line 5 is of type List, any collections framework class that implements the List interface can be used to actually perform the work. For example, suppose you decide that you will need to make lots of insertions and deletions of elements into the collection. Since ArrayList utilizes an array as its underlying data structure, just like DynamicArray, it is not best suited to perform under these conditions. However, by making one more small change to the ArrayTestApp program you can swap out the ArrayList with a LinkedList and thus solve the problem. Example 17.4 gives the revised code for the ArrayTestApp program. Figure 17-3 shows the results of running this program.

Example 17.4: ArrayTestApp.java (Mod 2)

 1     import java.util.*; 2 3     public class ArrayTestApp { 4       public static void main(String[] args){ 5         List da = new LinkedList(); 6         System.out.println("Array size is: " + da.size()); 7         da.add(new String("Ohhh if you loved Java like I love Java!!")); 8         System.out.println(da.get(0).toString()); 9         for(int i = 1; i<26; i++){ 10          da.add(new Integer(i)); 11        } 12        System.out.println("Array size is: " + da.size()); 13        for(int i=0; i<da.size(); i++){ 14           if(da.get(i) != null){ 15         System.out.print(da.get(i).toString() + ", "); 16          } 17        } 18        System.out.println(); 19      }//end main() method 20    }// end ArrayTestApp class definition

Figure 17-3: Results of Running Example 17.4

Referring to example 17.4 — the only change between this and the previous version of ArrayTestApp is the substitution on line 5 of LinkedList for ArrayList. As you can see from looking at figure 17-3 the results produced are exactly the same. The implementation differences, however, between the LinkedList and ArrayList classes are significant, but those differences are hidden from you since, to paraphrase an old saying, a List, by any other name, is still a List.

The Power Of Collections — Polymorphic Code

The last two versions of ArrayTestApp provide a glimpse of the potential power gained by proper use of collections framework classes. By targeting collections framework interfaces you can write code that works with any collection class that implements that interface. The term polymorphic code, as it applies to object-oriented programming, means writing code that relies on interfaces vs. implementations. Thus, objects with the same interface but different implementations can be used in your code and your code will continue to work as designed. (i.e, It will not break!)