What is the difference between ArrayList and LinkedList?

Differences between ArrayList and LinkedList can be summarized in following points:

  • ArrayList internally uses a resizable-array implementation of the List interface to store the elements. LinkedList is doubly-linked list implementation of the List and Deque interfaces.
    LinkedList implements Deque interface as well, so it provides queue like FIFO functionality through methods such as peek() and poll().
  • ArrayList can be created as empty list of initial capacity 10 by overloaded constructor, while LinkedList only constructs the empty list without any initial capacity.
  • Manipulation with ArrayList is slow in comparison to LinkedList because it internally uses an array. If any element is removed from the array, elements need to be shifted in memory. Manipulation with LinkedList is faster than ArrayList because it uses a doubly linked list.
  • Insertions are fast in LinkedList as compared to ArrayList because there is no need of resizing array and copying content to new array if array gets full. Adding n elements requires O(n) time in case of ArrayList.
    While insertion operation in LinkedList requires O(1). ArrayList also needs to be update its index if you insert something anywhere except at the end of array.
  • Since ArrayList is backed by array, search operation based on index is pretty fast compared to the LinkedList search operation.
    get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n).
  • In LinkedList each element maintains two pointers (addresses) which points to the both neighbor elements in the list. Hence removal of element only requires change in the pointer location in the two neighbor nodes (elements) of the node which is going to be removed. While In ArrayList all the elements need to be shifted to fill out the space created by removed element.
    LinkedList remove operation gives O(1) performance while ArrayList gives variable performance: O(n) in worst case (while removing first element) and O(1) in best case (while removing last element).
  • ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbor nodes hence there is memory overhead associated with LinkedList.
  • LinkedList can be iterated in reverse direction using descendingIterator() while there is no descendingIterator() in ArrayList.