ArrayList Vs LinkedList

The Java SDK contains 2 implementations of the List interface - ArrayList and LinkedList.A common design dilemma for developers is when to use what ?

Some basics first:
An arraylist used an array for internal storage. This means it's fast for random access (e.g. get me element #999), 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. (Using System.arrayCopy())

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. The ArrayList has a growth algorithm of (n*3)/2+1, meaning that each time the buffer is too small it will create a new one of size (n*3)/2+1 where n is the number of elements of the current buffer. 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 construtor or ArrayList)

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. Gettting element #999 means you have to walk either forward from the beginning or backward from the end (depending on whether 999 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.

Ok. Cool...Now that the fundamentals are clear, let's conclude on when to use what:

Here is a snippet from SUN's site.

The Java SDK contains 2 implementations of the List interface - ArrayList and LinkedList.
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.

Here are a few more links that give interesting perspectives:
http://www.javaspecialists.co.za/archive/Issue111.html
http://joust.kano.net/weblog/archives/000066.html
http://soft.killingar.net/documents/LinkedList+vs+ArrayList
http://jira.jboss.com/jira/browse/JBXB-65