Java is the future !: ArrayList

Tuesday, September 7, 2010


While an array is a convenient way to store a lot of data, it requires you to specify the size in advance. Sometimes, we don’t know how many items we want to store. In this case, an ArrayList can be an excellent choice. Basically, an ArrayList acts like an array, except it grows automatically when it gets full. It allows you to efficiently access anything stored in it using a “get” method, to efficiently change the item stored at any location using a “set” method, and to add items with an “add” method. The “size” method returns how many items are currently in the ArrayList.

The method “readIntegers” shows how to create an ArrayList which will contain integers. ArrayList is a generic class, which means you can specify what kinds of things will be stored in it using less than(<), greater than(>). ArrayLists can’t store basic types, only classes, but each basic type has a corresponding class. For “int”, that is the class “Interger”. You’ll note Interger is capitalized, because it is the name of a class. Java automatically converts between “int” and “Interger” as required. As with all objects, we must call a constructor to create one. Then, while there are still more ints to be read from the scanner, we call the add method on “result”, our ArrayList object, to add them. At the end, we return result.

The method “reverse” demonstrates how to use “get” and “set”. This method loops through the first half of the array, getting one item from the first half and its corresponding item from the second half and swapping them. We set i to 0, then move the 0th entry to temp, move the right side to 0 and move temp to the right side. Then i becomes 1. We move the 1st entry to temp, move the right side to 1 and move temp to the right side. Then i becomes 2. We move the 2nd entry to temp, move the right side to 2 and move the temp to the right side. Now the loop is over and the entries are all reversed.

The methods “print” and “alternatePrint” show two different ways of priniting all of the elements in the ArrayList. Print use a regular for loop that counts from 0 to size-1, and then does a get on the ith element of the ArrayList. “alternatePrint”, however, uses a special kind of Java for loop, called an “iterator”. Here “Interger value colon list” means there will be one iteration for each item in the ArrayList, and value will, in turn, be the 0th, 1st, 2nd, though size minus 1st numbered item in the ArrayList. Both of the loops do exactly the same thing.

Click on the image to make it larger.


public class ArrayList
extends AbstractList
implements List, RandomAccess, Cloneable, Serializable

All the operations (get, set, size, isEmpty, iterator, listIterator) run in constant time excepting the "add" operation which runs in amortized constant time. To add n elements it takes O(n) time wheras other operatoins run in linear time.

Each and every instance of ArrayList has a capacity which denotes the size of the array used to store the elements in list. When an element is added in ArrayList it's capacity increases automatically. The addition of an element has constant amortized time cost.

The "ensureCapacity" operation can be used to increase the capacity of an ArrayList instance.

Consider a situation where multiple threads are accessing the same ArrayList instance concurrently and one of the thread is modifing that list, it must be synchronized externally.

Note : The modification must be structural i.e. addition/deletion of elements, explicitly resizing the backiarray.

Remember, setting the value of an element is not considered as a structural modification.

umm so back to the point - we saw that we have to synchronize externally and that is accomplished by synchronizing on some object that encapsulates the list. If no such object exists then "wrap" the list using the method named as "Collections.synchronizedList" and to prevent accidental unsynchronized access to list, this wrapping is done at creation time.

List list = Collections.synchronizedList (new ArrayList (...) ) ;

The iterators returned by "iterator" and "listIterator" methods are fail-fast. If list is modified (structurally) at any time after the iterator is created the "iterator" will throw a ConcurrentModificationException. (excepting iterator's own remove or add methods)


PS: fail-fast behavior of an iterator can't be guaranteed as it is. It throw ConcurrentModificationException on a best-effort basis, there are no guarantees in the presence of unsynchronized concurrent modification. Hence it would be wrong to write a program that depends on this exception for its correctness. Remember, the fail-fast behavior should be used only to detect bugs.

Edited by Rahul :
"Program to interfaces, not implementations" means try to use interface references wherever possible.
So in your first example it'd be better to write 
             List < Integer > result = new ArrayList < Integer >();
          and also returntype should be List < Integer >
List is an interface. ArrayList is a class that implements it. Thanks to subtyping polymorphism, superclass reference can point to subclass object. Use it here.
Second example.
Now see the reversal routine would be same irrespective of what type ArrayList is (Right) So generalize it!
It's generics. So
See this.

A is the type parameter. Notice the changes. Also there's already a reverse method in lib.

one useful thing You can initialize List concisely as
List list = Arrays.asList(5, 4, 2);
thats it!
no need to keep adding!
one more u might like, Suppose you want to make sure no one changes your list at runtime
Wrap it as unmodifiable collection.Assume there's a list called xs.
Wrap it as:
List ys = Collections.unmodifiableList(xs);
sometimes you dont want it to be changed at runtime.Like say I have a class Abc and it has a field xs which is a List Fine? So there's a method called getXs() If you directly return xs then client can screw that list.Your encapsulation breaks.

No comments:

Post a Comment