Что такое LinkedList?

LinkedList — структура данных с двусвязным списком

LinkedList — это коллекция в Java/Kotlin, которая реализует интерфейс List и Deque на основе двусвязного списка. В отличие от ArrayList, LinkedList хранит элементы не в виде непрерывного массива, а в виде связанных узлов, где каждый узел содержит ссылку на предыдущий и следующий элемент.

Особенности LinkedList

Структура:

• Каждый узел содержит: значение, ссылку на предыдущий узел (prev) и ссылку на следующий узел (next)
• Первый узел называется head (голова), последний — tail (хвост)
• Начало и конец списка связаны с null

Преимущества:

• O(1) для вставки/удаления в начало или конец (если есть ссылки на head и tail)
• O(1) для добавления в любую позицию (если уже позиция известна)
• Динамический размер — не нужно пересоздавать внутренний массив при расширении
• Экономит память, если много операций insert/delete

Недостатки:

• O(n) для доступа к элементу по индексу (нужно пройти от начала)
• O(n) для поиска элемента
• Больше памяти на узлы (каждый узел содержит две ссылки)
• Медленнее ArrayList на случайный доступ

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

// ✅ Хорошо — часто добавляешь в начало/конец
val queue = LinkedList<String>()
queue.addFirst("element1")
queue.addLast("element2")
val first = queue.removeFirst()

// ❌ Плохо — часто обращаешься по индексу
val list = LinkedList<String>()
for (i in 0 until list.size) {
    println(list[i]) // O(n) для каждого обращения!
}

// ✅ Хорошо — используй итератор
for (element in list) {
    println(element) // O(1)
}

LinkedList vs ArrayList

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

В Android разработке LinkedList используется редко, так как большинство задач связано с отображением данных в RecyclerView (доступ по индексу). Предпочитают ArrayList, MutableList или Flow для работы с последовательностями.