ArrayList — Use ArrayList and understand resizing...

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

Step 1 — Import and DeclareFirst, 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.

Step 2 — Add ElementsUse 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

Step 3 — Access by IndexRetrieve 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.

Step 4 — Remove an ElementRemove "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

Step 5 — Iterate with a for-each LoopPrint 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.

Key differences between Java arrays and ArrayList

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 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.

ArrayList in the broader Collections Framework

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

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

PROBLEM 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?

PROBLEM 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?

PROBLEM 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.

PROBLEM 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.

PROBLEM 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.

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.