MACRO NEPAL
ArrayList Internal Working in Java
awiskar acharya
October 30, 2025
9:19 am

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.

Category : JAVA

Leave a Reply

Your email address will not be published. Required fields are marked *


Macro Nepal Helper