Выполняют ли array (или ArrayList) и LinkedList одно и то же при итерации?

Я знаю, что массивы быстрее получают и настраивают, в то время как LinkedLists лучше при добавлении и удалении элементов, но как насчет итерации? Более «традиционный» for(i=0;i<intList.size();i++) определенно сделал бы LinkedLists медленнее, так как вам каждый раз приходилось бы получать элемент с индексом i. Но что, если я использую for(int i : intList)? Как это работает под капотом для этого экземпляра? Например:

LinkedList<Integer> intList = new LinkedList();
/*
populate list...
*/
for (int i : intList) {
    //do stuff
}

Я полагаю, что нет необходимости получать конкретный элемент при просмотре всего списка, поэтому должна быть возможность иметь какую-то реализацию цикла, где производительность примерно такая же. Хотя я не знаю, как именно реализован for для этого примера, поэтому я не могу быть уверен, что это так.

Для итерации они оба равны O (1). Если вы хотите получить доступ к случайному индексу, то LinkedList - это O (n), а ArrayList - O (1).

Elliott Frisch 09.04.2018 01:01

На практике Arraylist будет работать быстрее практически во всех отношениях, за исключением добавления / удаления элементов в начале или середине большого списка.

Magnus 09.04.2018 01:06

как насчет исходного кода этих классов, который четко отвечает на этот вопрос, вы не поняли?

user177800 09.04.2018 01:14

Точный дубликат - Когда использовать LinkedList вместо ArrayList?

user177800 09.04.2018 01:15

асимптотика такие же. Постоянные факторы, вероятно, в значительной степени благоприятствуют ArrayList.

Louis Wasserman 09.04.2018 01:18
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
5
5
156
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Оба они выполняют итерацию с одинаковой скоростью, O (1) при использовании foreach. Для получения дополнительной информации прочтите эта почта.

Другие вопросы по теме