Generic Lists

Sample Application

The examples in this document all part of the Java Application GenericLists. Download the source archive
GenericLists.zip
Extract and install it as a Java Application with Existing Sources. See the Using NetBeans document for details.

Description

Java generics provides a way to parameterize types, say
class MyClass<T> { ... }
This allows the user to substitute an arbitrary Java Class for T when a MyClass object class is instantiated. Generics were introduced in Java 1.5. Prior to that point, the only notion of a generic type was using the Object class.

We will discuss how to create user-defined generic entities later, but initially we want to focus on how to use generics for our applications, specifically how to use generic lists.

The most common usages of generics are for the so-called Java Collections classes, representing the data structures in Java. The notion of collection in Java is simply the idea of an aggregate of common elements. The collection classes reside within the package:
java.util
One of the simplest ideas of an aggregate is a list of elements, like that which is provided by an array. There are two list-oriented classes provided by Java collections:
ArrayList<T>
LinkedList<T>
At the moment, the difference between these two is immaterial and we will focus on the ArrayList<T>.

ArrayList

The ArrayList class is just a "wrapper" around an array offering additional support features which makes it easy to use. There are a number of significant problems when you work with a raw array, for example: The ArrayList class solves all of these problems. It maintains an internal array as well as the current size and capacity data members within the class. If the size needs to exceed capacity, the array is automatically "resized" (we'll talk about that later) to a larger capacity by an internal operation done behind the scenes. The ArrayList also provides member operations and all the support code necessary for removal or insertion at arbitrary positions within the array.

Example: ArrayList of Integer

This sample program illustrates many of the member functions available to an ArrayList object.

genericlists.ArrayInts
package genericlists;
 
import java.util.ArrayList;
 
public class ArrayInts {
  public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
 
    list.add(33);
    list.add(55);
    list.add(77);
    list.add(88);
    list.add(22);
    list.add(55);
 
    System.out.println("list = " + list);
    System.out.println("list.size() = " + list.size());
    System.out.println("");
 
    System.out.println("list.get(2) = " + list.get(2));
 
    int previous = list.set(2,99);
    System.out.println("previous value in position 2 = " + previous);
    System.out.println("after list.set(2,99), list = " + list);
    System.out.println("");
 
    System.out.println("list.indexOf(55)     = " + list.indexOf(55));
    System.out.println("list.lastIndexOf(55) = " + list.lastIndexOf(55));
    System.out.println("list.contains(55)    = " + list.contains(55));
 
    System.out.println("list.indexOf(11)     = " + list.indexOf(11));
    System.out.println("list.lastIndexOf(11) = " + list.lastIndexOf(11));
    System.out.println("list.contains(11)    = " + list.contains(11));
    System.out.println("");
 
    list.add(0, 22);
    System.out.println("after list.add(0,22), list = " + list);
 
    Integer removed = list.remove(4);
    System.out.println("list.remove(4) = " + removed);
    System.out.println("after remove(pos), list = " + list);
    System.out.println("");
 
    boolean wasIn;
 
    wasIn = list.remove((Integer) 55);
    System.out.println("55 was in the list = " + wasIn);
    System.out.println("after remove(55), list = " + list);
 
    wasIn = list.remove((Integer) 66);
    System.out.println("66 was in the list = " + wasIn);
    System.out.println("after remove(66), list = " + list);
    System.out.println("");
 
    // mistakes:
    // wasIn = list.remove(55);
    // list.remove(55);
 
    int sum;
    sum = 0;
    for(int n: list) {  // or, for(Integer n: list)
      sum += n;
    }
    System.out.println("sum(list) forward = " + sum);
    System.out.print("priting backward:");
    for(int i = list.size()-1; i >= 0; --i) {
      System.out.print(" " + list.get(i));
    }
    System.out.println("");
    System.out.println("");
 
    System.out.println("list is empty = " + list.isEmpty());
    list.clear();
    System.out.println("after list.clear(), list = " + list);
    System.out.println("list is empty = " + list.isEmpty());
  }
}
select

ArrayList Operations

Let's examine the code closely. The operation we are describing belong to the class
class ArrayList<T> 
where T is a type parameter. This type must be an Object, not a primitive type. Many of the methods reference this type, making them generic as well.

Declaration and Instantiation

We start out with:
ArrayList<Integer> list = new ArrayList<>();  // 1.7+
Prior to Java 1.7, you had to write this:
ArrayList<Integer> list = new ArrayList<Integer>(); // 1.6, 1.5
Java 1.7 introduced the diamond operator "<>" which effects a type inference from the variable declaration
ArrayList<T> obj
to the instantiated object
= new ArrayList<>()
You can still use the pre-1.7 version in Java 1.7, but NetBeans will "suggest" that you use the diamond operator. Oddly enough, you can even drop the "generic part" on the right-hand side completely and Java will not care:
ArrayList<String> mylist = new ArrayList();
The reason is because

The add operator

The add operation adds elements to the end of the array. Java uses the terms first and last to designate the beginning and end of a list, respectively. So we would say that the add operation is doing an addLast. The prototype is in generic form:
boolean add(T elt);
The return value is always true for lists, indicating that the element is always successfully added. In Java Set data structures, add will avoid duplicates return false if the element is already present.

The toString override

With arrays, you have to go out of your way to print them. Of course you can write your own loop to print out the contents. If the array is full, you can use static functions from the java.util.Arrays class like this:
System.out.print( Arrays.toString(myArray) );
But if the array is not full you have to get fancier:
System.out.print( Arrays.toString(Arrays.copyOfRange(myArray, 0, size)) );
In contrast, the ArrayList hides whatever code it uses to convert to string and allows you simply to use:
System.out.println(list);

The size member function

For an array A, A.length gives the capacity, not how many positions are actually in use. Thus the size member function
int size();
is a crucial feature, capturing the value of the private size member which is correctly maintained by ArrayList operations.

The get and set member functions

The get and set member functions are used to provide equivalents of common array access operations:
x = A[pos]
A[pos] = y
They both are have generic prototypes:
T get(int pos);
T set(int pos, T elt);
The position must be in the range 0 to size-1. Retrieving the first and last elements would look like this:
first = list.get(0);
last = list.get(list.size()-1);
The set operation captures the previous value at the given position before setting the new value and then returns the previous value.

The search member functions: indexOf, lastIndexOf, contains

These member functions do a linear search of the array for a given element. The prototypes are:
int indexOf(Object obj);
int lastIndexOf(Object obj);
boolean contains(Object obj);
The searches are based on the Object-level equals operator comparisons. The indexOf function searches forward (first to last) for the element, returning the first position where it is found and -1 if not found. The lastIndexOf function searches in reverse. The contains function searches forward simply returns a boolean value indicating whether the object was found or not. Note that contains uses the Object type for its argument instead of the generic type.

The positional add member function

The positional add used in the code is the line
list.add(0, 22);
This operation is differentiated from the previous add by the number of arguments. It has the generic prototype:
void add(int pos, T elt);
In ArrayList, the effect is actually to insert the element at the position after shifting the entire array above that position one cell to the right, increasing the array size by 1.

The position can be between 0 and size, inclusive, meaning that you can call this:
list.add(list.size(), ELEMENT);
even though there is no element at position list.size(). The effect is to add the element to the end, creating the same outcome as
list.add(ELEMENT);

The positional remove member function

The positional remove member function uses this prototype:
T remove(int pos);
In the ArrayList, it has the opposite effect of positional add, capturing the value at the position prior to shifting the array above the position down one cell, overriding the current value at the position, reducing the array size by 1.

The object remove member function

The object remove member function has this prototype:
boolean remove(Object obj)
It searches forward for a match (according to the equals method) of the object and removes the first occurrence if found. The return value is true if the object was found (and removed) and false if not found.

Note the potential ambiguity between the positional and object remove functions precisely when the object type is Integer due to the strong relationship of Integer with the primitive type int. In this and only this case we must ensure that the object remove function is given an Integer and not an int which we do by explicitly casting to Integer:
// remove the Integer 55 found somewhere in the list
wasIn = list.remove((Integer) 55);
versus
// remove the object at position 55
list.remove(55);
This latter version which would fail because it attempts to assign the return value (an int) to a boolean.

List iteration

Computing the sum of all integers in the list gives us the opportunity to use the value-based for loop:
for(int n: list) {        // or, for(Integer n: list) 
  // do something with n
}
The same structure can be used for arrays, but only when the array is full so as to avoid null values. This for code is actually translated into something like this:
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
  int n = iterator.getNext();
  // do something with n
}
In particular, the relevant generic member function used implicitly is:
Iterator<T> iterator()
Going backwards through the list has no slick code. Make the indexes explicit and use the get function:
for(int i = list.size()-1; i >= 0; --i) {
  int n = list.get(i);
  // do something with n
}

The clear and isEmpty functions

The clear function simply sets the size to 0, thereby ignoring what is currently in the array. The isEmpty function simply tests to see if size is 0. Their prototypes are:
void clear();
boolean isEmpty();

Generic Interfaces

Interfaces as well as classes can be generic; they have to be generic if they are going to relate to generic classes. From the Inheritance for Interfaces section of the Inheritance document, we see that inheritance for interfaces simply means adding more prototypes.

With respect to lists, there are 3 relevant generic interfaces which apply, expressed by this hierarchy:
Namely:
Collection<T> extends Iterable<T>
List<T> extends Collection<T>
It simply means that at each stage of the inheritance hierarchy one adds the methods listed. The Collection and List contain other prototypes not mentioned here.
Iterable<T>
Iterator<T> iterator()
Collection<T>
boolean add(T) boolean contains(Object) boolean remove(Object) int size() void clear() boolean isEmpty()
List<T>
T get(int) T set(int,T) int indexOf(Object) int lastIndexOf(Object) void add(int,T) T remove(int)
The usage of the interfaces are these: Java provides two classes which implement the List<T> interface:
ArrayList<T>
LinkedList<T>
We will study both of these:

An ArrayList implements (among others) the List interface, i.e.,
class ArrayList<T> implements List<T>
Consequently it must also implement Collection<T> and Iterable<T>. Therefore it must implement all the functions shown above.

Using the interface as type declaration

In the demo program above we declared the object as:
ArrayList<Integer> list = new ArrayList<>();
It is actually more common to express the type as an interface instead of a class:
List<Integer> list = new ArrayList<>();
Doing so is usually more succinct, saying that "this object is only using list operations" and so could be instantiated by any class that satisfies the list interface, such as:
List<Integer> list = new LinkedList<>();
When using the collection classes it is common to do:
SomeInterface<SomeType> someObj = new SomeInterfaceImplementation<>();
We could also write this to signify that we only plan to use the Collection operations:
Collection<Integer> list = new LinkedList<>();
We can now explain fully the code presented in the Read a Text file Line-by-line section of the File I/O document. The slickest code which reads the lines of a text file in one step uses the Files class like this:
Path path = Paths.get(filename);
List<String> lines = Files.readAllLines(path);
What is retrieved is some implementation of the List interface. It's actually an ArrayList, which can be discovered by adding the line:
System.out.println(lines.getClass());

Avoid java.awt.List

Unfortunately, the List class appears in two packages:
java.util.List    (the one we want)
java.awt.List
The latter is the legacy graphical list, replaced by the swing component javax.swing.JList. In NetBeans, if you enter the declaration
List<Integer> list;
the line will be flagged as an error of missing type. Right-clicking on the error brings up a list of choices. In this case you should see two choices:
Add import for java.util.List
Add import for java.awt.List
Make sure to pick the right one.

An illustrative Interfaces example

This example illustrates declarations based on interfaces as well as the usage of other types, included a user-defined type. It also provides an important understanding about equality usage.

genericlists.User
package genericlists;
 
public class User {
  private final String name;
  private int age;
 
  public User(String name, int age) {
    this.name = name;
    this.age = age;
  }
 
  public void setAge(int age) {
    this.age = age;
  }
 
  @Override
  public String toString() {
    return String.format("(%s,%s)", name, age);
  }
 
  // user equality is based on name alone
  @Override
  public boolean equals(Object obj) {
    if (!(obj instanceof User)) {
      return false;
    }
    User user = (User) obj;
    return name.equals( user.name );
  }
 
  // the overloaded version doesn't work!!
//  public boolean equals(User user) {
//    if (user == null) {
//      return false;
//    }
//    return name.equals( user.name );
//  }
 
}

genericlists.UserInterfaces
package genericlists;
 
import java.util.List;
import java.util.Collection;
import java.util.ArrayList;
 
public class UserInterfaces {
  public static void main(String[] args) {
 
    // test users
    User jill = new User("Jill", 39);
    User john = new User("John", 39);
 
    // first test simple equality
    System.out.println("both tests must say true for Users to work in lists");
 
    System.out.printf("=> (Jill,10).equals( %s )\n", jill);
    System.out.println( new User("Jill",10).equals(jill) );
    System.out.printf("=> (Jill,10).equals( (Object) %s )\n", jill);
    System.out.println( new User("Jill",10).equals((Object) jill) );
    System.out.println();
 
    // a collection of Users: cannot use positional operations
    Collection<User> users1 = new ArrayList<>();
    users1.add(new User("Jules", 20));
    users1.add(new User("Rose", 22));
    users1.add(new User("Jill", 30));
    users1.add(new User("Bradley", 51));
    users1.add(new User("Robert", 44));
 
    System.out.println("-------------------------------");
    System.out.println("Collection: users1 = " + users1);
    System.out.println("-------------------------------");
 
    User[] testUsers = { john, jill };
 
    for (User user : testUsers) {
      System.out.printf("users1.contains(%s)=%s\n", user, users1.contains(user));
      System.out.printf("users1.remove(%s)=%s\n", user, users1.remove(user));
      System.out.println("afterwards: " + users1);
      System.out.println();
    }
 
    // a List of Users: collection and positional ops both apply
    List<User> users2 = new ArrayList<>();
 
    users2.add(new User("Jim", 20));
    users2.add(new User("John", 23));
    users2.add(new User("Linda", 33));
    users2.add(new User("Bill", 34));
    users2.add(new User("Rose", 15));
 
    System.out.println("-------------------------------");
    System.out.println("List: users2 = " + users2);
    System.out.println("-------------------------------");
 
    for (User user : testUsers) {
      System.out.printf("users2.contains(%s)=%s\n", user, users2.contains(user));
      int pos = users2.indexOf(user);
      System.out.printf("users2.indexOf(%s)=%s\n", user, pos);
 
      if (pos >= 0) {
        users2.remove(pos);
        System.out.printf("after remove(%s): %s\n", pos, users2);
        System.out.println();
      }
    }
    System.out.println("-------------------------------");
  }
}

Overridden vs. Overloaded Equals

This issue was discussed in the notes on Inheritance. Inheritance: Objects The overloaded equals method taken from the textbook works in some instances for specifying equality of objects. Unfortunately, it does not work when equality needs to be tested in list operations such as contains, remove, and indexOf!

We really need the overridden equals method with Object parameter type. Try it out for yourself, the overloaded code is there in the User class, commented out.

Specializations of the ArrayList

An ArrayList is based on an array, and so has aspects that differentiate it from the LinkedList, which, as we will see, has an entirely different underlying structure.

Array Capacity

For example the ArrayList supports an int constructor:
List<Integer> list = new ArrayList<>(100); 
The idea here is that, because it has an underlying array, you are dictating the initial capacity of that array. The reason that you would do so is that there is additional overhead whenever the underlying array reaches its capacity and must be enlarged. Specifying an initial capacity may ensure that the array will not have to be resized.

The ArrayList supports a few operations which are not part of the List interface, for example:
void ensureCapacity(int minCapacity)
This operation will check if the current capacity is at least minCapacity and if not, resize it to have capacity equal to minCapacity. If typed as a List we would have to cast it to use this operation, i.e.
List<Integer> list = new ArrayList<>();
...
((ArrayList<Integer>) list).ensureCapacity(250);

Other interfaces

The ArrayList has this declaration:
public class ArrayList<T> implements List<T>, Serializable, RandomAccess, Cloneable
We know about the Serializable interface. It is required to be provide the ability to write ArrayList objects to files. Implicit is that the generic T class also be serializable. For example, in the UseInterfaces demo program above we have:
class User {
  ...
}
...
Collection<String> names = new ArrayList<>();
...
List<User> users = new ArrayList<>();
...
The names object would be truly serializable, but the users object would not without adding the declaration:
class User implements java.io.Serializable {
  ...
}

The RandomAccess interface

The RandomAccess interface, like Serializable requires has no prototypes. It is a declaration that the positional get and set operations are "fast" in some sense and that they take the same amount of time regardless of the position used. It expresses one key advantage over the LinkedList class which does not have this characteristic.

The Cloneable interface

Cloning an object means to make a copy of that object with the same content which is "separate" from the original. Cloning refers to the Object-level operation The usage is a bit convoluted.
protected Object clone() throws CloneNotSupportedException
The protected qualifier means that you cannot clone an Object per se, but effectively you can clone a class which implements the Cloneable interface.

Cloing an ArrayList means to make an new ArrayList with copies of the elements. The function used is the Object-level clone function. The effect is this:
List<Double> nums = new ArrayList<>();
...
List<Double> nums1 = new ArrayList<>();
for( Double x: nums ) {
  nums1.add(x);
}
To use the clone operation you have to make sure that the object somehow declares its class. It is the type of nums is an interface, the class is only known to be Object, and clone will not work:
List<Double> nums = new ArrayList<>();
...
List<Double> nums1 = (List<Double>) nums.clone();
To fix this, we need to "tell" clone what is the class of nums like this:
List<Double> nums = new ArrayList<>();
...
List<Double> nums1 = (List<Double>) ((ArrayList<Double>)nums).clone();
In contrast, the procedure would work if nums were typed by the class instead of the interface:
ArrayList<Double> nums = new ArrayList<>();
...
List<Double> nums1 = (List<Double>) nums.clone();
The ArrayList class also has a copy constructor which achieves the same outcome as clone:
List<Double> nums = new ArrayList<>();
...
List<Double> nums1 = new ArrayList<>(nums);

Clone and Serialize Example

The following program illustrates aspects about ideas discussed in the program.

genericlists.OtherAspects
package genericlists;
 
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
 
public class OtherAspects {
  public static void main(String[] args) throws IOException {
    List<Double> nums = new ArrayList<>(100);
    //List<Double> nums = new LinkedList<>(100); // error
 
    nums.add(11.3);
    nums.add(-44.66);
    nums.add(115.22);
    System.out.println("nums  = " + nums);
    System.out.println();
 
    // write ArrayList object to file
    OutputStream ostr = new FileOutputStream("ArrayListDoubleData.dat");
    ObjectOutputStream oostr = new ObjectOutputStream(ostr);
    oostr.writeObject(nums);
    oostr.close();
 
    // duplicate nums in two ways and show the effects
    List<Double> nums1 = (List<Double>) ((ArrayList<Double>) nums).clone();
    //List<Double> nums1 = nums;
 
    nums1.set(1, 0.0);
 
    System.out.println("=> nums1 is a clone of nums");
    System.out.println("=> Reassign to postion 1 in nums1");
    System.out.println("nums1 = " + nums1);
    System.out.println("nums  = " + nums);
    System.out.println("=> observe that nums is unchanged");
  }
}

A Clone is still pretty shallow

With an array of objects, the clone only copies the references which point to the same objects as in the original array. Try the following example with the above User class.

genericlists.ShallowClone
package genericlists;
 
import java.util.ArrayList;
 
public class ShallowClone {
 
  public static void main(String[] args) {
    // make cloning easier by typing the variables by the class
    // instead of the interface
 
    ArrayList<User> users1 = new ArrayList<User>();
 
    users1.add(new User("John", 23));
    users1.add(new User("Mary", 24));
    users1.add(new User("Dave", 25));
 
    ArrayList<User> users2;
 
    // shallow copy vs. clone
    //users2 = users1;
    users2 = (ArrayList<User>) users1.clone();
 
    System.out.println("=> users2 is a clone of users1");
    System.out.println("users1 = " + users1);
    System.out.println("users2 = " + users2);
    System.out.println("");
 
    users2.set(0, new User("Alice",44));
    System.out.println("=> replace users2, element 0: users1 unaffected");
 
    System.out.println("users1 = " + users1);
    System.out.println("users2 = " + users2);
    System.out.println("");
 
    System.out.println("=> change age of users2, element 2: users1 affected");
    users2.get(2).setAge(77);
 
    System.out.println("users1 = " + users1);
    System.out.println("users2 = " + users2);
  }
 
}


© Robert M. Kline