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:
- Create a new, larger array.
- Copy all elements from the old array to the new one.
- Update the reference to point to the new array.
- 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:
- A new capacity is calculated. In the OpenJDK implementation, this is typically
oldCapacity + (oldCapacity >> 1), effectively a 1.5x growth factor. - A new array is allocated with this new capacity.
- The contents are transferred using
Arrays.copyOf(which internally uses the highly optimizedSystem.arraycopy). - 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.
- Access: The element at
indexis saved to be returned. - Shift:
numMoved = size - index - 1. IfnumMoved > 0, the elements are shifted. - Cleanup: The last element in the array is set to
nullto assist the Garbage Collector. - Update:
sizeis 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
Integerobjects can lead to significant memory pressure and GC overhead compared to a primitiveint[].
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
- The Capacity Lag: An
ArrayListgrows, 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. UsetrimToSize()to release that memory. - 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. - Off-by-One Errors in Removal: When removing elements in a standard
forloop (not an iterator), the indices shift. If you remove indexi, the next element moves to indexi. If your loop then increments toi+1, you have skipped an element. - 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. |
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 sectionAll sections of Java Programming and Algorithmic Thinking Fundamentals · Browse more course pages