ArrayList Fundamentals and Dynamic Memory Management
Limitations of Standard Arrays and the Need for Resizing
Arrays are fundamental structures used to store multiple items, making programs scalable by allowing loops rather than requiring millions of unique variables to handle data.
The primary downside of a standard array is its fixed memory size; once initialized, it cannot be resized. For example, an array of size cannot simply be expanded to size .
Manually expanding a standard array (e.g.,
arr = {1, 7, 2}) involves a labor-intensive four-step procedure:Create a completely new temporary array (
temp) with a size oforiginal.length + 1().Perform a
forloop to copy every element from the original array into the temporary array, ensuring the loop uses the originalarray.lengthto avoidArrayIndexOutOfBoundsExceptionon the source, or empty trailing values on the destination iftemp.lengthwere used.Add the new item (e.g., the number ) to the last position of the temporary array:
temp[temp.length - 1] = 99;.Replace the original reference by reassigning the variable:
arr = temp;.
This manual process is required every time a piece of data is added (such as adding a reply to a social media post), illustrating the inefficiency of standard arrays for dynamic datasets.
Introduction to ArrayLists
An
ArrayListis a library class in Java that acts as a dynamic array, growing automatically when it becomes full.ArrayLists offer several built-in methods that automate manual tasks:
add(): Appends an item to the list.size(): Returns the number of elements (equivalent to.lengthfor arrays).get(): Accesses an item at a specific index.set(): Changes an item at a specific index.remove(): Deletes an item and shifts remaining elements to close the gap.
Standard arrays can hold both primitive data (e.g.,
int,boolean,float) and objects. In contrast,ArrayListscan only hold objects.
Java Imports and Syntax
Unlike the
SystemorMathlibraries,ArrayListis not imported by default to ensure program efficiency. It must be manually imported using the command:import java.util.ArrayList;If the import is missing, the compiler will return an error stating the type "cannot be resolved."
Standard syntax for creating an ArrayList:
ArrayList<Integer> list = new ArrayList<Integer>();.The
newkeyword indicates that memory addresses and object instances are being assigned.The "pointy brackets" () indicate a Generic. This specifies the type of data the list will hold. Without this specification, the program would not know if the list contained strings, integers, or booleans.
Java identifies classes/objects by the use of capital letters (e.g.,
String,ArrayList,Integer), whereas primitives are generally lowercase (e.g.,int,boolean).
Wrapper Classes and Auto-boxing
Because
ArrayListscannot store primitives, Java uses Wrapper Classes to encapsulate primitive values into objects.Common Wrapper Classes include:
Integerwrapsint.Booleanwrapsboolean.Doublewrapsdouble.Characterwrapschar.Floatwrapsfloat(which requires anfsuffix for literals, like5.0f).
Auto-boxing: The automatic conversion of a primitive into its corresponding wrapper object. Example:
Integer a = 50;converts the primitive50into anIntegerobject.Auto-unboxing: The automatic conversion of a wrapper object back into a primitive. Example:
int c = b;(wherebis anInteger) extracts the numerical value from the object.Function Overloading: Different versions of a function can exist with the same name if their parameters differ.
If a function
foo(int x)andfoo(Integer x)both exist,foo(50)will call theintversion, whilefoo(new Integer(50))will call theIntegerversion.If only one version exists, Java will automatically box or unbox to match the parameter.
Essential ArrayList Methods
add(E e): Appends the specified element to the end of the list. It uses the generic type
Edefined during initialization.size(): Returns an
intrepresenting the total number of elements currently in the list.get(int index): Returns the element at the specified position.
set(int index, E element): Replaces the element at the specified position with the new element. Like arrays, attempting to set a value at an index outside the current size results in an
IndexOutOfBoundsException.remove(int index): Removes the element at the index and shifts all subsequent elements to the left. This version returns the object that was removed.
remove(Object o): Searches for the first occurrence of the specific object and removes it. This version returns a
boolean(trueif found/removed,falseotherwise). It does not return the object because the caller already knows what they requested to remove.add(int index, E element): Inserts an element at a specific index. Everything at that index and beyond is shifted to the right to make space. For a list of size , adding at index is valid (appends to end), but adding at index is an error.
Traversing and Looping
Standard
forloop traversal:for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); }.For-each loop (Enhanced for loop): A shorthand syntax often referred to as Syntactic Sugar.
Syntax:
for (Integer item : list) { ... }(read as "for each item in list").Limitation: The for-each loop cannot be used to update or double the values inside an
ArrayList. This is because theitemvariable is a local copy of the value; modifyingitemdoes not change the reference stored within the actual list. To update values, a standard loop with.set()must be used.
Memory Diagrams and Internal Structure
An
ArrayListinstance is a complex object structure stored in memory:The variable (e.g.,
marks) holds a reference/address to theArrayListobject instance.The
ArrayListinstance contains two primary fields:size(primitiveint) andelementData(a reference to a standard array).elementDatapoints to an internal array of references.These references inside the internal array point to the final
Integeror object instances containing the actual data.
When an
ArrayListis passed into a function, it is passed by reference. Modifying the list inside the function (e.g.,list.set(0, 500)) alters the original list outside the function because they share the same memory location.
Efficiency and Performance Trade-offs
There is no "magic" in programming; the convenience of
ArrayListcomes at a performance cost.Example Case Study: Extracting Positive Even Numbers:
Manual Array Approach: Requires two passes: one to count the positives to determine the exact size needed, and a second to copy them. This is efficient in memory usage as it creates only two fixed arrays ().
ArrayList Approach: Only requires one pass because you can
add()as you find positives. However, every time the internal array is full, theadd()method triggers a nested loop to create a new array and copy all items ( in some growth patterns).
Numerical Benchmarking:
In a test with a large dataset, a standard array operation took approximately .
The identical operation using an
ArrayListtook approximately (roughly 10 times slower).
Pre-allocation: To mitigate the cost of copying,
ArrayListsoften pre-allocate extra space (e.g., doubling the internal array size). This can lead to "Out of Memory" (Heap Space) errors on extremely large datasets because the program must hold both the old array and the new, larger array in memory simultaneously during the copy process.
Questions & Discussion
Question: Can you put a standard array inside an
ArrayList?Response: Yes. Since an array is considered an object in Java, you can create a list such as
ArrayList<int[]> list2;which stores array locations.Question: What is the difference between
floatanddouble?Response: A
doubleuses twice the memory bits of afloat, allowing for greater precision and more digits. In Java,5.0is treated as adoubleby default; afloatmust be explicitly denoted with anf(e.g.,5.0f).Question: Does
remove(Object o)take out every instance of that object?Response: No, it only removes the first occurrence it finds in the list.
Question: Why does
size()use brackets but arraylengthdoes not?Response:
size()is a method call belonging to theArrayListclass, whilelengthis a property of the built-in array structure in Java.