Mediumarraylistlinkedlist
Чем ArrayList отличается от LinkedList?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
ArrayList — массив под капотом, растёт ×1.5. LinkedList — двусвязный список узлов.
Операция ArrayList LinkedList
get(i) O(1) O(n)
add(e) (конец) O(1)* O(1)
add(i, e)/remove O(n) O(n) (поиск узла)
memory мало большой overhead (объект + 2 указателя)
cache locality отлично плохоList<String> arr = new ArrayList<>(); // почти всегда предпочтительнее
List<String> lnk = new LinkedList<>(); // для частых вставок в начало/конец- *add(e) в ArrayList — амортизировано O(1) (reallocation редко);
ArrayDequeлучшеLinkedListдля дека;- ArrayList: меньше memory, cache locality, быстрее random access;
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.