ArrayList in java [ ArrayList best explanations for interview point of view]

ArrayList in java [ArrayList Interview point of view]

ArrayList class is introduced in java 1.2, It is resizable-array implementation of the List interface, It can hold all type of element including null.

This class is somehow equivalent to Vector except that it is unsynchronised. The underlying data structure is Array.

Let's see the hierarchy of ArrayList class.

Performance

The size, isEmpty, get, set, iterator, and listIterator operations run in a constant time.

The add operation runs in gradually write off the initial constant time, that is, adding n elements requires O(n) time. 

All of the other operations run in linear time (roughly). 

  

Capacity 

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, it's capacity grows automatically. 

An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.

Thread Safety

The implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally*, It must be synchronized externally.

This can be accomplished by synchronizing on some object that naturally encapsulates the list.

If no such object exist, the list should be wrapped using the Collections.synchronizedList() method.

The best practice to do it at creation time, to prevent accidental unsynchronized access to the list.

eg :

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

* A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array merely setting the value of an element is not a structural modification.

Fail-Fast

The iterators returned by this class's iterator() and listIterator(int)  methods are fail-fast.  if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove() or ListIterator.add(Object) methods, the iterator will throw a ConcurrentModificationException.  Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behaviour at an undetermined time in the future.

The fail-fast behavior of an iterator cannot be guaranteed. Therefore, it would be wrong to write a program that depended on this exception for its correctness, the fail-fast behavior of iterators should be used only to detect bugs.

To be continue...