What is the difference between ArrayList and LinkedList?
Question
Answer
# ArrayList vs LinkedList in Java - Complete Comparison Guide
## Overview
ArrayList and LinkedList are two fundamental List implementations in Java's Collections Framework. Understanding their differences is crucial for writing efficient Java programs and performing well in technical interviews.
---
## 1. Internal Implementation
### ArrayList:
- Data Structure: Dynamic array (resizable array)
- Storage: Elements stored in contiguous memory locations
- Growth: Automatically resizes when capacity is exceeded
- Default Capacity: 10 elements
- Growth Factor: Increases by 50% when full (newCapacity = oldCapacity + oldCapacity/2)
Internal Structure:
// Simplified ArrayList internals
class ArrayList<E> {
private Object[] elementData; // Array to store elements
private int size; // Current number of elements
private int capacity; // Current capacity
}
### LinkedList:
- Data Structure: Doubly linked list
- Storage: Elements stored as nodes with pointers to next and previous nodes
- Node Structure: Each node contains data, next pointer, and previous pointer
- No Capacity: No fixed size, grows dynamically
Internal Structure:
// Simplified LinkedList internals
class LinkedList<E> {
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
private Node<E> first; // First node
private Node<E> last; // Last node
private int size;
}
---
## 2. Time Complexity Comparison
| Operation |
| ArrayList |
| LinkedList |
| Winner |
| ----------- |
| ----------- |
| ------------ |
| -------- |
| Get by Index | O(1) | O(n) | ✅ ArrayList |
| Add at End | O(1) amortized | O(1) | ✅ LinkedList |
| Add at Beginning | O(n) | O(1) | ✅ LinkedList |
| Add at Middle | O(n) | O(n) | ⚖️ Tie (but LinkedList slightly better) |
| Remove from End | O(1) | O(1) | ⚖️ Tie |
| Remove from Beginning | O(n) | O(1) | ✅ LinkedList |
| Remove from Middle | O(n) | O(n) | ⚖️ Tie (but LinkedList slightly better) |
| Search by Value | O(n) | O(n) | ⚖️ Tie |
| Memory Overhead | Lower | Higher | ✅ ArrayList |
---
## 3. Detailed Operation Analysis
### Random Access (Get by Index)
ArrayList:
// Direct array access - O(1)
E get(int index) {
return elementData[index]; // Direct memory access
}
- ✅ O(1) time complexity - Direct array indexing
- ✅ Cache-friendly - Contiguous memory locations
- ✅ Very fast - Single memory access
LinkedList:
// Must traverse from head or tail - O(n)
E get(int index) {
Node<E> current = first;
for (int i = 0; i < index; i++) {
current = current.next; // Traverse nodes
}
return current.item;
}
- ❌ O(n) time complexity - Must traverse from beginning or end
- ❌ Cache-unfriendly - Non-contiguous memory
- ❌ Slower - Multiple memory accesses
Verdict: ArrayList wins decisively for random access.
---
### Insertion Operations
#### Insert at End
ArrayList:
// O(1) amortized, O(n) worst case (when resizing)
boolean add(E element) {
if (size >= capacity) {
resize(); // O(n) operation
}
elementData[size++] = element; // O(1)
}
- Amortized O(1) - Most of the time it's O(1)
- Worst case O(n) - When array needs resizing
- Resizing happens infrequently, so average is O(1)
LinkedList:
// Always O(1)
void add(E element) {
Node<E> newNode = new Node<>(element);
last.next = newNode;
newNode.prev = last;
last = newNode;
}
- ✅ Always O(1) - Just update pointers
- ✅ No resizing needed - Dynamic growth
Verdict: LinkedList is slightly better (guaranteed O(1) vs amortized O(1)).
---
#### Insert at Beginning
ArrayList:
// O(n) - Must shift all elements
void add(int index, E element) {
System.arraycopy(elementData, index,
elementData, index + 1,
size - index); // Shift elements
elementData[index] = element;
}
- ❌ O(n) time complexity - Must shift all elements
- ❌ Expensive operation - Especially for large lists
LinkedList:
// O(1) - Just update pointers
void addFirst(E element) {
Node<E> newNode = new Node<>(element);
newNode.next = first;
first.prev = newNode;
first = newNode;
}
- ✅ O(1) time complexity - Just pointer updates
- ✅ Very efficient - No element shifting
Verdict: LinkedList wins decisively.
---
#### Insert at Middle
ArrayList:
- O(n) time - Must shift elements after insertion point
- Memory efficient - No extra nodes created
LinkedList:
- O(n) time - Must traverse to find insertion point
- O(1) insertion - Once position found, just update pointers
- More efficient - No element shifting, just pointer updates
Verdict: LinkedList is slightly better (no shifting, just traversal).
---
### Deletion Operations
#### Remove from End
ArrayList:
// O(1) - Just decrement size
E remove(int index) {
E oldValue = elementData[index];
size--; // No shifting needed for last element
return oldValue;
}
- ✅ O(1) time complexity - Just size decrement
LinkedList:
// O(1) - Just update last pointer
E removeLast() {
Node<E> toRemove = last;
last = last.prev;
last.next = null;
return toRemove.item;
}
- ✅ O(1) time complexity - Just pointer update
Verdict: Tie - Both are O(1).
---
#### Remove from Beginning
ArrayList:
- ❌ O(n) time - Must shift all remaining elements left
LinkedList:
- ✅ O(1) time - Just update first pointer
Verdict: LinkedList wins.
---
#### Remove from Middle
ArrayList:
- ❌ O(n) time - Must shift elements after removal point
LinkedList:
- O(n) time - Must traverse to find element
- O(1) removal - Once found, just update pointers
- Slightly better - No element shifting
Verdict: LinkedList is slightly better.
---
## 4. Memory Usage
### ArrayList:
- Memory per element: ~8 bytes (object reference)
- Overhead: Array capacity (may have unused slots)
- Total: More memory-efficient for storing elements
- Cache locality: Excellent (contiguous memory)
Example:
ArrayList<String> list = new ArrayList<>();
// Memory: [ref1][ref2][ref3][null][null]...
// Even if only 3 elements, may have 10 slots allocated
### LinkedList:
- Memory per element: ~24 bytes (object reference + 2 pointers)
- Overhead: Node objects (next + prev pointers)
- Total: Less memory-efficient (3x more per element)
- Cache locality: Poor (non-contiguous memory)
Example:
LinkedList<String> list = new LinkedList<>();
// Memory: Node1 -> Node2 -> Node3
// Each node: [prev][item][next] = ~24 bytes
Memory Comparison:
- 1,000 elements:
- ArrayList: ~8,000 bytes (8 bytes × 1,000)
- LinkedList: ~24,000 bytes (24 bytes × 1,000)
- LinkedList uses 3x more memory
---
## 5. When to Use ArrayList
✅ Use ArrayList when:
1. Frequent random access - You need to access elements by index often
// Good for ArrayList
for (int i = 0; i < list.size(); i++) {
process(list.get(i)); // O(1) access
}
2. Mostly add/remove at end - Adding or removing elements primarily at the end
list.add(item); // O(1) amortized
list.remove(list.size() - 1); // O(1)
3. Memory efficiency matters - When memory usage is a concern
4. Iteration performance - Better cache locality for iteration
5. General-purpose lists - Default choice for most scenarios
Real-World Examples:
- Shopping cart items
- User lists
- Configuration settings
- Data that's mostly read, rarely modified
---
## 6. When to Use LinkedList
✅ Use LinkedList when:
1. Frequent insertions/deletions at beginning - Adding or removing from start
// Good for LinkedList
list.addFirst(item); // O(1)
list.removeFirst(); // O(1)
2. Frequent insertions/deletions in middle - When position is known
ListIterator<E> it = list.listIterator(index);
it.add(item); // O(1) after iterator positioning
3. Implementing stacks/queues - Natural fit for these data structures
// Stack: addFirst/removeFirst
// Queue: addLast/removeFirst
4. Unknown size - When you don't know the final size upfront
5. No random access needed - When you don't need index-based access
Real-World Examples:
- Undo/redo functionality
- Browser history
- Music playlists (frequent reordering)
- Task schedulers
---
## 7. Code Examples
### Example 1: Random Access (ArrayList Wins)
// ArrayList - O(1) per access
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
arrayList.add(i);
}
long start = System.nanoTime();
for (int i = 0; i < 1000000; i++) {
int value = arrayList.get(i); // O(1) - Very fast
}
long time = System.nanoTime() - start;
// Result: ~50ms
// LinkedList - O(n) per access
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 1000000; i++) {
linkedList.add(i);
}
start = System.nanoTime();
for (int i = 0; i < 1000; i++) { // Only 1000 for comparison
int value = linkedList.get(i); // O(n) - Very slow
}
time = System.nanoTime() - start;
// Result: ~5000ms (100x slower!)
### Example 2: Insertion at Beginning (LinkedList Wins)
// ArrayList - O(n) per insertion
ArrayList<Integer> arrayList = new ArrayList<>();
long start = System.nanoTime();
for (int i = 0; i < 10000; i++) {
arrayList.add(0, i); // O(n) - Shifts all elements
}
long time = System.nanoTime() - start;
// Result: ~2000ms
// LinkedList - O(1) per insertion
LinkedList<Integer> linkedList = new LinkedList<>();
start = System.nanoTime();
for (int i = 0; i < 10000; i++) {
linkedList.addFirst(i); // O(1) - Just pointer update
}
time = System.nanoTime() - start;
// Result: ~5ms (400x faster!)
---
## 8. Performance Tips
### For ArrayList:
1. Set initial capacity if you know the size:
ArrayList<String> list = new ArrayList<>(1000); // Avoid resizing
2. Use trimToSize() after adding all elements:
list.trimToSize(); // Remove unused capacity
3. Prefer enhanced for-loop for iteration:
for (String item : list) { // Fast iteration
process(item);
}
### For LinkedList:
1. Use ListIterator for efficient middle insertions:
ListIterator<String> it = list.listIterator(index);
it.add(item); // O(1) after positioning
2. Avoid get() in loops - Use iterator instead:
// Bad: O(n²)
for (int i = 0; i < list.size(); i++) {
process(list.get(i)); // O(n) each time
}
// Good: O(n)
for (String item : list) {
process(item); // O(1) per iteration
}
---
## 9. Common Interview Questions
### Q: Why is ArrayList generally preferred?
A: ArrayList is preferred because:
- Most operations involve random access (O(1) vs O(n))
- Better memory efficiency (3x less memory)
- Better cache locality (contiguous memory)
- Simpler implementation
- Most real-world use cases don't require frequent middle insertions
### Q: When would you choose LinkedList?
A: Choose LinkedList when:
- You frequently add/remove from the beginning
- You need to implement a stack or queue
- You don't need random access
- Memory overhead is not a concern
- You're using ListIterator for middle operations
### Q: Can LinkedList be faster than ArrayList?
A: Yes, in specific scenarios:
- Insertion/deletion at beginning: LinkedList O(1) vs ArrayList O(n)
- Insertion/deletion in middle (with iterator): LinkedList O(1) vs ArrayList O(n)
- However, for most common operations (random access, iteration), ArrayList is faster
---
## 10. Summary Table
| Aspect |
| ArrayList |
| LinkedList |
| Winner |
| -------- |
| ----------- |
| ------------ |
| -------- |
| Random Access | O(1) | O(n) | ✅ ArrayList |
| Insert at End | O(1) amortized | O(1) | ⚖️ Tie |
| Insert at Start | O(n) | O(1) | ✅ LinkedList |
| Insert at Middle | O(n) | O(n) | ⚖️ LinkedList (slightly) |
| Remove from End | O(1) | O(1) | ⚖️ Tie |
| Remove from Start | O(n) | O(1) | ✅ LinkedList |
| Memory Usage | Lower | Higher (3x) | ✅ ArrayList |
| Cache Locality | Excellent | Poor | ✅ ArrayList |
| Iteration Speed | Fast | Moderate | ✅ ArrayList |
| General Use | ✅ Recommended | Special cases | ✅ ArrayList |
---
## Conclusion
Default Choice: Use ArrayList for most scenarios. It's faster, more memory-efficient, and better suited for typical use cases.
Special Cases: Use LinkedList only when you have specific requirements:
- Frequent insertions/deletions at the beginning
- Implementing stack/queue
- No need for random access
Remember: The choice depends on your specific access patterns. Profile your code if performance is critical, but in 90% of cases, ArrayList is the right choice.