Friday, December 2, 2011

Lists (Java Collections)

What is a List in Java?

When we refer to a list in Java, we mean specifically a collection of objects that:

has a fixed order (when we add an object to the list, it will stay in the place we put it);
allows objects to be referred to by position, so we can get or set the "4th element in the list";
generally speaking, list does not have a fixed number of elements, unlike an array.

A plain old array has the first two of these properties, but not the third: when we create an array, we always have to say how many elements it has, and we can't change this number once the array is created. The third property isn't strictly speaking a necessary property of a Java List. But in practice, the most commonly used types of List are used instead of a plain old array because they have this "unbounded" property.

Using a List in Java:

As with Java collections generally, there isn't actually a single Java class called List. Instead, there is an interface called List, with various implementations. So a typical way to create a list would look like this:


import java.util.*;

List myList = new ArrayList();


In the above example, we import all classes from java.util, which is where List and ArrayList reside. In this example, the actual collection object that we create is an ArrayList. This is a list implementation that stores objects inside an array. Although arrays have to be fixed-size, ArrayList internally handles this by creating a new, bigger array where necessary and copying the previous elements into the new array. So to the caller, what we effectively get is a list with no fixed size which we can add to and remove from arbitrarily.

Notice that we also state, inside angle brackets, that the list will specifically hold objects of type String. If you haven't come across it before, this syntax was introduced in Java 5, part of what is technically called the generics framework.

Now we have our list, we can start doing interesting things with it such as adding and removing elements. Any List provides various methods, including add(), get(), size():


myList.add("Hello");
myList.add("Hello");
myList.add("world");
System.out.println("The list contains " +
   myList.size() + "elements, and " +
   "the first is " + myList.get(0));


Lists provide various other useful methods, such as for removing items from the list, adding at a specific position, or determining the first or last position of a particular item in the list.

Using collections in Java: enumerating items in a list:

Above, we began our tour of Java collections by looking at creating and using an ArrayList. We saw an example of how to add an item to the list, query the list's size (number of elements currently in the list) and fetch the nth element.

Another commonly needed operation is to enumerate or iterate through all of the items in the list. Now, one way we could do this would be with a plain old for loop: query the number of elements in the list, and then cycle through from 0 to that number minus one, pulling out the nth element on each cycle through the loop:


List myList = ...

for (int len = myList=size(), i = 0; i < len; i++) {
  String s = myList.get(i);
  System.out.println("Item " + i + " is " + s);
}


Note that rather than calling the size() method on every pass through the loop, we can read the size once and store it in a local variable. If anything, this is more of a programming idiom than a real performance gain: the overhead of calling size() isn't much for most collections, especially with modern JVMs that can inline the call.

A disadvantage of the method we just mentioned is that it assumes that for a particular list, the cost of finding the nth element is negligible. That's the case for an ArrayList, but not for a LinkedList, which has to 'cycle through the chain' to find the object at a given "index". From Java 5 onwards, the compiler can help us out by allowing us to use a special loop syntax:


for (String s : myList) {
  System.out.println("Next item: " + s);
}


The above code will create a loop that cycles through all the elements in the list, and on each cycle assigns the next element in the list to the variable s. Under the hood, the compiler will generate code that iterates through the list by effectively asking the list which iteration method to use.

No comments:

Post a Comment