ArrayList vs LinkedList in Java
Compare ArrayList vs LinkedList in Java: performance, time complexity, memory, and when to use each, with clear code examples and interview questions.
Expected Interview Answer
ArrayList is backed by a resizable array giving fast index-based access, while LinkedList is a doubly linked list giving fast insertion and deletion at the ends but slow random access.
ArrayList stores elements in a contiguous array, so get(index) is O(1), but inserting or removing in the middle shifts elements and costs O(n). LinkedList stores each element in a node with pointers to its neighbours, so add/remove at the head or tail is O(1), but reaching an arbitrary index requires walking the chain in O(n). In practice ArrayList wins for most read-heavy workloads because of cache-friendly memory and lower overhead, while LinkedList suits queue or deque usage with frequent end operations.
- ArrayList: O(1) random access by index
- ArrayList: lower memory overhead and cache-friendly layout
- LinkedList: O(1) insertion and removal at head or tail
- LinkedList: implements Deque for queue-style use
- Both implement the List interface and are interchangeable in client code
AI Mentor Explanation
An ArrayList is like a numbered set of stadium seats: jump straight to seat 42 instantly, but squeezing a new spectator into the middle forces everyone down a seat. A LinkedList is a human chain passing the ball hand to hand: adding a person at either end is trivial, yet reaching the tenth person means passing along one grip at a time.
Step-by-Step Explanation
Step 1
Compare the backing structure
ArrayList uses a resizable array; LinkedList uses a doubly linked chain of nodes.
Step 2
Weigh random access
ArrayList get(index) is O(1); LinkedList get(index) is O(n) because it walks from an end.
Step 3
Weigh insertion and deletion
LinkedList add/remove at ends is O(1); ArrayList middle inserts shift elements at O(n).
Step 4
Consider memory
ArrayList stores raw elements compactly; LinkedList adds node objects with two pointers each.
Step 5
Match to the workload
Pick ArrayList for read-heavy indexed access, LinkedList for queue or deque end operations.
What Interviewer Expects
- Correct Big-O for access, insertion, and deletion in both
- Understanding of contiguous array vs node-based memory
- Awareness that LinkedList implements Deque
- Knowledge of cache locality favouring ArrayList
- A clear recommendation for common real-world use cases
Common Mistakes
- Claiming LinkedList random access is O(1)
- Assuming LinkedList is always faster for insertion regardless of position
- Ignoring the memory overhead of LinkedList nodes
- Forgetting that mid-list ArrayList inserts require shifting
- Recommending LinkedList by default without a workload reason
Best Answer (HR Friendly)
“ArrayList is like a numbered list that is great when you often look items up by position, while LinkedList is like a connected chain that is great when you frequently add or remove items at the ends. For most everyday needs ArrayList is the safer, faster default.”
Code Example
import java.util.*;
public class ListComparison {
public static void main(String[] args) {
// ArrayList: fast index access
List<Integer> arrayList = new ArrayList<>(List.of(10, 20, 30));
int fast = arrayList.get(1); // O(1) -> 20
// LinkedList: fast end operations, usable as a queue/deque
LinkedList<Integer> linkedList = new LinkedList<>(List.of(10, 20, 30));
linkedList.addFirst(5); // O(1)
linkedList.addLast(40); // O(1)
int slow = linkedList.get(2); // O(n) walk from an end -> 20
System.out.println(fast); // 20
System.out.println(linkedList); // [5, 10, 20, 30, 40]
System.out.println(slow); // 20
}
}Follow-up Questions
- What is the time complexity of get, add, and remove for each?
- Why does ArrayList often outperform LinkedList despite the same Big-O?
- How does ArrayList grow when it runs out of capacity?
- When is LinkedList genuinely the better choice?
- How does cache locality affect list performance?
MCQ Practice
1. What is the time complexity of get(index) on a LinkedList?
LinkedList must traverse nodes from the nearest end to reach an index, giving O(n) access.
2. Which list is generally best for frequent random access by index?
ArrayList uses a contiguous array, so index access is O(1) and cache-friendly.
3. Which interface does LinkedList implement that ArrayList does not?
LinkedList implements Deque, making it suitable for queue and stack style end operations.
Flash Cards
ArrayList get(index) complexity? — O(1) — direct array indexing.
LinkedList get(index) complexity? — O(n) — it walks the node chain from the nearest end.
Which has lower memory overhead? — ArrayList; LinkedList adds a node object with two pointers per element.
When to prefer LinkedList? — When you frequently add or remove at the head or tail, e.g. queue or deque usage.