ArrayList — Use ArrayList and understand resizing conceptually - Java

SECTION 1

Historical Context & Motivation

When you first learn to program in Java, you encounter arrays — fixed-size containers that hold a set number of elements. Arrays are fast and simple, but they come with a frustrating limitation: you must know the exact size you need before you create one. If you guess too small, you run out of room; if you guess too large, you waste memory. This tension between flexibility and efficiency is one of the oldest challenges in computer science.

As software grew more complex in the 1990s, programmers needed data structures that could grow and shrink on demand. Java's designers addressed this need by including a rich set of collection classes in the language, with ArrayList becoming one of the most popular and widely used.

1995 • Java 1.0 Released

Sun Microsystems releases Java with the Vector class — an early resizable array that was thread-safe but slow for most use cases.

1998 • Java 1.2 — Collections Framework

The Java Collections Framework debuts, introducing ArrayList as a faster, non-synchronized alternative to Vector. This framework standardized how Java stores groups of objects.

2004 • Java 5 — Generics Arrive

Generics let programmers declare ArrayList<String> instead of raw types, adding compile-time type safety and eliminating tedious casting.

2014 • Java 8 — Streams & Lambdas

ArrayList gains powerful functional operations like forEach and stream(), making it even more versatile for modern programming tasks.

The central question ArrayList answers is simple yet critical: How can we have an array-like structure that grows automatically when we add more elements? Understanding the answer to this question will make you a more confident Java programmer and prepare you for AP Computer Science and beyond.

SECTION 2

Core Principles & Definitions

An ArrayList is a class in Java's java.util package that implements a resizable array. Unlike a regular array, an ArrayList can change its size at runtime. Under the hood, it still uses a plain array, but it manages the complexity of resizing for you. Here are the foundational ideas you need to know.

Dynamic Sizing

You don't specify a fixed length. When you call add(), the ArrayList grows as needed, handling memory behind the scenes.

Indexed Access

Like arrays, ArrayList supports random access by index using get(index) and set(index, value). Retrieval is fast — O(1) time.

Objects Only

ArrayList stores objects, not primitives. Use wrapper classes like Integer instead of int. Java auto-boxes for you in most cases.

Generics for Type Safety

Declare the type in angle brackets: ArrayList<String>. The compiler then prevents you from accidentally adding the wrong type.

Capacity vs. Size

Size is the number of elements currently stored. Capacity is how many elements the internal array can hold before it needs to grow.

✦

KEY TAKEAWAY

Think of an ArrayList like a notebook with removable pages. A regular array is like a notebook with a fixed number of pages — once you fill them, you're stuck. An ArrayList is like a binder: when you run out of pages, you can snap open the rings and add a whole new batch. You don't have to think about the binder's capacity most of the time, because it handles the expansion automatically.

SECTION 3

Visual Explanation — How ArrayList Stores Data

The diagram below shows the relationship between an ArrayList's internal array (capacity) and the elements you've actually added (size). Notice that the internal array often has extra empty slots beyond the last element.

The violet-shaded cells represent elements that have been added (the size), while the dashed cells are unused slots in the internal array (part of the capacity). The method cards below show the most common operations you'll use.

As the diagram illustrates, calling add() simply fills the next empty slot in the internal array. The size() method tells you how many elements are actually present, while the capacity is managed internally. You never access the capacity directly in normal code — Java handles it for you.

SECTION 4

How Resizing Works Under the Hood

The magic of ArrayList lies in its automatic resizing. When you add an element and the internal array is already full, Java performs the following steps: it creates a brand-new array that is roughly 1.5 times the old capacity, copies every existing element into the new array, and then adds your new element. The old array is discarded and eventually garbage-collected.

RESIZING FORMULA

newCapacity = oldCapacity + (oldCapacity >> 1)

The expression oldCapacity >> 1 is a bitwise right shift, which is equivalent to dividing by 2. So the new capacity is approximately 1.5 × oldCapacity. For example, a capacity of 10 grows to 15, then 22, then 33, and so on.

Why not just add one slot each time? Because copying the entire array is an expensive operation — it takes time proportional to the number of elements. If you grew by one slot every time you added an element, you'd copy the entire array for every single add() call once the array is full. By growing by a factor of 1.5×, the ArrayList ensures that resizing happens less and less frequently as the list gets bigger.

AMORTIZED COST OF ADD

Amortized time per add = O(1)

Even though a single resize costs O(n) time (copying n elements), this cost is spread out over many additions. On average, each add() takes constant time. This concept is called amortized analysis.

💡

Why 1.5× and not 2×?

Earlier implementations (like C++ vectors) often double the array. Java's ArrayList uses 1.5× to balance speed and memory usage. Doubling wastes more memory because the internal array can be up to twice as large as needed. The 1.5× growth factor is a compromise — it still avoids frequent resizing while keeping memory waste lower.

SECTION 5

Resizing in Action — Step by Step

Let's watch an ArrayList grow from empty to beyond its initial capacity. The diagram below traces what happens inside Java's memory as you keep calling add(). Pay close attention to the moment when the internal array is full and a resize is triggered.

Stage 1 shows an empty ArrayList with capacity 4. Stage 2 fills all four slots. At Stage 3, adding a fifth element triggers a resize: a new array of capacity 6 is created, the old elements are copied, and the new element is placed at index 4.

The growth sequence at the bottom of the diagram shows how capacity expands over time starting from Java's default of 10. Notice how the gaps between resizes get larger as the list grows. The first resize happens after just 10 adds, but once the capacity reaches 109, the ArrayList won't need to resize again until it holds 109 elements. This is the beauty of multiplicative growth — the bigger the list gets, the less often it pays the cost of copying.

SECTION 6

Worked Example — Building a Student Roster

Let's walk through a realistic scenario: building and manipulating a student roster using an ArrayList. We'll create the list, add names, access them, remove one, and iterate through the final result.

Building a Student Roster with ArrayList

1
Step 1 — Import and Declare

First, import the ArrayList class and declare a new list with a type parameter of String. import java.util.ArrayList; ArrayList<String> roster = new ArrayList<String>();

An empty ArrayList of Strings is created with default capacity 10.
2
Step 2 — Add Elements

Use the add() method to append names to the end of the list. roster.add("Alice"); roster.add("Bob"); roster.add("Carlos"); roster.add("Diana");

roster = ["Alice", "Bob", "Carlos", "Diana"], size = 4
3
Step 3 — Access by Index

Retrieve the student at index 2 using get(). Remember, ArrayList indices start at 0, just like arrays. String student = roster.get(2); System.out.println(student); // Output: Carlos

The value "Carlos" is returned from index 2.
4
Step 4 — Remove an Element

Remove "Bob" at index 1. All elements after the removed position shift left by one index. roster.remove(1); After removal, "Carlos" moves from index 2 to index 1, and "Diana" moves from index 3 to index 2.

roster = ["Alice", "Carlos", "Diana"], size = 3
5
Step 5 — Iterate with a for-each Loop

Print every name in the roster using Java's enhanced for loop. for (String name : roster) { System.out.println(name); }

Output: Alice, Carlos, Diana (each on its own line)

⚠

Watch Out!

When you remove an element, the indices of all elements after it shift down by one. If you're iterating with a traditional for loop and removing elements at the same time, you can accidentally skip elements or get an IndexOutOfBoundsException. A safe approach is to iterate backwards, or use an Iterator.

SECTION 7

Array vs. ArrayList — When to Use Which

Now that you understand how ArrayList works, you might wonder: when should you use a plain array instead? Both have their place. The table below compares the two structures across several dimensions to help you make informed choices in your programs.

Feature	Array	ArrayList
Size	Fixed at creation	Grows and shrinks dynamically
Type	Primitives and objects	Objects only (uses wrapper classes for primitives)
Syntax to access	`arr[i]`	`list.get(i)`
Length / Size	`arr.length` (field)	`list.size()` (method)
Adding elements	Manual — must manage index yourself	`add()` handles it automatically
Performance	Slightly faster (no method call overhead)	Negligible overhead for most applications
Best use case	Known, fixed number of elements	Unknown or changing number of elements

Key differences between Java arrays and ArrayList

✦

KEY TAKEAWAY

Think of a regular array like reserving a specific number of seats at a restaurant — if more friends show up, you're out of luck. An ArrayList is like a restaurant with flexible seating: they just pull up another table when your group grows. Use arrays when you know exactly how many items you need. Use ArrayList when the number could change.

SECTION 8

Connection to Advanced Data Structures

ArrayList is just one member of Java's Collections Framework. As you progress in computer science, you'll encounter other structures that solve different problems. Understanding where ArrayList fits in this larger picture will help you choose the right tool for each task.

Structure	Ordering	Duplicates	Best For
ArrayList	Maintains insertion order	Allowed	Fast random access by index
LinkedList	Maintains insertion order	Allowed	Frequent insertions/deletions in the middle
HashSet	No guaranteed order	Not allowed	Fast membership checks (contains)
HashMap	No guaranteed order	Unique keys, any values	Key-value lookups

ArrayList in the broader Collections Framework

In AP Computer Science A, you'll primarily work with ArrayList, but knowing about LinkedList and HashMap will give you context for why ArrayList makes certain tradeoffs. For instance, ArrayList is excellent for reading elements by index but slow for inserting in the middle (because all subsequent elements must shift). LinkedList handles mid-list insertions more efficiently but sacrifices fast random access. Each collection class represents a different balance of strengths.

ℹ

Looking Ahead

In college-level data structures courses, you'll study the internal mechanics of these collections in depth — hash tables, linked nodes, tree-based sets, and more. The resizing concept you learned here for ArrayList is a fundamental pattern that reappears in hash tables and other dynamic structures.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain the difference between the size and the capacity of an ArrayList. Why is it useful for the capacity to be larger than the size?

Show answer

The size is the number of elements that have actually been added to the ArrayList, while the capacity is the length of the internal array that stores those elements. The capacity is often larger than the size because it provides room for future additions without immediately triggering a resize. If the capacity equaled the size at all times, every single call to add() would require creating a new, larger array and copying all elements — a very expensive operation. By maintaining extra capacity, ArrayList ensures that most add() calls simply place the new element in the next open slot, which is fast (O(1) time).

Question 2: BASIC CALCULATION

An ArrayList is created with an initial capacity of 10. You add 10 elements, triggering a resize. Using the formula newCapacity = oldCapacity + (oldCapacity >> 1), what is the new capacity after the first resize? After the second resize?

Show answer

After the first resize: newCapacity = 10 + (10 >> 1) = 10 + 5 = 15. The ArrayList can now hold 15 elements before needing to grow again. After the second resize (when 15 elements are filled and the 16th is added): newCapacity = 15 + (15 >> 1) = 15 + 7 = 22. The bitwise right shift operator (>>) divides by 2 and rounds down. So the capacity progression starting from 10 is: 10 → 15 → 22 → 33 → 49, and so on.

Question 3: INTERMEDIATE

Consider the following code: ArrayList<Integer> nums = new ArrayList<Integer>(); nums.add(5); nums.add(10); nums.add(15); nums.add(20); nums.remove(1); nums.add(1, 25); nums.set(3, 30); What does the ArrayList contain after all these operations? Trace each step.

Show answer

Start: [5, 10, 15, 20]. After nums.remove(1): the element at index 1 (which is 10) is removed and elements shift left → [5, 15, 20]. After nums.add(1, 25): the value 25 is inserted at index 1, pushing 15 and 20 to the right → [5, 25, 15, 20]. After nums.set(3, 30): the element at index 3 (which is 20) is replaced by 30 → [5, 25, 15, 30]. The final ArrayList contains [5, 25, 15, 30] with a size of 4.

Question 4: APPLIED

You are writing a program that reads student test scores from user input until the user types -1. You don't know in advance how many scores there will be. Write the code using an ArrayList to store the scores, then compute and print the average. Explain why ArrayList is better than a regular array here.

Show answer

Here is the code: import java.util.ArrayList; import java.util.Scanner; Scanner scan = new Scanner(System.in); ArrayList<Double> scores = new ArrayList<Double>(); System.out.println("Enter scores (-1 to stop):"); double input = scan.nextDouble(); while (input != -1) { scores.add(input); input = scan.nextDouble(); } double sum = 0; for (double s : scores) { sum += s; } System.out.println("Average: " + sum / scores.size()); ArrayList is better than a regular array because we don't know how many scores the user will enter. With an array, we'd have to guess a maximum size (wasting memory or risking overflow). The ArrayList grows automatically as scores are added, handling any number of inputs gracefully.

Question 5: CRITICAL THINKING

Suppose you know in advance that your program will store exactly 1,000,000 strings. Would you use new ArrayList<String>() or new ArrayList<String>(1000000)? Explain the performance implications of each choice in terms of how many resize operations will occur and how much unnecessary copying takes place.

Show answer

You should use new ArrayList<String>(1000000). The default constructor creates an internal array of size 10. To reach 1,000,000 elements, the ArrayList would need to resize many times. Starting from 10 and growing by 1.5× each time: 10 → 15 → 22 → 33 → ... it takes roughly 40 resize operations to reach 1,000,000. Each resize copies all current elements to a new array, so collectively, millions of element copies occur. By pre-allocating with capacity 1,000,000, you create a single internal array large enough from the start, resulting in zero resize operations and zero unnecessary copies. This is a significant performance optimization when the size is known ahead of time. The lesson: ArrayList's flexibility is wonderful, but when you have knowledge about the expected size, use the capacity constructor to avoid wasted effort.

SUMMARY

Summary

Java's ArrayList is a resizable array from the java.util package that stores objects only (not primitives). You declare it with generics for type safety, such as ArrayList<String>. Key operations include add(), get(), set(), remove(), and size(). Internally, ArrayList uses a plain array; when that array fills up, it creates a new one approximately 1.5× the old capacity and copies elements over.

The distinction between size (elements stored) and capacity (internal array length) is fundamental: extra capacity reduces the frequency of expensive resize operations, giving add() an amortized O(1) running time. Use ArrayList when you need a flexible-size collection and plain arrays when the size is fixed. This concept is the gateway to Java's Collections Framework — a powerful toolkit you'll use throughout your programming career.