11.2 List: ArrayList and LinkedList

Overview

List is an ordered collection that allows duplicate elements and provides positional access by index. The two most commonly used implementations are ArrayList (backed by a resizable array) and LinkedList (backed by a doubly-linked list).

1. ArrayList

ArrayList is the go-to List for most situations. It stores elements in a contiguous array internally, giving O(1) random access by index. When the array is full, it automatically resizes (typically to 150% of its current size).

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

// Creation
ArrayList<String> list = new ArrayList<>();         // empty, initial capacity 10
ArrayList<String> sized = new ArrayList<>(100);     // initial capacity 100 (optimization)
List<String> fromExisting = new ArrayList<>(List.of("a", "b", "c")); // copy from collection

// Adding elements
list.add("Alice");         // append to end
list.add("Bob");
list.add("Charlie");
list.add(1, "Dave");       // insert at index 1 (shifts others right)

System.out.println(list);  // [Alice, Dave, Bob, Charlie]
System.out.println(list.size()); // 4

// Accessing elements
System.out.println(list.get(0));        // Alice
System.out.println(list.get(list.size() - 1)); // Charlie (last element)
System.out.println(list.indexOf("Bob")); // 2

// Updating
list.set(0, "Alex");
System.out.println(list.get(0)); // Alex

// Removing
list.remove("Dave");              // remove by value
list.remove(0);                   // remove by index
System.out.println(list);         // [Bob, Charlie]

// Searching
System.out.println(list.contains("Bob"));   // true
System.out.println(list.contains("Zara"));  // false

// Iteration
for (String name : list) {
    System.out.println(name);
}
list.forEach(System.out::println);

ArrayList Performance

Operation	Time Complexity	Notes
`get(index)`	O(1)	Direct array access
`add(element)`	O(1) amortized	Occasional resize is O(n)
`add(index, element)`	O(n)	Shifts elements right
`remove(index)`	O(n)	Shifts elements left
`contains(element)`	O(n)	Linear scan

2. LinkedList

LinkedList stores elements as nodes, where each node holds data and references to the previous and next node. This gives O(1) add/remove at head and tail, but O(n) access by index.

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

LinkedList<String> linked = new LinkedList<>();

// Add to head and tail
linked.addFirst("First");
linked.addLast("Last");
linked.add("Middle");

System.out.println(linked); // [First, Last, Middle]

// Peek (without removing)
System.out.println(linked.getFirst()); // First
System.out.println(linked.getLast());  // Middle

// Remove from head and tail
System.out.println(linked.removeFirst()); // First
System.out.println(linked.removeLast());  // Middle
System.out.println(linked);              // [Last]

LinkedList Performance

Operation	Time Complexity	Notes
`get(index)`	O(n)	Must traverse from head
`addFirst() / addLast()`	O(1)	Direct pointer update
`removeFirst() / removeLast()`	O(1)	Direct pointer update
`add(index, element)`	O(n)	Must find position first
`contains(element)`	O(n)	Linear scan

3. ArrayList vs LinkedList — When to Use What

Scenario	Winner	Reason
Frequent random access by index	`ArrayList`	O(1) vs O(n)
Append to end	`ArrayList`	Better cache locality
Insert/delete at beginning	`LinkedList`	O(1) vs O(n)
Used as a stack or queue	`ArrayDeque`	Faster than both for this use case
Small lists (under ~100 elements)	`ArrayList`	Array overhead is negligible

In practice, ArrayList is the right default in nearly all cases. LinkedList is rarely faster due to poor cache locality from scattered heap objects.

4. Key List Methods

import java.util.*;

List<Integer> numbers = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9, 3, 7, 4, 6));

// Sorting
Collections.sort(numbers);                              // natural order
System.out.println(numbers);  // [1, 2, 3, 4, 5, 6, 7, 8, 9]

numbers.sort(Comparator.reverseOrder());                // reverse order
System.out.println(numbers);  // [9, 8, 7, 6, 5, 4, 3, 2, 1]

numbers.sort(Comparator.naturalOrder());                // back to ascending

// Sub-list
List<Integer> sub = numbers.subList(2, 5);              // [3, 4, 5] (view, not copy)
System.out.println(sub);

// Binary search (list must be sorted first!)
int idx = Collections.binarySearch(numbers, 7);
System.out.println("Index of 7: " + idx);              // 6

// Shuffle and reverse
Collections.shuffle(numbers);
Collections.reverse(numbers);

// Min and max
System.out.println(Collections.min(numbers));
System.out.println(Collections.max(numbers));

// Remove with condition (Java 8+)
numbers.removeIf(n -> n % 2 == 0);  // remove all even numbers
System.out.println(numbers);

// Transform all elements (Java 8+)
numbers.replaceAll(n -> n * 2);
System.out.println(numbers);

5. Creating Lists

import java.util.*;

// Mutable ArrayList (can add/remove)
List<String> mutable1 = new ArrayList<>(Arrays.asList("a", "b", "c"));
List<String> mutable2 = new ArrayList<>(List.of("a", "b", "c")); // Java 9+

// Immutable list (List.of — Java 9+, no null allowed)
List<String> immutable = List.of("a", "b", "c");
// immutable.add("d"); // throws UnsupportedOperationException

// Single-element list
List<String> single = Collections.singletonList("only");

// Empty list
List<String> empty = Collections.emptyList();
List<String> empty2 = List.of();

// N copies of same element
List<Integer> zeros = Collections.nCopies(5, 0);
System.out.println(zeros); // [0, 0, 0, 0, 0]

// Convert array to list
String[] array = {"x", "y", "z"};
List<String> fromArray = new ArrayList<>(Arrays.asList(array));
List<String> fromArray2 = List.of(array); // immutable, Java 9+

// Convert list to array
String[] backToArray = fromArray.toArray(new String[0]);

6. Sorting with Comparator

import java.util.*;

record Student(String name, int grade, double gpa) {}

List<Student> students = new ArrayList<>(List.of(
    new Student("Alice", 3, 3.8),
    new Student("Bob",   2, 3.5),
    new Student("Carol", 3, 3.9),
    new Student("Dave",  1, 3.7),
    new Student("Eve",   2, 3.6)
));

// Sort by grade ascending
students.sort(Comparator.comparingInt(Student::grade));

// Sort by grade ascending, then by GPA descending within same grade
students.sort(Comparator.comparingInt(Student::grade)
        .thenComparingDouble(Student::gpa).reversed()
        // Note: .reversed() reverses the entire chain — use carefully
);

// Better: explicit multi-key sort
students.sort(Comparator
        .comparingInt(Student::grade)
        .thenComparing(Comparator.comparingDouble(Student::gpa).reversed())
);

students.forEach(s -> System.out.printf("Grade %d | GPA %.1f | %s%n",
        s.grade(), s.gpa(), s.name()));

7. Practical Example: Student Management System

import java.util.*;
import java.util.stream.*;

public class StudentManager {

    record Student(String name, String subject, int score) {}

    private final List<Student> students = new ArrayList<>();

    public void add(String name, String subject, int score) {
        students.add(new Student(name, subject, score));
    }

    public void remove(String name) {
        students.removeIf(s -> s.name().equals(name));
    }

    public List<Student> getTopStudents(int limit) {
        return students.stream()
                .sorted(Comparator.comparingInt(Student::score).reversed())
                .limit(limit)
                .collect(Collectors.toList());
    }

    public double getAverageScore() {
        return students.stream()
                .mapToInt(Student::score)
                .average()
                .orElse(0.0);
    }

    public Map<String, List<Student>> groupBySubject() {
        return students.stream()
                .collect(Collectors.groupingBy(Student::subject));
    }

    public void printRanking() {
        System.out.println("=== Student Rankings ===");
        List<Student> sorted = new ArrayList<>(students);
        sorted.sort(Comparator.comparingInt(Student::score).reversed());

        for (int i = 0; i < sorted.size(); i++) {
            Student s = sorted.get(i);
            System.out.printf("%2d. %-10s [%s] %d points%n",
                    i + 1, s.name(), s.subject(), s.score());
        }
        System.out.printf("Class average: %.1f%n", getAverageScore());
    }

    public static void main(String[] args) {
        StudentManager mgr = new StudentManager();
        mgr.add("Alice",   "Math",    95);
        mgr.add("Bob",     "English", 87);
        mgr.add("Charlie", "Math",    92);
        mgr.add("Diana",   "English", 78);
        mgr.add("Eve",     "Math",    88);

        mgr.printRanking();

        System.out.println("\nTop 3:");
        mgr.getTopStudents(3).forEach(s ->
                System.out.println("  " + s.name() + " - " + s.score()));

        System.out.println("\nBy Subject:");
        mgr.groupBySubject().forEach((subject, list) -> {
            System.out.println("  " + subject + ":");
            list.forEach(s -> System.out.println("    " + s.name() + " " + s.score()));
        });
    }
}

Pro Tips

removeIf is safer and cleaner than a manual loop:

// WRONG: ConcurrentModificationException!
for (String s : list) {
    if (s.startsWith("A")) list.remove(s);
}

// CORRECT option 1: removeIf (Java 8+)
list.removeIf(s -> s.startsWith("A"));

// CORRECT option 2: Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().startsWith("A")) it.remove();
}

Pre-size ArrayList when you know the count:

// If you know you'll add 1000 elements, pre-size to avoid resizing overhead
List<String> list = new ArrayList<>(1000);

Overview​

1. ArrayList​

ArrayList Performance​

2. LinkedList​

LinkedList Performance​

3. ArrayList vs LinkedList — When to Use What​

4. Key List Methods​

5. Creating Lists​

6. Sorting with Comparator​

7. Practical Example: Student Management System​