ArrayList vs LinkedList
Both implement List: they keep insertion order, allow duplicates and allow null. The difference is the data structure underneath:
- ArrayList is a resizable array.
get(i)is instant (O(1)). Adding at the end is O(1) on average (it grows by 50% when full). Inserting or removing in the middle shifts the elements after it, which is O(n). - LinkedList is a doubly linked list of nodes.
get(i)walks from the nearer end (O(n)). Adding or removing at either end is O(1); in the middle it's O(1) only once you're already there with an iterator. It also implementsDeque.
In practice, use ArrayList. Modern CPUs are very fast at reading contiguous arrays and slow at chasing pointers, and every LinkedList node adds about 24 bytes of overhead. Even "insert in the middle" is often faster with ArrayList at realistic sizes. For queues and stacks, ArrayDeque beats LinkedList too.
Side by side
| ArrayList | LinkedList | |
|---|---|---|
| Structure | Resizable array | Doubly linked list of nodes |
| get(index) | O(1) | O(n) |
| Add at the end | O(1) on average | O(1) |
| Add or remove at the start | O(n): shifts everything | O(1) |
| Add or remove in the middle | O(n): shifts the rest | O(n) to reach the spot, O(1) to link |
| Memory per element | One reference (plus spare capacity) | A node with two extra pointers |
| Iteration | Very fast (cache-friendly) | Slower (pointer chasing) |
| Also implements | RandomAccess | Deque |
| Use it for | Almost everything | Rarely; prefer ArrayDeque for queues |
Example
List<String> names = new ArrayList<>(List.of("Asha", "Ravi", "Meera"));
names.get(2); // O(1): straight to the slot
names.add(1, "Kiran"); // shifts Ravi and Meera one place right
LinkedList<String> queue = new LinkedList<>(names);
queue.addFirst("Zoya"); // O(1)
queue.removeLast(); // O(1)
// The LinkedList trap: indexed loops are O(n²)
for (int i = 0; i < queue.size(); i++) {
System.out.println(queue.get(i)); // each get(i) walks the list again
}
for (String n : queue) System.out.println(n); // use an iterator (for-each) instead: O(n)Common mistake
Looping over a LinkedList with get(i). Every call walks the list from an end, so the loop is O(n²).
Under the hood
ArrayList starts with an empty array and allocates 10 slots on the first add, then grows to about 1.5× each time it's full; ensureCapacity and trimToSize let you manage that. The RandomAccess marker interface tells algorithms such as Collections.binarySearch that indexed access is fast. LinkedList's own author, Joshua Bloch, has joked that he never uses it.
Check yourself
What is the time complexity of get(i) on a LinkedList?
How this connects
Know these first
Where this leads
You've reached the end of this thread. Try a learning path for what's next.
Part of Java 8 and collections, practically.
Was this lesson helpful?
Finished reading? Mark it complete to track your progress.