Какая структура используется под капотом у MutableList и ImmutableList?

Структуры данных MutableList и ImmutableList в Kotlin

Под капотом Kotlin, MutableList и ImmutableList (обычно представляемый интерфейсом List) — это не конкретные структуры данных, а интерфейсы, которые декларируют поведение. Их фактическая реализация зависит от способа создания и используемого Kotlin/Java API.

Реализация MutableList

В большинстве случаев MutableList в Kotlin реализуется через стандартные классы коллекций из Java, адаптированные через механизм type aliasing и wrapper-функции.

Основные реализации:

1. ArrayList (java.util.ArrayList) — это наиболее частая структура под капотом при использовании mutableListOf().

val mutableList = mutableListOf("a", "b", "c") // Внутри обычно ArrayList

• Структура: Динамически расширяемый массив (Array).
• Принцип работы: Элементы хранятся в непрерывном блоке памяти. При добавлении элементов и превышении вместимости создается новый массив большего размера (обычно в 1.5 раза), и данные копируются.
• Характеристики: Быстрый доступ по индексу O(1), добавление в конец в среднем O(1) (за счет amortized analysis), но добавление/удаление в середину требует сдвига элементов и имеет стоимость O(n).

// Пример создания и демонстрации поведения
val list: MutableList<Int> = mutableListOf(1, 2)
list.add(3) // Быстро, если емкость позволяет
list.add(0, 0) // Медленнее, требует сдвига [1,2,3] -> [0,1,2,3]

1. LinkedList (java.util.LinkedList) — используется, если создавать список через конструктор LinkedList или mutableListOf с исходными данными другой структуры, но mutableListOf() по умолчанию возвращает ArrayList.

• Структура: Двухсвязный список. Каждый элемент (Node) содержит ссылки на предыдущий и следующий.
• Принцип работы: Элементы разрознены в памяти. Добавление и удаление из начала/середины/конца происходит за O(1) (если известна позиция), но доступ по индексу требует последовательного прохода и имеет стоимость O(n).

Реализация List (Immutable)

Kotlin пропагандирует безопасность и четко разделяет изменяемые и неизменяемые коллекции. Однако термин "ImmutableList" — это скорее контракт интерфейса List. Сам интерфейс List в Kotlin не имеет методов модификации (add, remove). Конкретные реализации, возвращаемые функцией listOf(), могут быть разными.

Основные реализации:

1. EmptyList — специализированный singleton объект для пустого списка.
2. SingletonList — оптимизированная реализация для списка с одним элементом.
3. ArrayList (но обернутый) — для списков большего размера listOf(...) часто возвращает тот же java.util.ArrayList, но представленный как List. Это означает, что вы не можете вызвать методы модификации, так как тип — List, а не MutableList.

val immutableList: List<String> = listOf("x", "y", "z")
// immutableList.add("w") // Ошибка компиляции: `List` не имеет метода `add`.

// Однако, важно понимать: если исходный объект был ArrayList,
// и существует другая ссылка на него как на MutableList,
// то "иммутабельность" может быть лишь на уровне типа.
val internalArray: ArrayList<String> = ArrayList(immutableList)
internalArray.add("w") // Модифицирует внутреннюю структуру
println(immutableList) // Но immutableList все еще показывает ["x", "y", "z"]
// потому что immutableList — это read-only view, а не обязательно копия.

1. Arrays.ArrayList — это специальная обертка вокруг обычного массива, используемая, например, при вызове listOf(varargs).

Ключевой момент: Kotlin read-only интерфейсы (List, Set, Map) гарантируют, что через эту ссылку коллекцию нельзя изменить. Но они не гарантируют глубокую иммутабельность (immutability) самой структурной реализации, если исходный объект был изменяемым и доступен по другой ссылке. Для истинной иммутабельности необходимы специальные коллекции (например, из библиотеки Kotlinx или создание копии).

Итог

• MutableList (создается через mutableListOf()): чаще всего ArrayList — динамический массив. Может быть и LinkedList, если явно создан.
• List (read-only, создается через listOf()): интерфейс, под которым могут быть оптимизированные реализации для пустого/одноэлементного списка (EmptyList, SingletonList), или обернутый ArrayList/массив. Структура данных та же, но доступ только для чтения обеспечивается на уровне типа интерфейса Kotlin.

Выбор реализации влияет на производительность операций. Для частого доступа по индексу и добавления в конец предпочтительнее ArrayList (и, соответственно, mutableListOf()). Для частых операций добавления/удаления в середину при работе с итератором может быть лучше LinkedList. Kotlin, используя Java коллекции под капотом, дает доступ к этой мощной, проверенной базе структур данных, дополняя ее важной философией контроля мутабельности через систему интерфейсов.