What is the difference between ArrayList and LinkedList in Java?
Quick answer
ArrayList is backed by a resizable array with O(1) index access and O(n) insertion in the middle, while LinkedList is a doubly linked list with O(n) index access and O(1) insertion once you hold the node; in practice ArrayList is faster for most workloads.
ArrayList stores elements contiguously, which is cache-friendly, so iteration and get(i) are very fast. Adding at the end is amortised O(1); inserting or removing in the middle shifts the following elements.
LinkedList stores each element in a node with previous and next pointers, which costs extra memory and scatters nodes around the heap. Finding the element at position i requires walking the list. It only wins when you repeatedly add or remove at the ends or through an iterator. For queue and deque behaviour, ArrayDeque is usually a better choice than LinkedList.
Key points
- ArrayList: O(1) get, amortised O(1) add at end
- LinkedList: O(n) get, extra memory per element
- Default to ArrayList; use ArrayDeque for queues