Какая разница между ArrayList и LinkedList? Когда использовать каждый?

ArrayList vs LinkedList: полное сравнение

Это фундаментальный вопрос о структурах данных в Java, которые постоянно используются в Android разработке. Давай разберёмся в деталях.

Основные различия

ArrayList использует динамический массив как основу, а LinkedList построен на двусвязном списке. Это влияет на все остальное.

Структура и память

ArrayList:

• Хранит элементы в единовременно выделенной области памяти
• При увеличении размера создаёт новый массив (обычно в 1.5 раза больше)
• Все элементы расположены рядом в памяти
• Меньше overhead памяти на элемент

LinkedList:

• Каждый элемент — это узел с ссылками на следующий и предыдущий элемент
• Элементы разбросаны по памяти
• Больше памяти на элемент (две ссылки + данные)

Производительность операций

Доступ по индексу:

val list: List<String> = ...
val element = list[0]  // get(0)

• ArrayList: O(1) — прямой доступ к массиву
• LinkedList: O(n) — нужно пройти по ссылкам

Вставка/удаление в начало:

list.add(0, "element")  // Вставка в начало
list.removeAt(0)        // Удаление из начала

• ArrayList: O(n) — нужно сдвинуть все элементы
• LinkedList: O(1) — просто переставляем ссылки

Вставка/удаление в конец:

list.add("element")     // Добавление в конец
list.removeLast()       // Удаление из конца

• ArrayList: O(1) в среднем (O(n) если нужна реаллокация)
• LinkedList: O(1) — просто переставляем ссылки

Итерация:

for (item in list) {
    println(item)
}

• ArrayList: O(n) — быстрая, элементы подряд в памяти
• LinkedList: O(n) — медленнее, дополнительные переходы по ссылкам

Когда использовать ArrayList

ArrayList лучше в большинстве случаев:

1. Частые обращения по индексу

val scores = mutableListOf(100, 95, 87, 92)
println(scores[2])  // O(1) — хороший выбор

1. Частые итерации

for (item in arrayList) {
    process(item)  // ArrayList быстрее в памяти
}

1. Добавление в конец

data.add(newItem)  // Типичный паттерн в Android

1. Стандартный выбор — используй ArrayList по умолчанию

Когда использовать LinkedList

LinkedList редко, но бывает нужен:

1. Частые операции в начале/середине

// Очередь с удалением из начала
val queue = LinkedList<Task>()
queue.add(task)          // O(1)
val nextTask = queue.removeFirst()  // O(1)

1. Queue/Deque реализация

// LinkedList реализует Deque
val deque: Deque<Int> = LinkedList()
deque.addFirst(1)    // O(1)
deque.removeLast()   // O(1)

1. Постоянные манипуляции в середине

// Но это редкий случай
list.add(50, element)  // Вставка в позицию 50

Практические примеры в Android

Хороший пример с ArrayList:

// Загрузка списка пользователей с сервера
val users = mutableListOf<User>()
networkRepository.fetchUsers().forEach { 
    users.add(it)  // O(1) добавление
}
usersAdapter.submitList(users)  // Итерация O(n)

Пример с LinkedList (очень редко):

// Очередь задач обработки
val taskQueue: Queue<ProcessingTask> = LinkedList()
// Добавляем задачи в конец
taskQueue.offer(task)  // O(1)
// Берём из начала
val task = taskQueue.poll()  // O(1)

Важные замечания для Android

В Android практически всегда используй ArrayList:

• RecyclerView и адаптеры работают лучше с ArrayList
• LiveData и Flow удобнее с List
• Kotlin коллекции по умолчанию ArrayList-подобные
• Память в мобильных устройствах ограничена, LinkedList плохо для кэша

Если нужна Queue или Deque:

// Используй ArrayDeque вместо LinkedList
val deque = ArrayDeque<Int>()
// Это гибрид: структура двусвязного списка, но хранение как массив
// Лучше производительность, меньше памяти

Выводы

1. ArrayList — выбор по умолчанию (95% случаев)
2. LinkedList — только для Queue/Deque при частых операциях с концами
3. ArrayDeque — лучше чем LinkedList для большинства случаев
4. Всегда профилируй код, если сомневаешься

Это базовые знания, которые каждый Android разработчик должен применять на практике ежедневно.