Какую структуру данных получим, если в Kotlin-е написать listOf()? В чем отличия ArrayList и LinkedList? Сложность добавления в каждый из них? Сложность удаления из середины?

Вопрос комплексный, поэтому давайте разобьем на части. Помните, что мы будем обсуждать с ориентиром на JVM и что будет «под капотом» когда Kotlin-код будет транслирован. Потому, что реализации этих функций и тд может варьироваться на разных платформах. Ведь Kotlin язык созданный в первую очередь для мультиплатформы.

1. Что даёт listOf() в Kotlin на JVM

Под капотом (на JVM), listOf() не возвращает ни ArrayList, ни LinkedList. В зависимости от количества элементов:

• listOf() без аргументов => специальный singleton EmptyList
• listOf(x) => SingletonList
• listOf(a, b, c, ...) => реализация на основе динамического массива (kotlin.collections.ArrayList, который внутри использует java.util.ArrayList)

Важно: это неизменяемый (read-only) список с точки зрения Kotlin API. Например: List<Int> для listOf(1, 2, 3).

2. Чем отличается ArrayList от LinkedList?

Оба — реализации List, но внутреннее устройство разное.

ArrayList

• Внутри — обычный массив Object[].
• Элементы лежат плотно подряд в памяти.
• Доступ по индексу list[i] — это просто array[i].

Свойства:

• Отличная cache-locality (процессор любит).
• Быстрый случайный доступ: get(i) — O(1).
• При добавлении может быть реаллокация массива (увеличение capacity), но это происходит редко.

LinkedList

Внутри LinkedList является двусвязным списоком, состоящим из Node-ов. Каждый Node хранит: значение, ссылку на следующую ноду, ссылку на предыдующую ноду.

[Node] <-> [Node] <-> [Node]

Свойства:

• Чтобы добраться до index, нужно пройти по цепочке с головы или хвоста.
• Доступ get(i) => O(n).
• Нет крупных realocation, но много мелких объектов, хуже для кэша, больше давления на GC.

3. Сложность добавления

ArrayList

1. Добавление в конец:
   • Амортизированно O(1)
   • Иногда массив перераспределяют (копирование в больший), но в среднем — константа.
2. Добавление в середину/начало (по индексу):

list.add(index, element)

• Нужно сдвинуть хвост массива вправо => O(n)
• Чем ближе к началу — тем больше сдвиг.

LinkedList

1. Добавление в начало/конец:
   • Если у реализации есть ссылки на head/tail => O(1)
   • Создаётся один новый Node, перевязываются ссылки.
2. Добавление в середину по индексу:

list.add(index, element)

• Сначала нужно найти позицию (идём от head или tail) => O(n)
• Вставка после найденного узла сама по себе O(1).

Итого:

• «чистая» вставка по ссылке на узел — O(1)
• но обычно работаешь с индексом, а не с Node => O(n).

4. Сложность удаления из середины

ArrayList

Нужно:

• взять элемент по индексу — O(1)
• сдвинуть всё, что справа, на 1 влево — O(n)

Итого: удаление из середины/начала → O(n)

LinkedList

• Найти Node по индексу => O(n)
• Перевязать prev.next и next.prev => O(1)
• Итого: по индексу => O(n)

Если у тебя уже есть ссылка на узел (итератор/листитер):

• iterator.remove() => O(1)