LinkedList<> over ArrayList<>?

LinkedList and ArrayList are two different implementations of the List interface of Java Collections Framework. LinkedList is implemented based on doubly-linked list where as ArrayList implements it with a dynamically resizing array.

These implementations differ in algorithmic runtime as shown below

For ArrayList

• Accessing Data : get(int index) - Constant time O(1) - Reading is faster which is main advantage of using ArrayList
• Adding new elements : 
• • End of list - add(E element) - If it fits into existing size of the list O(1). If the array is full and needs resize O(n) which is worst case
  • Add at a particular index (in between) - add(int index, E element) - This requires re indexing of all the elements after insertion position and hence in general O(n-index) and worst case will be O(n)
  • ListIterator.add(Element e) - Since we will adding at a position, it is same as adding an element at a index
• Remove an element:
• • remove(int index) - As with adding elements at a particular index, removing (if not last element) requires re indexing all the elements after the element which is removed. So, in general it is O(n-index) and worst case is O(n).
  • remove(Element e) - It is same as removing at an index.
  • Iterator.remove() - Same as removing at an index.

For LinkedList

• Accessing Data : get(int index) - O(n) - Reading is slower compared to ArrayList since we need to sequentially move towards the specified index to get the data.
• Adding new elements : 
• • add(E element) - constant time O(1) only if you happen to have a pointer to the location where you are inserting (index). Else O(n-index)
  • add(int index, E element) - O(n-index) and worst case is O(n)
  • ListIterator.add(E element) is O(1)  - mainly because you are already at the index of the element after which element will be added. This is the main advantage of Linked Liked over ArrayList.
• Remove an element:
• • remove(int index) - O(n) as we need to traverse to index and remove it. But we need not re index since only the pointers will be adjusted.
  • Iterator.remove() - O(1) same as ListIterator.add(E element). Again this is one of the main advantage over ArrayList.

As a conclusion,

LinkedList allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list.

ArrayList, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.

And one more important point to note here that memory requirements for LinkedList is more than ArrayList since it has to store the information about next and previous pointers. So, when we are looking at memory angle, we need to take this into consideration.

Choice of Data structure depends on specific use case and how we need to handle the add/remove and read operations on the data structure. During design, need to list all the possible uses of the data structure and finalize on optimized data structure to be used.