Skip to main content

Java collection series - ArrayList

Another general purpose implementation of List interface in Java is ArrayList.

Interfaces implemented - List, Collection, RandomAccess, Serializable, Cloneable, Iterable

Classes extends from - AbstractCollection, AbstractList

Structurally, it maintains an array to store the data. Initially the array is created with a size of 10 and when that limit is reached (which implies that the load factor is 1), a new array is created with 1.5 times the original arrays capacity and the data from the existing array is copied using System.arraycopy().

Features
  • provides random access
  • non-synchronized data structure (Collections.synchronizedList() can be used to reverse the behavior)
  • Iterator and ListIterator returned from ArrayList are fail-fast (throws ConcurrentModificationException when the structure changes by any method other than the iterators' methods)
  • insertion order is retained in ArrayList
  • has one tuning parameter initial capacity which refers to the size of the array before it grows
How good is the performance?
  • O(1) for searching as ArrayList maintains an index for each element which makes the searching an easy affair
  • Addition and deletion operations have O(n) as all the elements need to be repositioned in the array to fill once an element is added or deleted.
Comparatively low memory print as ArrayList maintains only element data and element indexes.


Comments

Post a Comment

Popular posts from this blog

Working in India

The day I started working in SRA India(Indian arm of Japan's Software Research Associates, Inc ), I never thought that I world become an onsite team member in just one and half years. Because, the branch was very small & it was very illogical for a novice like me to think of an onsite tour that time. But the fact was that they would make you do your work in almost Japanese style. The very first day I started coding in SRA India, I was told that the Japanese were simply put - perfectionists. This simple word had a very large inner meaning. The code that you wrote should be totally bug free, robust, modifiable without introducing regression etc. The first project I was assigned to, it took a hell lot days to prepare only the detailed design(Java Doc) for a very tiny function, every molecular level detail was described on that. But somehow I made myself adjusted to such work environment. My performance was good in my batch. And in one day, one of my managers told me of an onsite a...
Post a Comment
Read more

Java collection series - miscellaneous

Java Vector is a legacy class. And it is significantly faster in comparison to a list obtained through Collections.synchronizedList(). Vector has loads of legacy operations and hence the manipulations in Vector needs to be done through the List interface, otherwise you won't be able to replace the implementation at a later time. Arrays.asList() is better choice if the list is of fixed size and any kind of size mutation of the collection results in UnsupportedOperationException. The underlying array is updated whenever the list is updated (or vice-versa), but the array reference isn't retained. Collections.nCopies() is another convenient mini-implementation which can be useful in two ways - initialize a newly created list with n null values (need not be only null values) -  new ArrayList (Collections.nCopies(1000, (Type)null)  grow an existing list -  lovablePets.addAll(Collections.nCopies(69, "fruit bat")) Collections.singleton()/Collectio...
Post a Comment
Read more

DB transaction ACID properties

DB transaction is a combination of different operations. If not performed in a proper manner, different transactions working on the same data at the same time may leave the data in corrupted state, effecting the application. In this article, I am going to illustrate DB transaction ACID properties through an example of money transfer application between two different accounts A and B. To begin with, lets suppose that accounts A and B both have initial balance of $100. ACID stands for Atomicity , Consistency , Isolation and Durability . Let's try to understand these one by one. Atomicity : This is the property that mandates that if a transaction is started, either all the operations which are part of the transaction need to be completed by end of the transaction completion as a single unit of work or none of the operations needs to be completed. It is maintained by transaction management component. If a debit of $10 is made from account A, then the corresponding credit of $10 al...
Post a Comment
Read more