A comprehensive guide to List in Java

We are taking a deep dive into Lists in Java and its two common implementations: ArrayList and LinkedList. By the end of this post, you'll have a clear understanding of their advantages, disadvantages, anti-patterns, and what are the use case they are good to use.

Table of contents

• ArrayList
  • Core Characteristics
  • Thread Safety & Concurrency
  • Common Pitfalls and best practices
  • Comparison with alternatives
  • Exception Handling
• LinkedList
  • Core architecture
  • Performance Characteristics
  • Thread Safety & Concurrency
  • Dequeue Operations
  • When to use LinkedList VS ArrayList
  • Common LinkedList Anti-Patterns
  • Exception Handling
  • Use case matrix and Best Practices
• Comparison and Summary: List
• References

A List is an ordered collection, where the user has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

• Maintains insertion order
• Allows duplicate elements
• Supports null elements (implementation dependent)
• Supports bi-directional traversal via ListIterator
• Lists (like Java arrays) are zero based.
• An ordered collection with precise control over element insertion positions
• Extends SequencedCollection<E>

Unlike sets, lists typically allow duplicate elements. More formally, lists typically allow pairs of elements e1 and e2 such that e1.equals(e2), and they typically allow multiple null elements if they allow null elements at all.

It is not inconceivable that someone might wish to implement a list that prohibits duplicates, by throwing runtime exceptions when the user attempts to insert them, but we expect this usage to be rare.

Unmodifiable Lists (using List.of() and List.copyOf()):

• Elements cannot be added, removed, or replaced
• Disallow null elements
• Are serializable if all elements are serializable
• Implement RandomAccess interface
• Are value-based (treat equal instances as interchangeable)

Common implementation of the list interface

ArrayList

Core Characteristics

Performance Profile

• Constant Time O(1): size(), isEmpty(), get(), set(), getFirst(), getLast(), removeLast(), iterator(), listIterator(), reversed()
• Amortized Constant Time: add(), addLast() - adding n elements requires O(n) time total
• Linear Time O(n): All other operations (search, insert at position, remove by index/object)
• Low constant factor compared to LinkedList

Memory Management

• Dynamic resizing: Capacity grows automatically as elements are added
• Growth policy: Not specified, but adding elements has constant amortized cost
• Capacity optimization: Use ensureCapacity(int) before bulk additions
• Memory trimming: Use trimToSize() to minimize storage after removals

Thread Safety & Concurrency

Not Thread-Safe

• Multiple threads accessing concurrently require external synchronization
• Synchronized wrapper: Collections.synchronizedList(new ArrayList(...))
• Must synchronize on wrapper object for iteration

Fail-Fast Iterators

• Throw ConcurrentModificationException on structural modification during iteration
• Structural modifications: add, remove, resize operations (not set())
• Use iterator's own remove()/add() methods for safe modification

Null Handling

• Permits null elements (unlike unmodifiable lists)
• Search operations use Objects.equals() for comparison

Cloning & Serialization

• clone() returns shallow copy (elements not cloned)
• Implements Serializable
• Implements RandomAccess marker interface

Common Pitfalls and best practices

Performance optimization

// Bad: Frequent insertions at beginning
for (int i = 0; i < 1000; i++) {
    list.add(0, element); // O(n) each time = O(n²) total
}

// Good: Use LinkedList for frequent insertions, or reverse logic
List<String> temp = new LinkedList<>();
for (int i = 0; i < 1000; i++) {
    temp.add(element); // O(1) amortized
}
Collections.reverse(temp); // O(n) once

Safe concurrent modification

// Bad: ConcurrentModificationException risk
for (String item : list) {
    if (condition) {
        list.remove(item); // Throws exception
    }
}

// Good: Use iterator's remove method
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String item = it.next();
    if (condition) {
        it.remove(); // Safe
    }
}

// Better: Use removeIf (Java 8+)
list.removeIf(condition);

Memory efficiency

// Good: Trim after bulk removals
list.removeIf(condition);
list.trimToSize(); // Reduce memory footprint

// Good: Pre-size collections
List<String> results = new ArrayList<>(inputSize);

Comparison with alternatives

ArrayList vs LinkedList

• ArrayList: Better for random access, iteration, memory efficiency
• LinkedList: Better for frequent insertions/deletions in middle

ArrayList vs Vector

• ArrayList: Unsynchronized, better performance
• Vector: Synchronized, legacy, generally avoid

ArrayList vs Unmodifiable Lists

• ArrayList: Mutable, allows nulls, larger memory footprint
• List.of(): Immutable, no nulls, optimized, value-based

Exception Handling

Common Exceptions

• IndexOutOfBoundsException: Invalid index access
• NoSuchElementException: getFirst()/getLast() on empty list
• ConcurrentModificationException: Concurrent structural modification
• NullPointerException: Null collection passed to constructor/addAll

Validation Patterns

// Safe access patterns
if (!list.isEmpty()) {
    String first = list.getFirst(); // Safe
}

// Bounds checking
if (index >= 0 && index < list.size()) {
    String element = list.get(index); // Safe
}

LinkedList

Core Architecture

Doubly-Linked List Implementation

• Node Structure: Each element contains data + forward/backward pointers
• Memory Layout: Non-contiguous memory allocation (unlike ArrayList)

Performance Characteristics

Time Complexities

• Constant Time O(1):
  • addFirst(), addLast(), removeFirst(), removeLast()
  • getFirst(), getLast(), peekFirst(), peekLast()
  • size(), isEmpty()
• Linear Time O(n):
  • get(index), set(index, element) - traversal required
  • add(index, element), remove(index) - traversal + insertion/deletion
  • indexOf(), lastIndexOf(), contains()

Index-Based Access Optimization

// LinkedList optimizes traversal by choosing shortest path
// For index < size/2: traverse from beginning
// For index >= size/2: traverse from end
E element = list.get(index); // Automatically optimized

Thread Safety & Concurrency

Not Thread-Safe

• No internal synchronization
• Synchronized wrapper: Collections.synchronizedList(new LinkedList<>())
• Must synchronize on wrapper object for iteration

Fail-Fast Iterators

// Bad: Will throw ConcurrentModificationException
for (String item : linkedList) {
    if (condition) {
        linkedList.remove(item); // Structural modification during iteration
    }
}

// Good: Use iterator's remove method
Iterator<String> it = linkedList.iterator();
while (it.hasNext()) {
    String item = it.next();
    if (condition) {
        it.remove(); // Safe structural modification
    }
}

Dequeue Operations

Stack operations

// LIFO (Last In, First Out)
linkedList.push(element);        // Add to front
String top = linkedList.pop();   // Remove from front

// Equivalent operations
linkedList.addFirst(element);    // Same as push()
String first = linkedList.removeFirst(); // Same as pop()

Queue operations

// FIFO (First In, First Out)
linkedList.offer(element);       // Add to end
String head = linkedList.poll(); // Remove from front

// Null-safe variants
String peek = linkedList.peek();      // Returns null if empty
String element = linkedList.element(); // Throws NoSuchElementException if empty

When to use LinkedList VS ArrayList

// Excellent for frequent insertions/deletions at ends
Deque<String> deque = new LinkedList<>();
deque.addFirst("item1");  // O(1)
deque.addLast("item2");   // O(1)

// Good for frequent insertions/deletions in middle (if you have iterator)
ListIterator<String> it = linkedList.listIterator(someIndex);
it.add(newElement);  // O(1) at iterator position

// Stack/Queue operations
Stack<String> stack = new LinkedList<>(); // Use as stack
Queue<String> queue = new LinkedList<>(); // Use as queue

LinkedList Disadvantages

// Poor for random access
String item = linkedList.get(1000); // O(n) - must traverse 1000 nodes

// Higher memory overhead per element
// Each node: data + 2 pointers (next/previous) + object overhead

Common LinkedList Anti-Patterns

Avoid random access

// Bad: O(n²) complexity
for (int i = 0; i < linkedList.size(); i++) {
    String item = linkedList.get(i); // Each get() is O(n)
    process(item);
}

// Good: O(n) complexity
for (String item : linkedList) {
    process(item); // Enhanced for-loop uses iterator
}

Avoid size based decisions

// Bad: Inefficient size checks in loops
while (linkedList.size() > 0) {  // size() is O(1) but unnecessary
    linkedList.removeFirst();
}

// Good: Direct empty check
while (!linkedList.isEmpty()) {
    linkedList.removeFirst();
}

Exception Handling

Common exceptions

• IndexOutOfBoundsException: Invalid index access (get(), set(), add(index), remove(index))
• NoSuchElementException: Empty list access (getFirst(), getLast(), removeFirst(), removeLast(), element(), pop())
• ConcurrentModificationException: Concurrent structural modification during iteration
• NullPointerException: Null collection in constructor

Safe Access patterns

// Safe first/last access
if (!linkedList.isEmpty()) {
    String first = linkedList.getFirst(); // Safe
    String last = linkedList.getLast();   // Safe
}

// Null-safe queue operations
String head = linkedList.poll();     // Returns null if empty
String peek = linkedList.peek();     // Returns null if empty

Use case matrix and Best Practices

Operation Type	LinkedList	ArrayList
Sequential Access	✅ Excellent	✅ Excellent
Random Access	❌ Poor O(n)	✅ Excellent O(1)
Insert/Delete at Ends	✅ Excellent O(1)	✅ Good (amortized)
Insert/Delete in Middle	✅ Good O(1) at position	❌ Poor O(n)
Memory Usage	❌ Higher overhead	✅ Lower overhead
Cache Performance	❌ Poor locality	✅ Excellent locality
Stack/Queue Operations	✅ Perfect fit	✅ Usable

LinkedList Best Practices

1. Use LinkedList when: Frequent insertions/deletions, stack/queue operations, unknown size with many modifications
2. Use ArrayList when: Random access needed, memory efficiency important, mostly read operations
3. Always use enhanced for-loops or iterators for traversal
4. Consider ArrayDeque for pure stack/queue operations (often better performance)
5. Synchronize externally for concurrent access
6. Use fail-fast behavior for debugging, not program logic

Comparison and summary: List

Hierarchy of the list interface

interface List
class LinkedList
class ArrayList
class Stack
class Vector

LinkedList ..|> List : implements
ArrayList ..|> List
Stack --|> Vector
Vector ..|> List

Use Case	ArrayList	LinkedList	Reason
Random Access (get/set by index)	✅ Choose	❌ Avoid	ArrayList: O(1) vs LinkedList: O(n)
Sequential Iteration	✅ Good	✅ Good	Both are O(n), ArrayList has better cache locality
Insert/Delete at Beginning	❌ Slow	✅ Choose	ArrayList: O(n) vs LinkedList: O(1)
Insert/Delete at End	✅ Choose	✅ Good	ArrayList: O(1) amortized vs LinkedList: O(1)
Insert/Delete in Middle	❌ Slow	✅ Choose (if you have position)	ArrayList: O(n) vs LinkedList: O(1) at iterator position
Memory Efficiency	✅ Choose	❌ Higher overhead	ArrayList: contiguous arrays vs LinkedList: node objects
Cache Performance	✅ Choose	❌ Poor locality	ArrayList: excellent cache locality
Stack/Queue Operations	✅ Usable	✅ Choose	LinkedList implements Deque interface
Unknown Size, Many Modifications	❌ May resize frequently	✅ Choose	LinkedList grows dynamically without copying

🧠 Recommendations

Default Choice: ArrayList

• Use ArrayList as your default List implementation
• Better performance for most common operations
• Lower memory overhead
• Better cache locality

Switch to LinkedList when:

• Frequent insertions/deletions at the beginning
• Using as a stack, queue, or deque
• Frequent insertions/deletions in the middle with iterator
• Unknown size with many structural modifications

Consider ArrayDeque when:

• Primary use case is stack or queue operations
• Often provides better performance than LinkedList for deque operations

Migration Path
When changing between implementations, ensure your code doesn't rely on implementation-specific behavior:

// Good: Program to interface
List<String> list = createList();  // Factory method

// Avoid: Direct implementation coupling  
ArrayList<String> arrayList = new ArrayList<>();  // Hard to change later

References

• https://docs.oracle.com/en/java/javase/25/docs/api//java.base/java/util/List.html
• https://docs.oracle.com/en/java/javase/25/docs/api//java.base/java/util/ArrayList.html
• https://docs.oracle.com/en/java/javase/25/docs/api//java.base/java/util/LinkedList.html