java: Arrays vs ArrayLists vs Vectors vs LinkedLists

The question is which one to use and when? Which one is more efficient? Lets look into each one of them.

An array is basically a fixed size collection of elements. The bad point about an array is that it is not resizable. But its constant size provides efficiency. So arrays are better to use when you know the number of elements available with you.

ArrayList is another collection where the number of elements is resizable. So if you are not sure about the number of elements in the collection use an ArrayList. But there are certain facts to be considered while using ArrayLists.

=> ArrayLists is not synchronized. So if there are multiple threads accessing and modifying the list, then synchronization might be required to be handled externally.
=> ArrayList is internally implemented as an array. So whenever a new element is added an array of n+1 elements is created and then all the n elements are copied from the old array to the new array and then the new element is inserted in the new array.
=> Adding n elements requires O(n) time.
=> The isEmpty, size, iterator, set, get and listIterator operations require the same amount of time, independently of element you access.
=> Only Objects can be added to an ArrayList
=> Permits null elements

If you need to add a large number of elements to an ArrayList, you can use the ensureCapacity(int minCapacity) operation to ensure that the ArrayList has that required capacity. This will ensure that the Array is copied only once when all the elements are added and increase the performance of addition of elements to an ArrayList. Also inserting an element in the middle of say 1000 elements would require you to move 500 elements up or down and then add the element in the middle.

The benefit of using ArrayList is that accessing random elements is cheap and is not affected by the number of elemets in the ArrayList. But addition of elements to the head of tail or in the middle is costly.

Vector is similar to ArrayList with the difference that it is synchronized. It offers some other benefits like it has an initial capacity and an incremental capacity. So if your vector has a capacity of 10 and incremental capacity of 10, then when you are adding the 11th element a new Vector would be created with 20 elements and the 11 elements would be copied to the new Vector. So addition of 12th to 20th elements would not require creation of new vector.

By default, when a vector needs to grow the size of its internal data structure to hold more elements, the size of internal data structure is doubled, whereas for ArrayList the size is increased by only 50%. So ArrayList is more conservative in terms of space.

LinkedList is much more flexible and lets you insert, add and remove elements from both sides of your collection - it can be used as queue and even double-ended queue! Internally a LinkedList does not use arrays. LinkedList is a sequence of nodes, which are double linked. Each node contains header, where actually objects are stored, and two links or pointers to next or previous node. A LinkedList looks like a chain, consisting of people who hold each other's hand. You can insert people or node into that chain or remove. Linked lists permit node insert/remove operation at any point in the list in constant time.

So inserting elements in linked list (whether at head or at tail or in the middle) is not expensive. Also when you retrieve elements from the head it is cheap. But when you want to randomly access the elements of the linked list or access the elements at the tail of the list then the operations are heavy. Cause, for accessing the n+1 th element, you will need to parse through the first n elements to reach the n+1th element.

Also linked list is not synchronized. So multiple threads modifying and reading the list would need to be synchronized externally.

So the choice of which class to use for creating lists depends on the requirements. ArrayList or Vector( if you need synchronization ) could be used when you need to add elements at the end of the list and access elements randomly - more access operations than add operations. Whereas a LinkedList should be used when you need to do a lot of add/delete (elements) operations from the head or the middle of the list and your access operations are comparatively less.

Work Work Work ...

Have been working straight for 4 days... getting only 2-4 hours of sleep in the night.

Well, i am a hard worker, but not that hard. Now the question comes, what is the urgency for this hard work. And i would say, buddy, it is a difficult to maintain the product on which i am working. People call it RESDEX. Short form for "Resume Database Access". We have more than 55 lakh profiles as of today. And it is my job to ensure that everything works without any problem. Providing a search on such a huge database, and getting results in matter of seconds is a difficult task.

What the user sees is a search form (well actually 4 search forms). Which is the tip of the iceberg. What i have to see is the complete iceberg. And it is a big iceberg. Like my collegue says - "Har click ki alag kahani hai" (Every click has its own story).

This is the first time i am talking about my work over here. Though all i do is work and work. Actually i have done things in my life which i am proud of. Building system architecture block by block is something which is really very exciting.

Earlier i used to work for an organization named 3di systems. I worked on lots of projects over there, but my major contribution was in handling the website named as www.newgateway4u.com. And it was an MLM (Multi Level Marketing) website. Logic for the website was - in theoretical terms - a binary tree. To explain in layman terms, each user registered with the website had to pay a certain amount to get himself activated. And once activated, he had to work on getting active people below him. Each user can have at most one person on left and one on right. The tree used to look something like this

            Root
             |
            /            /             L    R
           \   /\  
            \ /             LR RL RR
             /
            RLL

And the site used to work as - if R is active and both RL & RR are active then some percentage of the activation fees used to be passed to R. So Root would get percentage of activation money from L, R, LR, RL, RR, RLL, if all of them are active. There used to be weekly calculations to extract the amount payble for all active users.

The owner of the site used to make money by taking what was remaining from giving out the percentages to eligible active people.

When i joined the project, there were 5000 users and the amount calculation time was 11 hours. The site was pathetically slow. And then I Joined. Moved the complete binary tree to a doubly linked list in memory. Everything became cool. Calculations that used to take 11 hours were done in 30 minutes. WOW!!

And then after 1 year of working with the site, i left the organization. When i left, the no of users were 50,000 and the weekly calculation time was 4 hours. Boy!! the code i wrote and how i handled the application architecture. The ideas that used to flow from me. I was good. And i am proud of myself.

And after that i joined Naukri. And worked over here. Handled servers, built up lots of applications. And finally got into resdex. The Baap of all applications. RESDEX started off with i dont remember how much, but we hit a bottleneck at 10 Lakh cvs. When we shifted the architecture to something better. I still remember the date. It was 11th june 2004. Things stabilized. And we kept on adding more features and cvs to the product. The product is going stable. But there is always a fear of what would happen once the number reaches something like 100 lakh. How will we be providing a search on such a large database.

Challenges are unlimited. And step by step evolution is the only way to adapt to them.

Cool yaar...

And currently i am just adding one more block to the architecture...
And it is a bit heavy block. Well all blocks are heavy... Right!!.

Wish that everything goes right and i get to sleep on Monday...