Где хранятся ссылки в ArrayList?

# Где хранятся ссылки в ArrayList?

Краткий ответ

Ссылки в ArrayList хранятся в обычном массиве Java (Object[]). Внутренняя реализация ArrayList — это обёртка над примитивным массивом с логикой динамического увеличения размера.

Внутренняя структура ArrayList

public class ArrayList<E> extends AbstractList<E> implements List<E> {
    // Основной массив для хранения элементов
    transient Object[] elementData;  // Сюда хранятся ссылки
    
    // Текущее количество элементов
    private int size;
    
    // Начальная ёмкость по умолчанию
    private static final int DEFAULT_CAPACITY = 10;
}

Как это работает на уровне памяти

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

// Внутренний массив выглядит так:
// elementData = ["Hello", "World", "Java", null, null, null, ...]
//               ^       ^        ^      ^
//               ref     ref      ref    пусто

Детальный взгляд на память

В Heap памяти:

// Объект ArrayList занимает место в Heap:
ArrayList<String> list = new ArrayList<>();
//        ↓ Объект ArrayList в памяти
//  ┌─────────────────┐
//  │ elementData[]   │ ──→ ссылка на массив Object[]
//  │ size = 0        │
//  │ capacity = 10   │
//  └─────────────────┘
//
//  Array в памяти:
//  ┌────────────────────────────────────────┐
//  │ null │ null │ null │ ... │ null │     │  Размер = 10
//  └────────────────────────────────────────┘

list.add("Hello");
//  ┌────────────────────────────────────────┐
//  │ "Hello" │ null │ null │ ... │ null │  │
//  └────────────────────────────────────────┘
//   ↑ ссылка на строку в памяти

Как растёт ArrayList

public void ensureCapacity(int minCapacity) {
    // Когда нужно больше места
    if (minCapacity > elementData.length) {
        // Увеличиваем ёмкость на 50%
        int newCapacity = elementData.length + (elementData.length >> 1);
        Object[] newElementData = new Object[newCapacity];
        
        // Копируем все ссылки в новый массив
        System.arraycopy(elementData, 0, newElementData, 0, size);
        
        // Заменяем старый массив новым
        elementData = newElementData;
    }
}

Пример роста ArrayList

List<Integer> list = new ArrayList<>();  // Capacity = 10

for (int i = 0; i < 15; i++) {
    list.add(i);
}

// Процесс добавления:
// После add(0-9):   capacity = 10, size = 10
// При add(10):      capacity = 15, size = 11 (10 + 10/2 = 15)
// После add(11-14): capacity = 15, size = 15
// При add(15):      capacity = 22, size = 16 (15 + 15/2 = 22)

Внутренний массив доступен через Reflection

import java.lang.reflect.Field;

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

try {
    // Получаем доступ к приватному массиву
    Field field = ArrayList.class.getDeclaredField("elementData");
    field.setAccessible(true);
    Object[] elementData = (Object[]) field.get(list);
    
    System.out.println("Array size: " + elementData.length);
    System.out.println("Element 0: " + elementData[0]);  // "Hello"
    System.out.println("Element 1: " + elementData[1]);  // "World"
} catch (NoSuchFieldException | IllegalAccessException e) {
    e.printStackTrace();
}

Где находится сам массив Object[]?

// Массив Object[] хранится:
// 1. Сама ссылка на массив (в объекте ArrayList) → в HEAP
// 2. Сам массив Object[] → в HEAP
// 3. Объекты, на которые указывают ссылки → в HEAP

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

// Визуально в памяти:
// STACK                    HEAP
// ┌─────────────┐    ┌──────────────────────┐
// │ s1 ref  ────┼───→│ "Hello" String obj   │
// │ s2 ref  ────┼───→│ "World" String obj   │
// │ list ref ───┼───→│ ArrayList object     │
// └─────────────┘    │ ├─ elementData ref ──┼──→ [Object[10]]
//                    │ ├─ [Object[10]] ─────┼──→ [s1, s2, null, ...]
//                    └──────────────────────┘

Когда удаляем элемент

list.remove(0);  // Удаляем "Hello"

// Что происходит:
// 1. Ссылка на "Hello" удаляется из массива
// 2. Остальные элементы сдвигаются влево
// 3. Последний элемент становится null

// Было:  ["Hello", "World", null, null, ...]
// Стало: ["World", null,    null, null, ...]

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

// O(1) - добавление в конец (обычно)
list.add("item");

// O(n) - добавление в начало или середину (нужно сдвигать элементы)
list.add(0, "item");

// O(1) - получение элемента по индексу
String item = list.get(0);

// O(n) - удаление элемента (нужно сдвигать)
list.remove(0);

// O(n) - поиск элемента
int index = list.indexOf("item");

Сравнение с LinkedList

// ArrayList - ссылки в массиве
List<String> list = new ArrayList<>();  // O(1) доступ по индексу

// LinkedList - ссылки в узлах двусвязного списка
List<String> linked = new LinkedList<>();  // O(n) доступ по индексу

// Вставка в начало:
list.add(0, "item");        // O(n) - нужно сдвигать весь массив
linked.addFirst("item");      // O(1) - просто меняем ссылки

Практическая демонстрация

public class ArrayListDemo {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        
        // Добавляем элементы
        for (int i = 0; i < 20; i++) {
            list.add(i);
        }
        
        // Каждый элемент хранится как ссылка на объект Integer
        Integer first = list.get(0);  // Получает ссылку из массива
        
        // Удаляем элемент
        list.remove(5);  // Сдвигает ссылки в массиве
        
        // Проверяем
        System.out.println(list.size());  // 19
    }
}

Итог

Ссылки в ArrayList хранятся в обычном примитивном массиве Java (Object[]), который находится в Heap памяти. При добавлении элементов ArrayList автоматически увеличивает размер массива, копируя ссылки в новый, больший массив. Это обеспечивает быстрый доступ по индексу O(1), но медленные вставки и удаления в начало/середину O(n).