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 33 cannot simply be expanded to size 44.

  • Manually expanding a standard array (e.g., arr = {1, 7, 2}) involves a labor-intensive four-step procedure:

    1. Create a completely new temporary array (temp) with a size of original.length + 1 (n+1n+1).

    2. Perform a for loop to copy every element from the original array into the temporary array, ensuring the loop uses the original array.length to avoid ArrayIndexOutOfBoundsException on the source, or empty trailing values on the destination if temp.length were used.

    3. Add the new item (e.g., the number 9999) to the last position of the temporary array: temp[temp.length - 1] = 99;.

    4. 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 ArrayList is 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 .length for 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, ArrayLists can only hold objects.

Java Imports and Syntax

  • Unlike the System or Math libraries, ArrayList is 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 new keyword 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 ArrayLists cannot store primitives, Java uses Wrapper Classes to encapsulate primitive values into objects.

  • Common Wrapper Classes include:

    • Integer wraps int.

    • Boolean wraps boolean.

    • Double wraps double.

    • Character wraps char.

    • Float wraps float (which requires an f suffix for literals, like 5.0f).

  • Auto-boxing: The automatic conversion of a primitive into its corresponding wrapper object. Example: Integer a = 50; converts the primitive 50 into an Integer object.

  • Auto-unboxing: The automatic conversion of a wrapper object back into a primitive. Example: int c = b; (where b is an Integer) 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) and foo(Integer x) both exist, foo(50) will call the int version, while foo(new Integer(50)) will call the Integer version.

    • 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 E defined during initialization.

  • size(): Returns an int representing 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 (true if found/removed, false otherwise). 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 33, adding at index 33 is valid (appends to end), but adding at index 44 is an error.

Traversing and Looping

  • Standard for loop 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 the item variable is a local copy of the value; modifying item does 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 ArrayList instance is a complex object structure stored in memory:

    1. The variable (e.g., marks) holds a reference/address to the ArrayList object instance.

    2. The ArrayList instance contains two primary fields: size (primitive int) and elementData (a reference to a standard array).

    3. elementData points to an internal array of references.

    4. These references inside the internal array point to the final Integer or object instances containing the actual data.

  • When an ArrayList is 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 ArrayList comes 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 (O(n)O(n)).

    • ArrayList Approach: Only requires one pass because you can add() as you find positives. However, every time the internal array is full, the add() method triggers a nested loop to create a new array and copy all items (O(n2)O(n^2) in some growth patterns).

  • Numerical Benchmarking:

    • In a test with a large dataset, a standard array operation took approximately 106 ms106\,ms.

    • The identical operation using an ArrayList took approximately 1200 ms1200\,ms (roughly 10 times slower).

  • Pre-allocation: To mitigate the cost of copying, ArrayLists often 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 float and double?

  • Response: A double uses twice the memory bits of a float, allowing for greater precision and more digits. In Java, 5.0 is treated as a double by default; a float must be explicitly denoted with an f (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 array length does not?

  • Response: size() is a method call belonging to the ArrayList class, while length is a property of the built-in array structure in Java.