Как устроена внутренняя организация ArrayList в памяти с точки зрения хранения элементов?

# Внутренняя организация ArrayList в памяти

ArrayList использует обычный Java массив для хранения элементов. Вот как это организовано.

Структура ArrayList

public class ArrayList<E> extends AbstractList<E> {
    // Внутренний массив для хранения элементов
    transient Object[] elementData;
    
    // Актуальное количество элементов (size)
    private int size;
    
    // Константа по умолчанию
    private static final int DEFAULT_CAPACITY = 10;
}

Как выглядит в памяти

ArrayList list = new ArrayList();
list.add("A");
list.add("B");
list.add("C");

В памяти Java Heap:

┌─────────────────────────────┐
│ ArrayList Object            │
├─────────────────────────────┤
│ elementData ─────────┐      │
│ size = 3             │      │
│ ...other fields...   │      │
└─────────────────────┼───────┘
                      │
                      ↓
┌──────────────────────────────────┐
│ Object[] массив (capacity=10)    │
├──────────────────────────────────┤
│ [0] → ref to "A" (String object) │
│ [1] → ref to "B" (String object) │  ← elementData[2]
│ [2] → ref to "C" (String object) │
│ [3] → null                       │
│ [4] → null                       │
│ [5] → null                       │
│ [6] → null                       │
│ [7] → null                       │
│ [8] → null                       │
│ [9] → null                       │
└──────────────────────────────────┘

Ключевые моменты

1. Хранятся ссылки (references), не сами объекты

ArrayList<String> list = new ArrayList<>();
list.add("Hello");
list.add("World");

// В elementData[0] хранится ссылка на String "Hello"
// В elementData[1] хранится ссылка на String "World"
// Сами строки находятся в другом месте в Heap

2. Тип хранения: Object[]

// Внутри ArrayList используется Object[]
// Это позволяет хранить любые типы (благодаря inheritance)

ArrayList<Integer> intList = new ArrayList<>();
intList.add(5);
// 5 автоматически оборачивается в Integer object
// В elementData хранится ref на Integer(5)

ArrayList<MyClass> myList = new ArrayList<>();
myList.add(new MyClass());
// В elementData хранится ref на MyClass object

3. Расположение в памяти

String Heap (где хранятся сами объекты):
┌──────────────────────────┐
│ String "A" (в String Pool)│
│ hash=1234, value=[......]│
└──────────────────────────┘

String "B" (в String Pool)
┌──────────────────────────┐
│ String "B"               │
│ hash=5678, value=[......]│
└──────────────────────────┘

ArrayList elementData[]
┌──────────────────────┐
│ [0] → ref(String "A")│
│ [1] → ref(String "B")│
│ [2] → null           │
└──────────────────────┘

Примитивные типы

// ❌ ArrayList<int> НЕ существует
// ArrayList<int> list = new ArrayList<>();  // Ошибка компиляции!

// ✅ Используем wrapper класс
ArrayList<Integer> list = new ArrayList<>();
list.add(5);  // Автоматически: Integer.valueOf(5)

// В памяти
┌──────────────────────┐
│ Integer wrapper      │
│ value = 5            │
└──────────────────────┘
   ^
   │
   └─ ref in elementData[0]

Удаление элемента

ArrayList<String> list = new ArrayList<>();
list.add("A");  // [0] → ref "A"
list.add("B");  // [1] → ref "B"
list.add("C");  // [2] → ref "C"
// size = 3, capacity = 10

list.remove(1);  // Удаляем "B"

// После удаления:
┌──────────────────────┐
│ [0] → ref "A"       │
│ [1] → ref "C"       │  (сдвинулся с позиции 2)
│ [2] → null          │  (обнулено для GC)
│ [3] → null          │
└──────────────────────┘
// size = 2, capacity = 10 (не изменился!)

null элементы

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add(null);  // ✅ Можно хранить null
list.add("C");

┌──────────────────────┐
│ [0] → ref "A"       │
│ [1] → null           │  (это валидный элемент)
│ [2] → ref "C"       │
└──────────────────────┘
// size = 3 (null считается элементом!)

Особенности по версиям Java

Java 7+

// Type erasure - информация о типе стирается во время компиляции
ArrayList<String> list = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();

// В runtime они одно и то же: ArrayList (без информации о типе)
// Проверка типа только во время компиляции

Получение внутреннего массива (рефлексия)

import java.lang.reflect.Field;

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");

try {
    // Получаем поле elementData
    Field field = ArrayList.class.getDeclaredField("elementData");
    field.setAccessible(true);
    
    Object[] array = (Object[]) field.get(list);
    
    System.out.println("Capacity: " + array.length);  // 10
    System.out.println("[0]: " + array[0]);  // "A"
    System.out.println("[1]: " + array[1]);  // "B"
    System.out.println("[2]: " + array[2]);  // null
} catch (NoSuchFieldException | IllegalAccessException e) {
    e.printStackTrace();
}

Сложность операций

Access by index [get(i)]:           O(1) - прямой доступ к массиву
Insert at end [add(e)]:             O(1) амортизированно
Insert at position [add(i, e)]:     O(n) - нужен сдвиг элементов
Remove from end [remove(size-1)]:   O(1)
Remove from start [remove(0)]:      O(n) - нужен сдвиг элементов
Search [indexOf(e)]:                O(n) - линейный поиск
Sort:                              O(n log n)

Резюме

ArrayList в памяти:

1. Использует Object[] массив - хранит ссылки на объекты
2. size - количество реальных элементов
3. capacity - размер внутреннего массива
4. Растёт на 50% когда capacity не достаточна
5. Не уменьшается при удалении
6. Ссылки, не значения - хранит refs, не сами объекты
7. null элементы разрешены - это валидные элементы
8. Type erasure - информация о типе стирается во время компиляции