From the free course Java Programming and Algorithmic Thinking Fundamentals on Lykke

Advanced Data Structures: ArrayList

Key concepts: ArrayList vs. Fixed-size Arrays · Dynamic Resizing · Automatic Element Shifting · ArrayList Methods (add, set, remove) · Generics (Basic usage)

Transitioning from fixed-size arrays to dynamic arrays using the Java ArrayList class.

Advanced Data Structures: ArrayList

In the landscape of computer science, the tension between memory efficiency and developer productivity often dictates the choice of data structures. While the standard array is the bedrock of contiguous data storage, its rigid nature—defined by a fixed size at the moment of instantiation—presents significant hurdles for modern software engineering. Enter the ArrayList.

The ArrayList is a part of the Java Collections Framework and serves as a resizable-array implementation of the List interface. It provides a sophisticated abstraction over the primitive array, offering the speed of index-based access while removing the manual labor of memory management and element shifting.

The Architecture of Fluidity: ArrayList vs. Fixed-Size Arrays

To understand the ArrayList, one must first appreciate the limitations of the primitive array (T[]). In Java, an array is a container object that holds a fixed number of values of a single type. The length of an array is established when the array is created; after creation, its length is immutable.

The Problem of Static Allocation

When you declare int[] data = new int[10];, the JVM allocates a contiguous block of memory for exactly ten integers. If your application suddenly needs an eleventh integer, you are forced into a manual "migrate and replace" pattern:

  1. Create a new, larger array.
  2. Copy all elements from the old array to the new one.
  3. Update the reference to point to the new array.
  4. Allow the old array to be garbage collected.

The ArrayList automates this entire lifecycle. It maintains an internal array (often called the backing array) and a counter variable, size, which tracks how many elements are currently "active" within that backing array.

Feature Primitive Array (T[]) ArrayList<T>
Size Fixed (Static) Dynamic (Resizable)
Flexibility Low; requires manual resizing High; grows automatically
Performance Slightly faster (no abstraction overhead) High, with occasional resizing cost
Type Support Primitives (int, double) and Objects Objects only (uses Wrapper classes)
Generics Does not support generics natively Fully supports Generics
Metadata Only .length Rich API (size(), isEmpty(), etc.)

Dynamic Resizing: The Amortized Analysis of Growth

The most critical feature of an ArrayList is its ability to grow. However, memory cannot simply "expand" into adjacent slots, as those slots might be occupied by other objects. Instead, the ArrayList uses a Geometric Expansion strategy.

The Mechanics of the Growth Algorithm

When an element is added via add(), the ArrayList first checks if the current size is equal to the capacity (the length of the internal backing array). If size == capacity:

  1. A new capacity is calculated. In the OpenJDK implementation, this is typically oldCapacity + (oldCapacity >> 1), effectively a 1.5x growth factor.
  2. A new array is allocated with this new capacity.
  3. The contents are transferred using Arrays.copyOf (which internally uses the highly optimized System.arraycopy).
  4. The new element is inserted into the first available slot.

Proof of Efficiency: Amortized Time Complexity

A common concern is that resizing is an $O(n)$ operation because every element must be copied. If we resize frequently, does the add() operation become slow?

Through Amortized Analysis, we can prove that the cost of $N$ insertions is $O(N)$, making the average cost per insertion $O(1)$.

Theorem: If a dynamic array grows by a constant factor $k$ (where $k > 1$), then a sequence of $N$ insertions takes $O(N)$ total time.

Derivation: Assume a growth factor of 2. Resizes occur at sizes 1, 2, 4, 8... $2^i$. The total work for $N$ insertions (where $N = 2^k$) is: $Total Work = N (insertions) + (1 + 2 + 4 + 8 + ... + N) (copies)$ The summation $1 + 2 + 4 + ... + N$ is a geometric series that sums to $2N - 1$. Therefore, $Total Work = N + 2N - 1 \approx 3N$. $3N / N = 3$, which is a constant $O(1)$.

If we had chosen to grow the array by a fixed amount (e.g., capacity + 1), the total work would be $1 + 2 + 3 + ... + N$, which is $O(N^2)$, leading to an unacceptable $O(N)$ per insertion.

Automatic Element Shifting

Unlike a linked list where nodes are scattered in memory, an ArrayList must maintain contiguity. This requirement introduces a performance trade-off when inserting or removing elements from the middle of the list.

The remove(int index) Operation

When an element is removed from the middle of an ArrayList, a "hole" is created. To maintain the contract of an array-based list, all elements to the right of the deleted index must be shifted one position to the left.

  1. Access: The element at index is saved to be returned.
  2. Shift: numMoved = size - index - 1. If numMoved > 0, the elements are shifted.
  3. Cleanup: The last element in the array is set to null to assist the Garbage Collector.
  4. Update: size is decremented.

The add(int index, E element) Operation

Similarly, inserting at a specific index requires shifting all subsequent elements to the right to make room.

Operation Best Case Worst Case Average Case Reason
add(e) $O(1)$ $O(n)$ $O(1)$ Amortized constant time; $O(n)$ only on resize.
add(i, e) $O(1)$ $O(n)$ $O(n)$ Inserting at the end is fast; at the start requires $n$ shifts.
remove(i) $O(1)$ $O(n)$ $O(n)$ Removing the last element is fast; the first requires $n$ shifts.
get(i) $O(1)$ $O(1)$ $O(1)$ Direct memory address calculation.
set(i, e) $O(1)$ $O(1)$ $O(1)$ Direct replacement at index.

Core Methods and Usage Patterns

The ArrayList API is designed for ease of use. Below are the primary methods used in daily development.

Implementation Example

import java.util.ArrayList;

public class InventoryManager {
    public static void main(String[] args) {
        // 1. Initialization with Generics
        ArrayList<String> tools = new ArrayList<>();

        // 2. Adding elements (Appends to end)
        tools.add("Hammer");
        tools.add("Screwdriver");
        tools.add("Wrench");

        // 3. Size vs. Capacity
        System.out.println("Current size: " + tools.size()); // Outputs 3

        // 4. Accessing elements (0-indexed)
        String primaryTool = tools.get(0); 

        // 5. Updating elements
        tools.set(1, "Impact Driver"); // Replaces Screwdriver

        // 6. Removing elements
        tools.remove(2); // Removes Wrench; size is now 2

        // 7. Iteration (Enhanced For-Loop)
        for (String tool : tools) {
            System.out.println("Tool: " + tool);
        }
    }
}

Generics and the Type Safety Paradigm

ArrayList utilizes Java Generics, denoted by the angle brackets <T>. This allows the list to be "parameterized" with a type, ensuring that the compiler can catch type mismatches at compile-time rather than throwing ClassCastException at runtime.

The Primitive Limitation and Wrapper Classes

ArrayList can only store Objects, not primitives. This is due to how Generics are implemented in Java (via Type Erasure), where the generic type is replaced by Object at runtime. Since primitives like int do not inherit from Object, they cannot be stored directly.

To solve this, Java provides Wrapper Classes and a mechanism called Autoboxing.

Primitive Wrapper Class Autoboxing Example
int Integer list.add(5); $\rightarrow$ list.add(Integer.valueOf(5));
double Double double d = list.get(0); $\rightarrow$ list.get(0).doubleValue();
boolean Boolean list.add(true);
char Character list.add('A');

Warning: While Autoboxing is convenient, it carries a performance penalty. In high-performance loops, creating thousands of Integer objects can lead to significant memory pressure and GC overhead compared to a primitive int[].

Advanced Iteration and Modification

While the enhanced for-loop is the standard for reading an ArrayList, it has a critical limitation: you cannot modify the list's structure (add or remove) while iterating over it. Doing so throws a ConcurrentModificationException.

The Iterator Pattern

To safely remove elements during iteration, one must use an Iterator explicitly.

ArrayList<Integer> scores = new ArrayList<>();
// ... populate scores ...

Iterator<Integer> it = scores.iterator();
while (it.hasNext()) {
    Integer score = it.next();
    if (score < 50) {
        it.remove(); // This is the safe way to remove during a loop
    }
}

Common Pitfalls and Best Practices

  1. The Capacity Lag: An ArrayList grows, but it rarely shrinks automatically. If you populate a list with 1,000,000 items and then remove 999,999 of them, the backing array still occupies memory for 1,000,000 items. Use trimToSize() to release that memory.
  2. Initial Capacity: If you know you will store 5,000 items, initialize the list with new ArrayList<>(5000);. This prevents the overhead of multiple resize/copy cycles.
  3. Off-by-One Errors in Removal: When removing elements in a standard for loop (not an iterator), the indices shift. If you remove index i, the next element moves to index i. If your loop then increments to i+1, you have skipped an element.
  4. Reference Semantics: ArrayList<T> stores references to objects. If you modify an object retrieved from a list, the object inside the list is modified (because they are the same object in memory).

Summary of Complexity

Method Time Complexity Notes
get(index) $O(1)$ Random access is the primary strength.
add(element) $O(1)$* Amortized constant time.
add(index, element) $O(n)$ Linear time due to shifting.
remove(index) $O(n)$ Linear time due to shifting.
indexOf(element) $O(n)$ Requires a linear search.
size() $O(1)$ Stored as a field.
Advanced Data Structures: ArrayList - Java Programming and Algorithmic Thinking Fundamentals - diagram 1
Advanced Data Structures: ArrayList - Java Programming and Algorithmic Thinking Fundamentals - diagram 1
Advanced Data Structures: ArrayList - Java Programming and Algorithmic Thinking Fundamentals - diagram 2
Advanced Data Structures: ArrayList - Java Programming and Algorithmic Thinking Fundamentals - diagram 2
Advanced Data Structures: ArrayList - Java Programming and Algorithmic Thinking Fundamentals - diagram 3
Advanced Data Structures: ArrayList - Java Programming and Algorithmic Thinking Fundamentals - diagram 3

Source Materials

Study Java Programming and Algorithmic Thinking Fundamentals on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of Java Programming and Algorithmic Thinking Fundamentals · Browse more course pages