As a java developer we always come across Collections. In interviews we say, I have always used ArrayList in my previous projects. But we may get tense if someone asks, why ?? Why ArrayList why not simple Arrays ?? Why not Linked List. Lets address the second question first.
Basics First:
1) Arraylist -
An arraylist used an array for internal storage. This means it's fast for random access (e.g. get me element #555), because the array index gets you right to that element. But then adding and deleting at the start and middle of the arraylist would be slow, because all the later elements have to copied forward or backward.
ArrayList would also give a performance issue when the internal array fills up. The arrayList has to create a new array and copy all the elements there. Each time the buffer is too small it will create a new one. Hence if we can guess the number of elements that we are going to have, then it makes sense to create a arraylist with that capacity during object creation (using the overloaded constructor or ArrayList)
ArrayList would also give a performance issue when the internal array fills up. The arrayList has to create a new array and copy all the elements there. Each time the buffer is too small it will create a new one. Hence if we can guess the number of elements that we are going to have, then it makes sense to create a arraylist with that capacity during object creation (using the overloaded constructor or ArrayList)
- Fast Random Access
- Adding values might be slow When you don’t know the amount of values the array will contain when you create it, a lot of shifting is going to be done in the memory space when the ArrayList manipulates its internal array.
- Slow manipulation When you’ll want to add a value randomly inside the array, between two already existing values, the array will have to start moving all the values one spot to the right in order to let that happen.
2) Linked List -
LinkedList is made up of a chain of nodes. Each node stores an element and the pointer to the next node. A singly linked list only has pointers to next. A doubly linked list has a pointer to the next and the previous element. This makes walking the list backward easier.
Linked lists are slow when it comes to random access. Getting element #555 means you have to walk either forward from the beginning or backward from the end (depending on whether 555 is less than or greater than half the list size), calling next or previous, until you get to that element.Linked lists are fast for inserts and deletes anywhere in the list, since all you do is update a few next and previous pointers of a node. Each element of a linked list (especially a doubly linked list) uses a bit more memory than its equivalent in array list, due to the need for next and previous pointers.
- Fast manipulation As you’d expect, adding and removing new data anywhere in the list is instantaneous. Change two links, and you have a new value anywhere you want it.
- No random access Even though the get(int) is still there, it now just iterates the list until it reaches the index you specified. It has some optimizations in order to do that, but that’s basically it.
3) when to use what ?
If you frequently add elements to the beginning of the List or iterate over the List to delete elements from its interior, you should consider using LinkedList. These operations require constant-time in a LinkedList and linear-time in an ArrayList. But you pay a big price in performance. Positional access requires linear-time in a LinkedList and constant-time in an ArrayList.
