List #

Almost every real Java program needs to store collections of data — product lists, task queues, transaction histories, or query results from a database. Java provides the List interface along with several implementations, each designed for a different scenario. Choosing the wrong implementation won’t cause a program error, but it can make performance plummet drastically as data grows. This article covers the five most commonly used List implementations, how they work internally, the common operations available, and a guide to choosing the right one for your situation.

List Overview #

List is an interface in the Java Collections Framework that represents an indexed sequence of elements. Unlike Set, List allows duplicate elements and guarantees insertion order — element 0 is always first, element 1 second, and so on.

flowchart TD
    A["«interface»\nCollection"] --> B["«interface»\nList"]
    B --> C["ArrayList"]
    B --> D["LinkedList"]
    B --> E["Vector"]
    E --> F["Stack"]
    B --> G["CopyOnWriteArrayList"]

All List implementations share the same basic operations because they all implement the same interface. The difference lies in their internal workings and performance characteristics — not in the available API.

Declare variables with the interface type List, not the concrete type: List<String> list = new ArrayList<>() instead of ArrayList<String> list = new ArrayList<>(). That way you can swap implementations anytime without changing the code that uses it.

ArrayList #

ArrayList is the most commonly used List implementation. Behind the scenes, it stores elements in a plain array. When the array is full, Java automatically creates a new, larger array (usually 1.5× the previous size) and copies all elements into it.

Because it’s array-based, accessing an element by index is O(1) — very fast. But inserting or removing an element in the middle requires shifting all subsequent elements, which means O(n).

flowchart LR
    subgraph "ArrayList internal (capacity=6)"
        direction LR
        A["\"[0\"]\nApple"] --- B["\"[1\"]\nBanana"] --- C["\"[2\"]\nCherry"] --- D["\"[3\"]\n_"] --- E["\"[4\"]\n_"] --- F["\"[5\"]\n_"]
    end

Creating and Filling #

import java.util.ArrayList;
import java.util.List;

// Creating an empty ArrayList with a generic type
List<String> fruits = new ArrayList<>();

// Adding an element at the end — O(1) amortized
fruits.add("Apple");
fruits.add("Mango");
fruits.add("Orange");

// Adding an element at a specific index — O(n) because other elements must shift
fruits.add(1, "Banana"); // result: [Apple, Banana, Mango, Orange]

// Creating an ArrayList directly from another collection
List<String> copy = new ArrayList<>(fruits);

// List.of() produces an unmodifiable (immutable) list
List<String> fixed = List.of("One", "Two", "Three");

Reading and Searching #

// Index access — O(1)
String first = fruits.get(0);
String last = fruits.get(fruits.size() - 1);

// Check element existence — O(n)
boolean hasMango = fruits.contains("Mango"); // true

// Find an element's index — O(n)
int index = fruits.indexOf("Banana");         // 1
int lastTime = fruits.lastIndexOf("Apple"); // 0

// Size and emptiness checks
int count = fruits.size();    // 4
boolean empty = fruits.isEmpty(); // false

Modifying and Removing #

// Replace the element at a specific index — O(1)
fruits.set(0, "Watermelon"); // [Watermelon, Banana, Mango, Orange]

// Remove by index — O(n) because elements must shift
fruits.remove(2); // removes "Mango" → [Watermelon, Banana, Orange]

// Remove by value — O(n)
fruits.remove("Banana"); // [Watermelon, Orange]

// Remove all elements
fruits.clear();

// Remove elements matching a condition (Java 8+)
List<Integer> numbers = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
numbers.removeIf(n -> n % 2 == 0); // removes all evens → [1, 3, 5]

Iteration #

List<String> cities = new ArrayList<>(List.of("Jakarta", "Bandung", "Surabaya", "Medan"));

// For-each — most common and clean
for (String c : cities) {
    System.out.println(c);
}

// Classic for — when you need the index
for (int i = 0; i < cities.size(); i++) {
    System.out.println(i + ": " + cities.get(i));
}

// forEach with a lambda (Java 8+)
cities.forEach(c -> System.out.println(c.toUpperCase()));

// ANTI-PATTERN: removing elements during for-each — causes ConcurrentModificationException
for (String c : cities) {
    if (c.startsWith("B")) {
        cities.remove(c); // ✗ DON'T: throws ConcurrentModificationException
    }
}

// CORRECT: use removeIf — safe and clean
cities.removeIf(c -> c.startsWith("B")); // ✓

Sorting and Transformation #

import java.util.Collections;
import java.util.Comparator;

List<String> names = new ArrayList<>(List.of("Budi", "Ani", "Citra", "Doni"));

// Sort ascending (natural order)
Collections.sort(names); // [Ani, Budi, Citra, Doni]

// Sort descending
names.sort(Comparator.reverseOrder()); // [Doni, Citra, Budi, Ani]

// Sort by string length
names.sort(Comparator.comparingInt(String::length));

// Shuffle, reverse, and sub-list
Collections.shuffle(names);
Collections.reverse(names);
List<String> part = names.subList(1, 3); // elements at index 1 and 2 (a view, not a copy)

LinkedList #

LinkedList stores elements in interconnected nodes. Each node holds its own data plus references to the node before and after it (doubly linked). There’s no array behind the scenes — elements are scattered in memory and connected via pointers.

As a result, index-based access is slow (O(n) — must traverse from the start), but inserting or removing elements at the beginning or end is very fast (O(1)). LinkedList also implements the Deque interface, so it can be used as a queue or a stack.

flowchart LR
    A["null ←\nApple\n→"] <--> B["← Banana →"] <--> C["← Mango\n→ null"]

Regular List Operations #

import java.util.LinkedList;
import java.util.List;

List<String> queue = new LinkedList<>();
queue.add("Task A");
queue.add("Task B");
queue.add("Task C");

String element = queue.get(1); // "Task B" — but this is O(n)!
queue.remove(0);              // removes "Task A"

Special Operations at the Start and End #

This is LinkedList’s main strength — all of the following operations run in O(1).

LinkedList<String> ll = new LinkedList<>();
ll.add("Middle");

// Add at the start and end — O(1)
ll.addFirst("First");
ll.addLast("Last");
// result: [First, Middle, Last]

// Peek without removing
String head = ll.peekFirst(); // "First"
String tail   = ll.peekLast();  // "Last"

// Remove from the start and end — O(1)
String taken = ll.removeFirst(); // "First"
ll.removeLast();                   // "Last"

As a Queue #

// Use as a Queue: add at the back (offer), take from the front (poll)
LinkedList<String> queue = new LinkedList<>();
queue.offer("Wait 1");
queue.offer("Wait 2");
queue.offer("Wait 3");

String served = queue.poll(); // "Wait 1" — FIFO

Index Access Anti-Pattern #

LinkedList<Integer> data = new LinkedList<>();
for (int i = 0; i < 10000; i++) data.add(i);

// ANTI-PATTERN: get(i) on a LinkedList = O(n) × n iterations = O(n²) total
for (int i = 0; i < data.size(); i++) {
    System.out.println(data.get(i)); // ✗ very slow
}

// CORRECT: use for-each, which traverses pointers sequentially — O(n)
for (int value : data) {
    System.out.println(value); // ✓
}

Vector #

Vector is the oldest List implementation in Java — it has existed since Java 1.0, before the Collections Framework was born in Java 2. Its structure is nearly identical to ArrayList (dynamic array), but every method is synchronized (synchronized), meaning only one thread can access it at a time.

Basic Operations #

import java.util.Vector;
import java.util.List;

List<String> data = new Vector<>();
data.add("One");
data.add("Two");
data.add("Three");

String element = data.get(1); // "Two"
data.set(0, "Zero");
data.remove(2);
System.out.println(data.size()); // 2

Why It’s Not Recommended for New Code #

Its API is exactly the same as ArrayList, but method-level synchronization is coarse and expensive — every operation locks the entire structure even when not needed. Vector still exists in Java for backward compatibility reasons.

For new code, use ArrayList if single-threaded, or Collections.synchronizedList(new ArrayList<>()) and CopyOnWriteArrayList if you need thread safety. Vector is almost never recommended anymore.

Stack #

Stack is a subclass of Vector that adds stack operations (LIFO — Last In, First Out). The last element inserted is the first one taken — like a stack of plates.

flowchart TB
    subgraph Stack
        direction TB
        C["C ← top (push/pop here)"]
        B["B"]
        A["A ← bottom"]
    end

Push, Pop, and Peek Operations #

import java.util.Stack;

Stack<String> history = new Stack<>();

// push: add to the top of the stack — O(1)
history.push("Page 1");
history.push("Page 2");
history.push("Page 3");

// peek: look at the top element without removing — O(1)
String current = history.peek(); // "Page 3"

// pop: take and remove the top element — O(1)
String back = history.pop();   // "Page 3"

// Always check isEmpty before popping
if (!history.isEmpty()) {
    history.pop();
}

Real Example: Bracket Validation #

A classic stack scenario is checking the balance of brackets in a mathematical expression.

public static boolean balancedBrackets(String expression) {
    Stack<Character> stack = new Stack<>();

    for (char c : expression.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stack.isEmpty()) return false;
            char open = stack.pop();
            if (c == ')' && open != '(') return false;
            if (c == ']' && open != '[') return false;
            if (c == '}' && open != '{') return false;
        }
    }
    return stack.isEmpty();
}

System.out.println(balancedBrackets("(a + b) * [c - {d}]")); // true
System.out.println(balancedBrackets("(a + [b)]"));            // false

For stack implementations in new code, Java recommends Deque (usually ArrayDeque) over Stack. ArrayDeque is faster because it’s not synchronized, and its API is more explicit: push(), pop(), peek().

CopyOnWriteArrayList #

CopyOnWriteArrayList is a thread-safe implementation that uses a different strategy from Vector. Instead of locking all operations, it creates a full copy of the array every time a write operation happens (add, remove, change). Read operations are never blocked because they always read the existing array snapshot.

sequenceDiagram
    participant T1 as Thread 1 (read)
    participant T2 as Thread 2 (write)
    participant Arr as Array [A, B, C]

    T1->>Arr: read → gets [A, B, C] (not blocked)
    T2->>Arr: add "D" → creates a copy [A, B, C, D]
    T2->>Arr: replaces the reference with the new copy
    T1->>Arr: reads again → gets [A, B, C, D]

Basic Operations #

import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

List<String> listeners = new CopyOnWriteArrayList<>();
listeners.add("Listener A");
listeners.add("Listener B");
listeners.add("Listener C");

// Safe iteration — won't throw ConcurrentModificationException
// even if another thread is modifying the list at the same time
for (String l : listeners) {
    System.out.println("Notifying: " + l);
}

Real Example: Event Listener System #

CopyOnWriteArrayList<Runnable> eventHandlers = new CopyOnWriteArrayList<>();

eventHandlers.add(() -> System.out.println("Handler 1 called"));
eventHandlers.add(() -> System.out.println("Handler 2 called"));

// Run all handlers — safe to iterate even with concurrent additions
for (Runnable handler : eventHandlers) {
    handler.run();
}

When Not to Use It #

// ANTI-PATTERN: using CopyOnWriteArrayList for frequently changing data
CopyOnWriteArrayList<Integer> frequentlyChanged = new CopyOnWriteArrayList<>();

// ✗ DON'T: every add() creates a full array copy — very expensive
for (int i = 0; i < 10000; i++) {
    frequentlyChanged.add(i); // 10,000 array copies created!
}

// CORRECT: use it only when reads >> writes
// For frequent writes in multithreading, use Collections.synchronizedList()

Common Operations with Collections #

The Collections utility class provides many operations that work on all List implementations.

Searching and Statistics #

import java.util.Collections;

List<Integer> scores = new ArrayList<>(List.of(3, 1, 4, 1, 5, 9, 2, 6, 5, 3));

int max = Collections.max(scores);              // 9
int min  = Collections.min(scores);              // 1
int freq = Collections.frequency(scores, 5);     // 2 (the number 5 appears twice)

// Binary search — the list MUST be sorted first
Collections.sort(scores);
int index = Collections.binarySearch(scores, 6); // the index of element 6

Transformation and Protection #

// Creating an unmodifiable list
List<String> fixed = Collections.unmodifiableList(new ArrayList<>(List.of("A", "B")));
// fixed.add("C"); // throws UnsupportedOperationException

// Creating a thread-safe list from a regular ArrayList
List<String> threadSafe = Collections.synchronizedList(new ArrayList<>());

// Fill an entire list with one value
List<String> filled = new ArrayList<>(Collections.nCopies(5, "default"));
// result: [default, default, default, default, default]

// Swap the positions of two elements
Collections.swap(scores, 0, scores.size() - 1);

// Refill with new values
Collections.fill(scores, 0); // all elements become 0

Performance Comparison #

Understanding operation complexity helps you make the right decisions as data grows large.

*LinkedList needs O(n) to find the position, then O(1) for the pointer operation.

Decision Tree for Choosing an Implementation #

flowchart TD
    A{"Need random\nindex-based access?"} -- Yes --> B[ArrayList]
    A -- No --> C{"Frequent insert/delete\nat the start or end?"}
    C -- Yes --> D{"Need it as\na Queue or Deque?"}
    D -- Yes --> E[LinkedList as Deque]
    D -- No --> F[LinkedList]
    C -- No --> G{"Need\nthread safety?"}
    G -- No --> B
    G -- Yes --> H{"Reads far more\noften than writes?"}
    H -- Yes --> I[CopyOnWriteArrayList]
    H -- Balanced --> J["Collections.synchronizedList\nor Vector"]

When to Use Each Implementation #

Use ARRAYLIST when:
  ✓ It's the default choice — use it unless there's a specific reason otherwise
  ✓ You often access elements by index (get, set)
  ✓ Additions happen more often at the end than the middle
  ✓ You don't need thread safety

Use LINKEDLIST when:
  ✓ You often insert or remove elements at the beginning
  ✓ You need a Queue or Deque structure (FIFO or double-ended)
  ✗ Avoid it when you often access by random index

Use VECTOR when:
  ✗ There's almost no reason for new code
  ✓ You must interact with legacy code that expects a Vector

Use STACK when:
  ✓ You need an explicit LIFO structure
  ✓ DFS algorithms, undo/redo, expression parsing
  ✗ For new code, consider ArrayDeque as a replacement

Use COPYONWRITEARRAYLIST when:
  ✓ Many threads read, few write
  ✓ Event listener systems or observer patterns in concurrent environments
  ✗ Avoid it when writes are frequent — full array copies are very expensive

Summary #

• ArrayList is the default choice — dynamic-array based, O(1) index access, fits almost all general scenarios that don’t need thread safety.
• LinkedList excels at start/end operations — O(1) for addFirst, removeFirst, addLast, removeLast. It can also be used as a Queue and Deque. Avoid index access because it’s O(n).
• Vector is a legacy leftover — functionally the same as ArrayList but with coarse synchronization. Not recommended for new code.
• Stack follows the LIFO principle — push, pop, peek operations. Useful for DFS algorithms, undo/redo, and parsing. For new code, ArrayDeque is a faster replacement.
• CopyOnWriteArrayList for concurrent read-heavy workloads — every write creates a new array copy so reads are never blocked. Ideal for event listener systems, but expensive if writes are frequent.
• Declare with the List type — write List<String> list = new ArrayList<>(), not ArrayList<String> list = new ArrayList<>(). Flexibility to swap implementations without changing other code.
• Use removeIf instead of removing during iteration — removing elements during for-each throws ConcurrentModificationException. Use removeIf() or Iterator.remove().
• Collections provides complete utilities — sort, shuffle, reverse, binarySearch, frequency, unmodifiableList, and many more — all work on every List implementation.

← Previous: Interface   Next: Map →