Java ArrayList and Collections: Operations, Traversals, and Algorithms

List Structure and Core Operations

An ArrayList<E> is an ordered, resizable collection of object references. Unlike an array, whose length is fixed after creation, an ArrayList can grow or shrink.

Important properties:

• Ordered: Each element has an index beginning at $0$.

• Resizable: Adding or removing elements changes the number of stored elements.

• Object-based: The collection stores objects rather than primitive values directly.

• Duplicate-friendly: Equal values may occur more than once.

• Mutable: Existing elements can be replaced, and the list's size can change.

A parameterized type such as ArrayList<String> tells the compiler what kind of objects the list should contain. Generics help detect incompatible values before the program runs. A variable may also use the List interface while the object is an ArrayList, allowing the implementation to be changed more easily later.

The basic operations have distinct purposes:

• add(value) appends an element.

• add(index, value) inserts an element and shifts the element previously at that index, along with later elements, to the right.

• get(index) returns an existing element.

• set(index, value) replaces an existing element without changing the size.

• remove(...) deletes an element and shifts later elements to the left.

For insertion, an index from $0$ through size() is valid; size() means insertion at the end. For access or replacement, the valid range is $0$ through $size() - 1$. An invalid index causes an IndexOutOfBoundsException.

Takeaway: Distinguish operations that change size, such as add and remove, from operations that preserve size, such as get and set.

Traversing and Inspecting Elements

A traversal visits list elements in a planned order. Choose the loop form according to whether the algorithm needs an index or changes the list.

An index-based for loop is appropriate when the position matters:

for (int i = 0; i < values.size(); i++)

The usual condition is $i < size()$, not $i \leq size()$. The last valid element is at index $size() - 1$, so using $i \leq size()$ eventually attempts an invalid access.

An enhanced for loop is convenient when the algorithm only needs each element:

for (String color : colors)

Do not add or remove elements from the list during an enhanced for traversal. Changing the list's size can cause a ConcurrentModificationException and can make the traversal incorrect.

A while loop is useful when the index update depends on what happens during each iteration. For example, if an element is removed, the next element shifts into the same index and may need to be examined before the index increases.

Search and inspection methods complement traversal:

• contains(value) reports whether an equal element is present.

• indexOf(value) returns the first matching index or $-1$.

• lastIndexOf(value) returns the last matching index or $-1$.

• isEmpty() reports whether the list contains no elements.

• clear() removes all elements.

Takeaway: Use enhanced for for simple read-only visits, and use an index-based or controlled while loop when positions or structural changes matter.

Safe Modification During Traversal

Removing or inserting elements changes the positions of later elements, so the loop must account for shifting.

Suppose adjacent negative values occur. If a left-to-right loop removes the value at index $i$ and then immediately increments $i$, the next value shifts into index $i$ and is skipped. This is a common traversal error.

Three reliable approaches are:

1. Traverse backward. Start at the last index and move toward $0$. Removing an element only shifts positions to the right, which have already been processed.

2. Control the index with a while loop. After removal, keep the same index so the newly shifted element is examined. Increase the index only when no removal occurs.

3. Build a new list. Add only the desired elements to a separate list while leaving the original unchanged.

Insertion requires similar care. Inserting at index $i$ shifts the old element at $i$ and all later elements one position right. If an algorithm inserts a value before an element and then continues forward, it must decide whether to process the inserted value, the original value, or both. The index update must reflect that decision.

A separate issue occurs when modifying an object inside a list: an ArrayList stores references. If two positions refer to the same mutable object, changing that object through one reference is visible through the other reference.

Takeaway: Whenever add or remove occurs during a traversal, explicitly track how the operation shifts indexes and how the next iteration should proceed.

Wrapper Types and Value Comparison

Collections store objects, so primitive types use corresponding wrapper classes. Common pairs include:

• int and Integer

• double and Double

• boolean and Boolean

• char and Character

• long and Long

Thus, a numeric list uses ArrayList<Integer>, not ArrayList<int>. Java performs Autoboxing when it converts a primitive such as an int into an Integer object. It performs Unboxing when it converts an Integer back to an int, for example during arithmetic.

Wrapper objects can be null, whereas primitives cannot. If Java tries to unbox a null wrapper, the program throws a NullPointerException, so code should ensure that a wrapper contains a value before relying on automatic conversion.

Wrapper objects are references. Therefore, use .equals to compare their values:

a.equals(b)

Using a == b compares object references rather than reliably comparing the numeric or logical values. The same value can be represented by distinct wrapper objects.

Takeaway: Know when Java is converting between primitives and objects, guard against null during unboxing, and use .equals for wrapper-value comparison.

Essential List Algorithms

Many list problems can be solved by one carefully designed traversal.

Aggregation and counting

For a sum, initialize an accumulator to $0$ and add every element. For an average, divide the total by the number of elements, but use a decimal result when needed, such as $\text{average} = \frac{\text{total}}{\text{size}}$. Handle an empty list according to the method specification before dividing.

For a minimum or maximum, initialize the candidate from the first element rather than automatically using $0$. A list containing only negative values shows why initializing a maximum to $0$ can be incorrect. This approach requires an explicit policy for an empty list.

For counting, start at $0$ and increment whenever an element satisfies the required condition. A condition such as “even” can be expressed with a remainder test: a value is even when $value \mathbin{\%} 2 = 0$.

Some versus all

To determine whether at least one element qualifies, return true as soon as a qualifying element is found; otherwise return false after the traversal. To determine whether all elements qualify, return false as soon as a violation is found; otherwise return true after the traversal. Check the specification for the intended behavior on an empty list.

Duplicates, pairs, and reversing

A duplicate check can compare each element with later elements only. For each index $i$, begin the inner comparison at $i + 1$, avoiding self-comparison and repeated pairs.

To inspect consecutive pairs, stop the starting index at $size() - 2$, because each iteration also accesses $i + 1$. To reverse a list in place, swap the elements at matching positions from the two ends and move the left position rightward and the right position leftward. Use set for swapping; add would change the list's size.

Takeaway: Define the accumulator, stopping condition, empty-list behavior, and early-return rule before writing the traversal.

Collections Utilities and Problem-Solving Checks

The Collections utility class supplies reusable algorithms for common list operations. Typical calls include:

• Collections.sort(list) orders elements in ascending order and changes the list.

• Collections.reverse(list) reverses the existing order.

• Collections.shuffle(list) randomly rearranges the elements.

• Collections.min(list) returns the smallest element without sorting the list.

• Collections.max(list) returns the largest element without sorting the list.

• Collections.frequency(list, value) counts occurrences of a value.

Collections.binarySearch(list, target) has an important precondition: the list must already be sorted according to the same ordering used by the search. The method returns an index if the target is present and a negative value if it is absent. Calling it on an unsorted list does not provide a reliable result.

Choose a library operation when the task exactly matches a standard operation. Write a custom traversal when the condition is more specific, such as counting values greater than a threshold that also satisfy another property. In either case, determine whether the operation changes the list or only returns information about it.

A useful final checklist is:

• Are indexes bounded by $0$ through $size() - 1$ for access?

• Is add being distinguished from set?

• Is remove(int) being distinguished from remove(Object)?

• Could a structural modification skip an element or invalidate an enhanced traversal?

• Could the list be empty?

• Are wrapper values compared with .equals?

• Is a sorted-list precondition satisfied before binary search?

Takeaway: Correct list algorithms depend on both the operation's behavior and the conditions required before it is called.

• remove method