1. Introduction to ArrayList

This is appropriate when the expected number of elements is unknown or small. The list begins empty and allocates storage as needed. In OpenJDK implementations, the no-argument constructor may initially use a shared empty array and allocate storage on the first insertion. The exact internal strategy is an implementation detail, not a promise of the List interface.

3.2 Constructor with an initial capacity

The integer specifies an initial capacity, not the list’s size. The new list is still empty, so size() returns 0. The capacity hint is useful when a program expects to add many elements and wants to reduce intermediate resizing.

The requested capacity must not be negative; a negative value causes IllegalArgumentException.

3.3 Copy constructor

The copy constructor creates a new, mutable ArrayList containing the source collection’s elements in the source’s iteration order. This is a useful way to obtain a mutable list from an immutable list such as one created by List.of(...).

The copy is shallow: the list structure is new, but objects stored inside it are not cloned. If the elements are mutable objects, the source and copy still refer to the same element objects.

4. Core ArrayList Operations

The most common operations are appending, indexed insertion, indexed retrieval, indexed removal, and membership testing.

These are typical costs for ArrayList. The cost of equality comparisons can also depend on the element type and its equals() implementation.

4.1 Appending with add(element)

Appending places an element after the current last element. When the backing array has room, the operation writes into the next available slot and increases the size. If the array is full, the implementation must allocate a larger array and copy existing references.

Most appends are inexpensive, which is why the average cost over a long sequence of appends is amortized \(O(1)\). This does not mean every individual append is constant time.

4.2 Inserting with add(index, element)

Indexed insertion places the new element at the specified position. Existing elements from that position onward shift one place to the right. Inserting at index 0 in a long list may therefore move nearly every element.

A valid insertion index ranges from 0 through size(), inclusive. The index size() appends to the end; an index outside that range causes IndexOutOfBoundsException.

4.3 Reading with get(index) and replacing with set(index, element)

get(index) returns the element at a valid position. set(index, element) replaces the element already at that position and returns the old value. set does not change the list’s size because it replaces rather than inserts.

For both methods, a valid existing-element index ranges from 0 through size() - 1. An empty list has no valid index for get or set.

4.4 Removing by index or value

remove(index) removes the element at a position and returns it. The elements after that position shift left.

remove(object) searches for the first element equal to the supplied object and removes that occurrence. If no matching element exists, the list remains unchanged.

The distinction between these overloads is particularly important for numeric wrapper types.

5. The remove(int) Versus remove(Object) Trap

A list of integers has two remove overloads with different meanings:

• remove(int index) removes the element at the specified position.
• remove(Object value) removes the first element equal to the supplied value.

The compiler chooses the overload based on the argument’s type and the available method signatures. In the first call, the integer literal selects the index-based overload. Integer.valueOf(30) supplies an Integer object, selecting the value-based overload.

This is not unique to ArrayList; the same overload distinction applies to List<Integer> generally. Be explicit whenever the intent is to remove a numeric value rather than an index.

6. Size Versus Capacity

Size and capacity describe different things:

If the size is 3 and capacity is 10, only indices 0, 1, and 2 are valid for reading list elements. Unused capacity does not create additional list elements and cannot be accessed through get(3).

7. How ArrayList Resizes

When an insertion requires more space than the backing array provides, ArrayList grows its internal storage. Conceptually, the process is:

1. Allocate a larger backing array.
2. Copy existing element references into the new array.
3. Use the new array and store the incoming element.

The exact growth policy is an implementation detail. OpenJDK has commonly grown capacity by roughly one half of the old capacity, but code should not depend on a specific growth factor.

A resize can make one particular append \(O(n)\), because existing references must be copied. However, the backing array grows geometrically rather than by a fixed one-slot increment. The expensive copies are spread over many insertions, giving appends an amortized \(O(1)\) cost.

7.1 ensureCapacity(int)

ensureCapacity(minCapacity) asks the ArrayList to ensure that its backing storage can accommodate at least the requested capacity. It can be useful before a large batch of additions. It is a method of the concrete ArrayList class, not part of the List interface.

7.2 trimToSize()

trimToSize() asks the list to reduce its backing-array capacity to match its current size. It does not remove list elements or change size(). Trimming can reduce unused storage, but it may cause another allocation and copy if the list grows again later.

Use these methods only when there is a practical capacity or memory reason; ordinary application code often does not need to manage capacity directly.

8. Understanding ArrayList Time Complexity

The complexity of an operation follows from whether the backing array can access an index directly or must move/search through elements.

• Constant time, \(O(1)\): indexed access and replacement, because the slot is directly addressable.
• Linear time, \(O(n)\): searching with contains, inserting or removing near the beginning, and operations that must shift many elements.
• Amortized constant time, \(O(1)\): appending over a sequence of additions, even though an occasional resize is linear.

8.1 Why repeated front insertion can be expensive

If a program repeatedly inserts at index 0, each insertion shifts the elements already present. As the list grows, the amount of shifting per operation increases. Across many front insertions, total work can become quadratic.

If a workload frequently adds and removes at the ends, consider whether an ArrayDeque is a better fit. If indexed access is important, ArrayList is usually more suitable. A LinkedList has different trade-offs, but it does not make arbitrary indexed access fast.

9. Iterating Over an ArrayList

Three common iteration styles are an indexed for loop, an enhanced for-each loop, and an iterator-based loop.

9.1 Indexed loop

Use this form when the index is needed—for example, when displaying positions or comparing neighboring elements. It works efficiently with ArrayList because get(i) is \(O(1)\).

9.2 Enhanced for-each loop

Use this when the element values are needed but the index is not. It is concise and works through an iterator internally.

Do not structurally modify the same list directly inside a for-each loop. Doing so can trigger ConcurrentModificationException.

9.3 Iterator-based traversal

An Iterator supports sequential traversal and provides its own remove() operation. When elements need to be removed while iterating, use the iterator’s removal method or use removeIf, rather than calling products.remove(...) directly from a for-each loop.

10. ConcurrentModificationException and Fail-Fast Iterators

One of the most common beginner mistakes is removing an element directly from an ArrayList while an enhanced for-each loop is traversing it.

An ArrayList iterator is fail-fast. It tracks structural modifications—changes such as adding or removing elements—and checks for unexpected changes during traversal. If the list is structurally modified outside the iterator while that iterator is active, the iterator may throw ConcurrentModificationException.

Despite its name, this exception does not necessarily indicate multiple threads. A single thread can cause it by changing the list directly during iteration.

Fail-fast behavior is a bug-detection mechanism, not a synchronization guarantee. Programs should not rely on the exception to make concurrent access safe.

10.1 Safer option: Iterator.remove()

When using an iterator, remove through that iterator:

The iterator can keep its traversal state consistent when its own remove() method performs the removal.

10.2 Safer option: removeIf

For a condition-based removal, removeIf is often the clearest approach:

It expresses the intent directly: remove every element matching the predicate. This avoids manually changing the list from inside an enhanced for-each loop.

10.3 Indexed removal loop

An indexed loop can also be written to account for shifting, but it requires care. After removing at index i, the next element shifts into that same index. If the loop immediately increments i, it can skip the shifted element. Reverse traversal or explicit index adjustment can avoid that issue, but removeIf is usually easier to read for simple filtering.

10.4 Iteration decision flow

11. ArrayList Compared with Other Collection Types

ArrayList is a list implementation, not the best data structure for every task.

Choose based on the operations the program performs most often, rather than selecting a collection based only on its name.

12. Common Mistakes to Avoid

1. Confusing size with capacity. A capacity of 10 does not mean the list contains ten elements.
2. Assuming every append is \(O(1)\) in the worst case. A resize can make an individual append \(O(n)\); the amortized cost is \(O(1)\).
3. Using repeated front insertion on large lists. Each insertion may shift many elements.
4. Mixing up the remove overloads. remove(1) on List<Integer> removes index 1, not necessarily the value 1.
5. Modifying a list directly during for-each traversal. Use Iterator.remove() or removeIf.
6. Assuming a copy constructor deep-copies objects. It copies element references into a new list structure.
7. Depending on OpenJDK’s exact capacity growth factor. The implementation strategy can change.
8. Expecting set to add an element. set replaces an existing element and requires a valid current index.

13. Best Practices

• Prefer the interface type for variables and parameters when implementation-specific methods are not needed: List<String> products = new ArrayList<>();.
• Use ArrayList as a sensible default for ordered collections with frequent indexed access and iteration.
• Provide an initial capacity when the expected element count is known and large enough to make it worthwhile.
• Use removeIf for straightforward condition-based filtering.
• Use Iterator.remove() when removal is part of explicit iterator traversal.
• Use HashSet or HashMap when membership or key-based lookup is the main requirement.
• Treat capacity management methods as targeted optimizations rather than routine necessities.
• Keep the overload distinction between remove(int) and remove(Object) clear in code involving numeric values.

14. Quick Revision

• ArrayList<E> is a resizable-array implementation of List<E>.
• It preserves sequence order, supports duplicates, and uses zero-based indices.
• size() counts actual elements; capacity describes internal storage.
• get(index) and set(index, element) are typically \(O(1)\).
• Indexed insertion and removal can be \(O(n)\) because elements shift.
• add(element) is amortized \(O(1)\), with occasional linear-time resizing.
• contains and index-search methods are \(O(n)\) in general.
• remove(int) removes by index; remove(Object) removes by value.
• ensureCapacity and trimToSize belong to ArrayList, not the List interface.
• Avoid direct structural modification during for-each traversal; use Iterator.remove() or removeIf.

15. Conclusion

ArrayList is a practical default for most Java list requirements because it combines ordered storage, duplicate support, fast indexed access, and convenient collection operations. Its behavior becomes predictable once the backing array is understood: direct slot access is fast, shifting costs time, and occasional resizing supports continued growth.

The most important habits are to distinguish size from capacity, understand amortized append performance, select the correct remove overload, and use safe techniques when modifying a list during traversal. These concepts help developers choose ArrayList confidently and recognize when another collection type better matches the workload.