ArrayList is one of the most commonly used data structures in Java. Understanding its internal implementation is crucial for writing efficient code.

1. ArrayList Class Structure

Basic Class Declaration

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { // Default initial capacity private static final int DEFAULT_CAPACITY = 10; // Shared empty array instance used for empty instances private static final Object[] EMPTY_ELEMENTDATA = {}; // The array buffer where elements are stored transient Object[] elementData; // The size of the ArrayList (number of elements it contains) private int size; // ... other methods and constructors }

2. Internal Data Structure

Core Fields

// Simplified view of ArrayList internals public class ArrayListInternalView<E> { // The actual array that stores elements private transient Object[] elementData; // Current number of elements in the list private int size; // Default capacity when no initial capacity specified private static final int DEFAULT_CAPACITY = 10; // Empty array for empty instances private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; }

3. Constructors and Initialization

Constructor Implementations

import java.util.Arrays; public class ArrayListInternalsDemo { // Simulating ArrayList's internal array private transient Object[] elementData; private int size; private static final int DEFAULT_CAPACITY = 10; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // Constructor 1: Default constructor public ArrayListInternalsDemo() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; this.size = 0; System.out.println("Default constructor: elementData = " + Arrays.toString(elementData) + ", size = " + size); } // Constructor 2: With initial capacity public ArrayListInternalsDemo(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; this.size = 0; } else if (initialCapacity == 0) { this.elementData = new Object[0]; this.size = 0; } else { throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } System.out.println("Capacity constructor: elementData.length = " + elementData.length + ", size = " + size); } // Constructor 3: From existing collection public ArrayListInternalsDemo(java.util.Collection<? extends E> c) { Object[] a = c.toArray(); this.size = a.length; if (size != 0) { this.elementData = Arrays.copyOf(a, size, Object[].class); } else { this.elementData = new Object[0]; } System.out.println("Collection constructor: elementData = " + Arrays.toString(elementData) + ", size = " + size); } public static void main(String[] args) { System.out.println("=== ArrayList Constructor Examples ==="); // Default constructor ArrayListInternalsDemo<String> list1 = new ArrayListInternalsDemo<>(); // Capacity constructor ArrayListInternalsDemo<String> list2 = new ArrayListInternalsDemo<>(20); // Collection constructor java.util.List<String> existingList = Arrays.asList("A", "B", "C"); ArrayListInternalsDemo<String> list3 = new ArrayListInternalsDemo<>(existingList); } }

4. Add Operation - Internal Working

add(E element) Method

public class ArrayListAddOperation { private Object[] elementData; private int size; private static final int DEFAULT_CAPACITY = 10; public ArrayListAddOperation() { this.elementData = new Object[DEFAULT_CAPACITY]; this.size = 0; } // Main add method public boolean add(E e) { System.out.println("Adding element: " + e); System.out.println("Before add - size: " + size + ", capacity: " + elementData.length); // Ensure capacity ensureCapacityInternal(size + 1); // Add element at the end elementData[size++] = e; System.out.println("After add - size: " + size + ", capacity: " + elementData.length); System.out.println("Current array: " + Arrays.toString(Arrays.copyOf(elementData, size))); return true; } // Internal capacity management private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { // Overflow-conscious code if (minCapacity - elementData.length > 0) { grow(minCapacity); } } // The core growth mechanism private void grow(int minCapacity) { System.out.println(">>> Growing array from " + elementData.length + " to accommodate " + minCapacity); int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 times old capacity System.out.println("Old capacity: " + oldCapacity + ", New capacity (1.5x): " + newCapacity); if (newCapacity - minCapacity < 0) { newCapacity = minCapacity; System.out.println("Adjusted new capacity to minCapacity: " + newCapacity); } if (newCapacity - MAX_ARRAY_SIZE > 0) { newCapacity = hugeCapacity(minCapacity); } // Copy elements to new larger array elementData = Arrays.copyOf(elementData, newCapacity); System.out.println(">>> Array grown to new capacity: " + newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; public static void main(String[] args) { ArrayListAddOperation<String> list = new ArrayListAddOperation<>(); // Add elements to demonstrate growth for (int i = 1; i <= 15; i++) { list.add("Element-" + i); System.out.println("---"); } } }

add(int index, E element) Method

public class ArrayListAddAtIndex { private Object[] elementData; private int size; private static final int DEFAULT_CAPACITY = 5; // Smaller for demonstration public ArrayListAddAtIndex() { this.elementData = new Object[DEFAULT_CAPACITY]; this.size = 0; } // Add at specific index public void add(int index, E element) { rangeCheckForAdd(index); System.out.println("Adding '" + element + "' at index " + index); System.out.println("Before: " + Arrays.toString(Arrays.copyOf(elementData, size))); ensureCapacityInternal(size + 1); // Shift elements to the right to make space System.arraycopy(elementData, index, elementData, index + 1, size - index); // Insert the new element elementData[index] = element; size++; System.out.println("After: " + Arrays.toString(Arrays.copyOf(elementData, size))); System.out.println("Size: " + size + ", Capacity: " + elementData.length); System.out.println("---"); } private void rangeCheckForAdd(int index) { if (index > size || index < 0) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } } private void ensureCapacityInternal(int minCapacity) { if (minCapacity - elementData.length > 0) { grow(minCapacity); } } private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) { newCapacity = minCapacity; } elementData = Arrays.copyOf(elementData, newCapacity); System.out.println(">>> Array grown from " + oldCapacity + " to " + newCapacity); } public static void main(String[] args) { ArrayListAddAtIndex<String> list = new ArrayListAddAtIndex<>(); // Add some initial elements list.add(0, "First"); list.add(1, "Third"); list.add(1, "Second"); // Insert in middle list.add(0, "Zeroth"); // Insert at beginning list.add(4, "Fifth"); // Insert at end list.add(2, "Middle"); // Insert in middle causing shift } }

5. Get and Set Operations

Internal Working of get() and set()

public class ArrayListGetSet { private Object[] elementData; private int size; public ArrayListGetSet() { this.elementData = new Object[10]; this.size = 0; } public void add(E e) { if (size == elementData.length) { elementData = Arrays.copyOf(elementData, elementData.length * 2); } elementData[size++] = e; } // Get operation - O(1) complexity @SuppressWarnings("unchecked") public E get(int index) { System.out.println("Getting element at index " + index); rangeCheck(index); E element = (E) elementData[index]; System.out.println("Returning: " + element); return element; } // Set operation - O(1) complexity @SuppressWarnings("unchecked") public E set(int index, E element) { System.out.println("Setting element at index " + index + " to: " + element); rangeCheck(index); E oldValue = (E) elementData[index]; elementData[index] = element; System.out.println("Old value: " + oldValue); return oldValue; } private void rangeCheck(int index) { if (index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } } public int size() { return size; } public static void main(String[] args) { ArrayListGetSet<String> list = new ArrayListGetSet<>(); // Add elements for (int i = 0; i < 5; i++) { list.add("Item-" + i); } System.out.println("=== Get Operations ==="); list.get(0); // First element list.get(2); // Middle element list.get(4); // Last element System.out.println("\n=== Set Operations ==="); list.set(1, "Updated-Item-1"); list.set(3, "Updated-Item-3"); // Try invalid access try { list.get(10); // Should throw exception } catch (IndexOutOfBoundsException e) { System.out.println("Expected exception: " + e.getMessage()); } } }

6. Remove Operation - Internal Working

remove(int index) Method

public class ArrayListRemoveOperation { private Object[] elementData; private int size; private static final int DEFAULT_CAPACITY = 10; public ArrayListRemoveOperation() { this.elementData = new Object[DEFAULT_CAPACITY]; this.size = 0; } public void add(E e) { if (size == elementData.length) { elementData = Arrays.copyOf(elementData, elementData.length * 2); } elementData[size++] = e; } // Remove by index @SuppressWarnings("unchecked") public E remove(int index) { System.out.println("Removing element at index " + index); System.out.println("Before remove: " + getArraySnapshot()); rangeCheck(index); E oldValue = (E) elementData[index]; int numMoved = size - index - 1; if (numMoved > 0) { // Shift elements to the left to fill the gap System.arraycopy(elementData, index + 1, elementData, index, numMoved); } // Clear the last element and reduce size elementData[--size] = null; System.out.println("After remove: " + getArraySnapshot()); System.out.println("Removed value: " + oldValue); System.out.println("---"); return oldValue; } // Remove by object public boolean remove(Object o) { System.out.println("Removing object: " + o); System.out.println("Before remove: " + getArraySnapshot()); if (o == null) { for (int index = 0; index < size; index++) { if (elementData[index] == null) { fastRemove(index); System.out.println("After remove: " + getArraySnapshot()); return true; } } } else { for (int index = 0; index < size; index++) { if (o.equals(elementData[index])) { fastRemove(index); System.out.println("After remove: " + getArraySnapshot()); return true; } } } System.out.println("Object not found: " + o); return false; } // Fast remove without bounds check private void fastRemove(int index) { int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(elementData, index + 1, elementData, index, numMoved); } elementData[--size] = null; } private void rangeCheck(int index) { if (index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } } private String getArraySnapshot() { return Arrays.toString(Arrays.copyOf(elementData, size)); } public static void main(String[] args) { ArrayListRemoveOperation<String> list = new ArrayListRemoveOperation<>(); // Add elements for (int i = 0; i < 6; i++) { list.add("Element-" + i); } System.out.println("=== Remove by Index ==="); list.remove(2); // Remove middle list.remove(0); // Remove first list.remove(2); // Remove last (after previous removes) System.out.println("=== Remove by Object ==="); list.remove("Element-1"); list.remove("Non-Existent"); // Try to remove non-existent element } }

7. Iteration and ModCount

Internal Iterator Implementation

import java.util.*; public class ArrayListIteratorInternal { private Object[] elementData; private int size; protected transient int modCount = 0; // Modification count public ArrayListIteratorInternal() { this.elementData = new Object[10]; this.size = 0; } public void add(E e) { modCount++; if (size == elementData.length) { elementData = Arrays.copyOf(elementData, elementData.length * 2); } elementData[size++] = e; } public E remove(int index) { modCount++; rangeCheck(index); @SuppressWarnings("unchecked") E oldValue = (E) elementData[index]; int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(elementData, index + 1, elementData, index, numMoved); } elementData[--size] = null; return oldValue; } // Custom iterator implementation public Iterator<E> iterator() { return new Itr(); } // Internal Iterator class private class Itr implements Iterator<E> { int cursor = 0; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; public boolean hasNext() { System.out.println("hasNext() - cursor: " + cursor + ", size: " + size); return cursor != size; } @SuppressWarnings("unchecked") public E next() { System.out.println("next() called - cursor: " + cursor); checkForComodification(); int i = cursor; if (i >= size) { throw new NoSuchElementException(); } Object[] elementData = ArrayListIteratorInternal.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } cursor = i + 1; lastRet = i; return (E) elementData[lastRet]; } public void remove() { System.out.println("Iterator remove() called"); if (lastRet < 0) { throw new IllegalStateException(); } checkForComodification(); try { ArrayListIteratorInternal.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; // Reset expected modification count } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (modCount != expectedModCount) { System.out.println("Concurrent modification detected! modCount: " + modCount + ", expectedModCount: " + expectedModCount); throw new ConcurrentModificationException(); } } } private void rangeCheck(int index) { if (index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } } public static void main(String[] args) { ArrayListIteratorInternal<String> list = new ArrayListIteratorInternal<>(); // Add elements for (int i = 0; i < 5; i++) { list.add("Item-" + i); } System.out.println("=== Normal Iteration ==="); Iterator<String> iterator = list.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); } System.out.println("\n=== Iteration with Remove ==="); iterator = list.iterator(); while (iterator.hasNext()) { String item = iterator.next(); if ("Item-2".equals(item)) { iterator.remove(); System.out.println("Removed: " + item); } } System.out.println("\n=== Concurrent Modification Example ==="); iterator = list.iterator(); try { while (iterator.hasNext()) { String item = iterator.next(); System.out.println(item); if ("Item-1".equals(item)) { list.add("New-Item"); // This will cause ConcurrentModificationException } } } catch (ConcurrentModificationException e) { System.out.println("Caught ConcurrentModificationException as expected"); } } }

8. Performance Analysis

Time Complexity Analysis

import java.util.*; public class ArrayListPerformanceAnalysis { private static final int TEST_SIZE = 100000; public static void main(String[] args) { System.out.println("ArrayList Performance Analysis"); System.out.println("Test Size: " + TEST_SIZE + " elements"); System.out.println("====================================="); // Add operations testAddOperations(); // Access operations testAccessOperations(); // Search operations testSearchOperations(); // Remove operations testRemoveOperations(); // Memory usage testMemoryUsage(); } public static void testAddOperations() { System.out.println("\n=== Add Operations ==="); // Add at end List<Integer> list = new ArrayList<>(); long start = System.nanoTime(); for (int i = 0; i < TEST_SIZE; i++) { list.add(i); } long end = System.nanoTime(); System.out.printf("Add at end: %.2f ms%n", (end - start) / 1_000_000.0); // Add at beginning list.clear(); start = System.nanoTime(); for (int i = 0; i < 1000; i++) { // Smaller size for beginning adds list.add(0, i); } end = System.nanoTime(); System.out.printf("Add at beginning (1000 elements): %.2f ms%n", (end - start) / 1_000_000.0); // Add in middle list.clear(); for (int i = 0; i < 1000; i++) { list.add(i); } start = System.nanoTime(); for (int i = 0; i < 100; i++) { list.add(500, i); } end = System.nanoTime(); System.out.printf("Add in middle (100 operations): %.2f ms%n", (end - start) / 1_000_000.0); } public static void testAccessOperations() { System.out.println("\n=== Access Operations ==="); List<Integer> list = new ArrayList<>(); for (int i = 0; i < TEST_SIZE; i++) { list.add(i); } // Random access long start = System.nanoTime(); for (int i = 0; i < TEST_SIZE; i++) { list.get(i); } long end = System.nanoTime(); System.out.printf("Sequential access: %.2f ms%n", (end - start) / 1_000_000.0); // Random indices access Random random = new Random(); start = System.nanoTime(); for (int i = 0; i < 10000; i++) { list.get(random.nextInt(TEST_SIZE)); } end = System.nanoTime(); System.out.printf("Random access (10000 operations): %.2f ms%n", (end - start) / 1_000_000.0); } public static void testSearchOperations() { System.out.println("\n=== Search Operations ==="); List<Integer> list = new ArrayList<>(); for (int i = 0; i < TEST_SIZE; i++) { list.add(i); } // Search for existing element long start = System.nanoTime(); boolean found = list.contains(TEST_SIZE / 2); long end = System.nanoTime(); System.out.printf("Contains (middle element): %.2f ms, Found: %b%n", (end - start) / 1_000_000.0, found); // Search for non-existing element start = System.nanoTime(); found = list.contains(TEST_SIZE + 1); end = System.nanoTime(); System.out.printf("Contains (non-existing): %.2f ms, Found: %b%n", (end - start) / 1_000_000.0, found); // Index of operation start = System.nanoTime(); int index = list.indexOf(TEST_SIZE / 2); end = System.nanoTime(); System.out.printf("IndexOf (middle element): %.2f ms, Index: %d%n", (end - start) / 1_000_000.0, index); } public static void testRemoveOperations() { System.out.println("\n=== Remove Operations ==="); // Remove from end List<Integer> list = new ArrayList<>(); for (int i = 0; i < TEST_SIZE; i++) { list.add(i); } long start = System.nanoTime(); for (int i = TEST_SIZE - 1; i >= 0; i--) { list.remove(i); } long end = System.nanoTime(); System.out.printf("Remove from end: %.2f ms%n", (end - start) / 1_000_000.0); // Remove from beginning list.clear(); for (int i = 0; i < 1000; i++) { list.add(i); } start = System.nanoTime(); while (!list.isEmpty()) { list.remove(0); } end = System.nanoTime(); System.out.printf("Remove from beginning (1000 elements): %.2f ms%n", (end - start) / 1_000_000.0); } public static void testMemoryUsage() { System.out.println("\n=== Memory Usage ==="); Runtime runtime = Runtime.getRuntime(); // Force garbage collection System.gc(); long memoryBefore = runtime.totalMemory() - runtime.freeMemory(); List<Integer> list = new ArrayList<>(); for (int i = 0; i < TEST_SIZE; i++) { list.add(i); } long memoryAfter = runtime.totalMemory() - runtime.freeMemory(); long memoryUsed = memoryAfter - memoryBefore; System.out.printf("Memory used by ArrayList with %d elements: %.2f MB%n", TEST_SIZE, memoryUsed / (1024.0 * 1024.0)); // Show capacity vs size // Note: We can't access internal capacity directly, but we can estimate System.out.println("Size: " + list.size()); System.out.println("Estimated capacity growth pattern: 10 → 15 → 22 → 33 → ..."); } }

9. Capacity Growth Pattern

Visualizing Capacity Growth

import java.lang.reflect.Field; import java.util.ArrayList; public class ArrayListCapacityGrowth { public static void main(String[] args) throws Exception { System.out.println("ArrayList Capacity Growth Pattern"); System.out.println("================================="); ArrayList<Integer> list = new ArrayList<>(); System.out.println("Initial state:"); printCapacityAndSize(list); // Add elements and track capacity growth for (int i = 1; i <= 100; i++) { list.add(i); // Print when capacity changes if (i == 1 || i == 10 || i == 11 || i == 16 || i == 17 || i == 25 || i == 26 || i == 38 || i == 39 || i == 58 || i == 59 || i == 88 || i == 89) { printCapacityAndSize(list); } } System.out.println("\nFinal state:"); printCapacityAndSize(list); System.out.println("\nGrowth Pattern Summary:"); System.out.println("10 → 15 (1.5x)"); System.out.println("15 → 22 (1.5x)"); System.out.println("22 → 33 (1.5x)"); System.out.println("33 → 49 (1.5x)"); System.out.println("49 → 73 (1.5x)"); System.out.println("73 → 109 (1.5x)"); } // Helper method to get capacity using reflection private static int getCapacity(ArrayList<?> list) throws Exception { Field elementDataField = ArrayList.class.getDeclaredField("elementData"); elementDataField.setAccessible(true); Object[] elementData = (Object[]) elementDataField.get(list); return elementData.length; } private static void printCapacityAndSize(ArrayList<?> list) throws Exception { System.out.printf("Size: %2d, Capacity: %2d%n", list.size(), getCapacity(list)); } }

Summary

Key Internal Mechanisms:

1. Backing Array: ArrayList uses Object[] elementData to store elements
2. Size Tracking: int size tracks the number of elements
3. Capacity Growth: Grows by 1.5x when needed (newCapacity = oldCapacity + (oldCapacity >> 1))
4. Default Capacity: 10 when created with default constructor
5. Fast Access: O(1) for get/set operations due to array backing
6. ModCount: Tracks structural modifications for fail-fast iterators

Time Complexity:

• add(E element): Amortized O(1)
• add(int index, E element): O(n)
• get(int index): O(1)
• set(int index, E element): O(1)
• remove(int index): O(n)
• remove(Object o): O(n)
• contains(Object o): O(n)

Memory Characteristics:

• Overhead: Each ArrayList has array overhead + size field
• Wasted Space: Can have unused capacity in the backing array
• Trim: trimToSize() can reduce wasted space

Best Practices:

1. Use initial capacity constructor if size is known
2. Prefer add(element) over add(index, element) when possible
3. Use ArrayList for frequent access, LinkedList for frequent insertions/deletions
4. Consider trimToSize() if memory is critical and no more adds expected

Understanding ArrayList's internal working helps in writing efficient code and choosing the right collection for specific use cases.