ArrayList

Internal Structure of ArrayList

ArrayList is backed by a dynamic array (Object[]). When you add elements, they are stored in this internal array. When the array becomes full, ArrayList creates a new array with 1.5x the capacity and copies elements over.

Key fields:

• elementData — the backing Object[] array
• size — the number of elements stored
• Default initial capacity is 10

public class ArrayListInternalDemo {
    public static void main(String[] args) {
        // Create with default capacity (10)
        java.util.ArrayList<String> list = new java.util.ArrayList<>();

        // Add elements - array grows as needed
        for (int i = 0; i < 15; i++) {
            list.add("Element " + i);
        }

        System.out.println("Size: " + list.size()); // 15
        System.out.println("First: " + list.get(0)); // Element 0
        System.out.println("Last: " + list.get(14)); // Element 14

        // Create with specific initial capacity
        java.util.ArrayList<Integer> nums = new java.util.ArrayList<>(100);
        System.out.println("Initial capacity: 100");
        System.out.println("Empty? " + nums.isEmpty()); // true

        // What happens internally during growth
        java.util.ArrayList<Integer> growth = new java.util.ArrayList<>(2);
        growth.add(1); // array: [1, null]
        growth.add(2); // array: [1, 2] - full!
        growth.add(3); // new array: [1, 2, 3, null, null] - 1.5x growth
        growth.add(4);
        growth.add(5); // new array: [1, 2, 3, 4, 5, null, null, null] - 1.5x growth

        System.out.println("Growth demo size: " + growth.size());

        // trimToSize - reduce capacity to actual size
        growth.trimToSize();
        System.out.println("After trim, size: " + growth.size());

        // ensureCapacity - pre-allocate to avoid repeated growth
        java.util.ArrayList<String> preallocated = new java.util.ArrayList<>();
        preallocated.ensureCapacity(1000); // avoid 10+ resizes
        for (int i = 0; i < 1000; i++) {
            preallocated.add("Item " + i);
        }
        System.out.println("Preallocated size: " + preallocated.size());
    }
}

Growth strategy: The new capacity is oldCapacity + (oldCapacity >> 1) — that is, 1.5x the old capacity. This amortizes the cost of array copying across many additions.

Memory considerations:

• ArrayList may waste memory if it holds many unused array slots
• Use trimToSize() to reclaim space after bulk operations
• Pre-allocate with ensureCapacity() if you know the approximate size

Core Methods of ArrayList

ArrayList provides a rich set of methods inherited from List and AbstractList. Here are the essential methods:

import java.util.*;

public class ArrayListMethodsDemo {
    public static void main(String[] args) {
        // Creating
        ArrayList<String> list = new ArrayList<>();
        ArrayList<String> fromArray = new ArrayList<>(Arrays.asList("a", "b", "c"));
        ArrayList<String> copy = new ArrayList<>(fromArray);

        // Adding elements
        list.add("Alice");           // append to end
        list.add("Bob");             // append to end
        list.add(0, "Charlie");       // insert at index 0
        list.add(1, "Diana");         // insert at index 1
        list.addAll(Arrays.asList("Eve", "Frank")); // add multiple
        list.addAll(2, Arrays.asList("Grace", "Heidi")); // add at index
        System.out.println("After adds: " + list);

        // Accessing elements
        String first = list.get(0);   // Charlie
        String last = list.get(list.size() - 1); // Frank
        int idx = list.indexOf("Diana"); // 2
        int lastIdx = list.lastIndexOf("Alice"); // 1
        boolean has = list.contains("Eve"); // true
        System.out.println("First: " + first);
        System.out.println("Index of Diana: " + idx);

        // Modifying elements
        list.set(0, "Charles"); // replace at index 0
        System.out.println("After set: " + list);

        // Removing elements
        list.remove("Bob");          // remove first occurrence of Bob
        list.remove(0);              // remove at index 0
        list.removeIf(s -> s.length() > 5); // remove all matching
        System.out.println("After removes: " + list);

        // Searching
        boolean exists = list.contains("Eve");
        int pos = list.indexOf("Eve");
        System.out.println("Contains Eve: " + exists + ", at position: " + pos);

        // Bulk operations
        ArrayList<String> other = new ArrayList<>(Arrays.asList("Eve", "Ivan"));
        list.retainAll(other); // keep only common elements
        System.out.println("After retainAll: " + list);

        // Converting
        Object[] array = list.toArray();
        String[] stringArray = list.toArray(new String[0]);
        System.out.println("Array: " + Arrays.toString(stringArray));

        // SubList (view, not copy)
        ArrayList<String> full = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
        List<String> sub = full.subList(1, 4); // [b, c, d]
        sub.set(0, "B"); // also changes full!
        System.out.println("Full after sublist change: " + full); // [a, B, c, d, e]

        // Clear
        list.clear();
        System.out.println("Empty? " + list.isEmpty());
    }
}

Important notes:

• get() and set() throw IndexOutOfBoundsException for invalid indices
• remove(Object) removes the first occurrence; remove(int) removes by index
• subList() returns a view — changes to the sublist affect the original list
• add() and remove() may trigger array resizing

Time Complexity of ArrayList

Understanding ArrayList's time complexity is crucial for making informed design decisions.

Operation	Time Complexity	Notes
get(index)	O(1)	Direct array access
set(index, element)	O(1)	Direct array access
add(element)	O(1) amortized	O(n) when resizing
add(index, element)	O(n)	Must shift elements
remove(int index)	O(n)	Must shift elements
remove(Object)	O(n)	Search + shift
contains(Object)	O(n)	Linear search
indexOf(Object)	O(n)	Linear search
size()	O(1)	Field access
isEmpty()	O(1)	Field access

import java.util.*;

public class ArrayListComplexityDemo {
    public static void main(String[] args) {
        // O(1) access
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(10, 20, 30, 40, 50));
        System.out.println("O(1) get: " + list.get(2)); // 30
        list.set(2, 35); // O(1) set
        System.out.println("O(1) set: " + list.get(2)); // 35

        // O(n) insertion in middle
        list.add(2, 25); // shifts elements at index 2+ right
        System.out.println("O(n) insert: " + list); // [10, 20, 25, 35, 40, 50]

        // O(n) removal from middle
        list.remove(3); // shifts elements at index 3+ left
        System.out.println("O(n) remove: " + list); // [10, 20, 25, 40, 50]

        // O(n) contains/indexOf
        System.out.println("O(n) contains: " + list.contains(25)); // true
        System.out.println("O(n) indexOf: " + list.indexOf(40)); // 3

        // Amortized O(1) add at end
        // Most adds are O(1), occasional resize is O(n)
        ArrayList<Integer> amortized = new ArrayList<>(2);
        for (int i = 0; i < 1000; i++) {
            amortized.add(i); // O(1) amortized
        }
        System.out.println("Amortized add: size=" + amortized.size());

        // When ArrayList is slow
        // Inserting at the beginning: O(n)
        // Removing from the beginning: O(n)
        // Searching without index: O(n)
    }
}

Performance tips:

• Pre-allocate capacity if you know the size: new ArrayList<>(expectedSize)
• Avoid inserting/removing at the beginning — use ArrayDeque instead
• Use indexOf() for searching, but consider HashSet for frequent lookups
• Use bulk operations like addAll() instead of individual add() calls
• For large lists, consider trimToSize() after removing many elements

ArrayList vs LinkedList

Both implement the List interface but have very different performance characteristics.

Operation	ArrayList	LinkedList
get(index)	O(1)	O(n)
add at end	O(1) amortized	O(1)
add at beginning	O(n)	O(1)
add at middle	O(n)	O(n)*
remove at end	O(1)	O(1)
remove at beginning	O(n)	O(1)
remove at middle	O(n)	O(n)*
contains	O(n)	O(n)
memory	compact	overhead per node

*LinkedList has O(n) to find the position, then O(1) to insert/remove.

import java.util.*;

public class ArrayListVsLinkedListDemo {
    public static void main(String[] args) {
        // Random access: ArrayList wins
        ArrayList<Integer> arrayList = new ArrayList<>();
        LinkedList<Integer> linkedList = new LinkedList<>();

        for (int i = 0; i < 10000; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        long start = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            arrayList.get(i); // O(1) each
        }
        long arrayListTime = System.nanoTime() - start;

        start = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            linkedList.get(i); // O(n) each!
        }
        long linkedListTime = System.nanoTime() - start;

        System.out.println("Random access ArrayList: " + arrayListTime + " ns");
        System.out.println("Random access LinkedList: " + linkedListTime + " ns");

        // Insert at beginning: LinkedList wins
        arrayList = new ArrayList<>(Arrays.asList(new Integer[10000]));
        linkedList = new LinkedList<>(Arrays.asList(new Integer[10000]));

        start = System.nanoTime();
        arrayList.add(0, -1); // O(n) - shifts all elements
        long arrayListInsert = System.nanoTime() - start;

        start = System.nanoTime();
        linkedList.addFirst(-1); // O(1)
        long linkedListInsert = System.nanoTime() - start;

        System.out.println("\nInsert at beginning ArrayList: " + arrayListInsert + " ns");
        System.out.println("Insert at beginning LinkedList: " + linkedListInsert + " ns");

        // When to use each
        System.out.println("\n--- When to use ---");
        System.out.println("ArrayList: frequent random access, iteration, append");
        System.out.println("LinkedList: frequent add/remove at both ends, Deque operations");
    }
}

Rule of thumb: Default to ArrayList. Use LinkedList only when you need frequent insertions/deletions at both ends and cannot use ArrayDeque. In practice, ArrayList is almost always the better choice due to CPU cache locality.