Collections List — ArrayList, LinkedList, Vector, CopyOnWriteArrayList, and Iteration

In this tutorial, you will learn about Collections List. We cover key concepts, practical examples, and best practices to help you master this topic.

The List interface in Java represents an ordered collection that allows duplicate elements, with implementations optimized for different access patterns. Lists are the most commonly used collection type — every developer encounters them in their first week of Java programming.

What You'll Learn

• ArrayList: dynamic array with fast random access
• LinkedList: doubly-Linked List with fast insertions/deletions
• Vector: legacy thread-safe list
• CopyOnWriteArrayList: concurrent list for read-heavy workloads
• Iteration patterns and ConcurrentModificationException

Why It Matters

Choosing the wrong List implementation causes performance problems. Using ArrayList for frequent insertions at the front is O(n) per insertion; using LinkedList for random access is O(n) per lookup. Understanding the trade-offs ensures your collections perform well at scale.

Real-World Use

ArrayList backs most JSON arrays and result sets. CopyOnWriteArrayList is used in event listener registries. LinkedList implements double-ended queues.

The List Interface

List extends Collection and adds positional access:

List<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add(0, "Apricot"); // insert at position 0
int size = list.size();  // 3
String first = list.get(0); // "Apricot"
list.remove(1);          // removes "Apple"
list.remove("Banana");   // removes by object
boolean exists = list.contains("Apple"); // false
int index = list.indexOf("Apricot");     // 0

ArrayList

Backed by a growable array:

List<String> list = new ArrayList<>();         // initial capacity 10
List<String> sized = new ArrayList<>(100);     // pre-size for known volume
List<String> fromExisting = new ArrayList<>(otherList); // copy constructor

Time Complexity

Capacity Management

ArrayList<String> list = new ArrayList<>();
list.ensureCapacity(1000); // pre-allocate to avoid resizing
list.trimToSize();         // shrink internal array to current size

LinkedList

Backed by a doubly-linked list:

List<String> list = new LinkedList<>();
Deque<String> deque = new LinkedList<>(); // also implements Deque

Time Complexity

Queue Operations

LinkedList<String> queue = new LinkedList<>();
queue.addLast("First");
queue.addLast("Second");
queue.addLast("Third");
String first = queue.removeFirst(); // "First" — FIFO
String last = queue.removeLast();   // "Third" — LIFO

Vector

Legacy thread-safe list from Java 1.0:

Vector<String> vector = new Vector<>();
vector.add("Item");
String item = vector.get(0);

Vector is synchronized on every method, making it thread-safe but slow. It is considered legacy — use Collections.synchronizedList(new ArrayList<>()) or CopyOnWriteArrayList instead.

CopyOnWriteArrayList

A thread-safe variant where all mutative operations create a new copy of the underlying array:

List<String> list = new CopyOnWriteArrayList<>();
list.add("Item"); // creates a new array

When to Use

• Read-heavy workloads (many readers, few writers)
• Event listeners that change infrequently
• Iteration without locking — iterators never throw ConcurrentModificationException

Performance

Iteration Patterns

For-Each Loop

for (String item : list) {
    System.out.println(item);
}

Iterator

Use when you need to remove elements during iteration:

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    if (item.startsWith("A")) {
        iterator.remove(); // safe removal
    }
}

ListIterator

Bidirectional iteration:

ListIterator<String> li = list.listIterator(list.size());
while (li.hasPrevious()) {
    System.out.println(li.previous());
}

Streams

list.stream()
    .filter(s -> s.length() > 3)
    .forEach(System.out::println);

ConcurrentModificationException

Modifying a list while iterating (except via Iterator.remove()) throws ConcurrentModificationException:

List<String> list = new ArrayList<>(List.of("a", "b", "c"));
for (String s : list) {
    if (s.equals("b")) {
        list.remove(s); // throws ConcurrentModificationException
    }
}

Safe alternatives:

1. Iterator.remove()
2. list.removeIf(s -> s.equals("b")) (Java 8+)
3. Collect elements to remove, then remove them after the loop

Common Mistakes

1. Using get(int) on a LinkedList in a loop. for (int i = 0; i < list.size(); i++) list.get(i) is O(n^2) for LinkedList. Use for-each or iterator.
2. Modifying a list during for-each iteration. Use Iterator.remove() or removeIf().
3. Assuming ArrayList insertion at the beginning is O(1). add(0, element) shifts all elements — O(n).
4. Using Vector for new code. Prefer ArrayList or CopyOnWriteArrayList.
5. Forgetting to override equals() and hashCode() for custom objects. contains(), remove(Object), and indexOf() all use equals().

Practice Questions

1. When would you choose LinkedList over ArrayList?
When you frequently insert/remove at the beginning or middle, and rarely access by index. Also when you need a queue or deque.

2. What is the time complexity of get(int) for ArrayList and LinkedList?
ArrayList: O(1). LinkedList: O(n).

3. How does CopyOnWriteArrayList achieve Thread Safety?
Every mutative operation creates a new copy of the underlying array. Reads are never blocked and never require locking.

4. What causes ConcurrentModificationException?
Structural modification of a list (add, remove) while iterating over it, except through the iterator's own remove() method.

5. How can you remove elements during iteration safely?
Use Iterator.remove(), Collection.removeIf(), or collect elements to remove and remove them after the loop.

Challenge Question:
Write a method List<Integer> mergeSorted(List<Integer> a, List<Integer> b) that merges two sorted lists into one sorted list. Do not use Collections.sort() — use a two-pointer technique. Handle edge cases: empty lists, lists of different sizes, duplicate values.

FAQ

Mini Project

Write a program ListPerformance.java that:

1. Creates an ArrayList and LinkedList, each with 100,000 elements
2. Measures and compares get(0), get(middle), get(last), add(0, element), and iteration time
3. Creates a CopyOnWriteArrayList and demonstrates that iterators never throw ConcurrentModificationException by modifying in one thread while iterating in another
4. Uses ListIterator to traverse a list backward and replace every even-indexed element
5. Shows the proper way to remove elements: removeIf() vs iterator vs collecting removals

Print timing results in nanoseconds.

What's Next

Lists store ordered collections, but sometimes you need unique elements. Lesson 24 covers the Set interface and implementations — HashSet, TreeSet, LinkedHashSet, SortedSet, and NavigableSet — for collections with no duplicates and fast membership testing.