Почему добавление элемента в конец LinkedList занимает больше времени, чем ArrayList?

Я узнал, что добавление элемента в конец LinkedList — это O (1), так как мы просто добавляем привязку объекта к последнему узлу списка. ArrayList также равен O (1), но в худшем случае — O (n ) из-за необходимости изменять размер, когда в массиве нет места. Я попытался проверить это, ожидая результатов, которые я узнал, но ArrayList значительно быстрее добавлял 10 миллионов элементов, чем LinkedList.

После нескольких попыток ArrayList занял около 570 мс, а LinkedList — около 1900 мс.

public static void listPractice(List<String> test) {
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < 10_000_000; i++) {
        test.add(String.valueOf(i));
    }
    System.out.println(System.currentTimeMillis() - startTime);

}

Кажется очень странным. Я читал другие обсуждения и вижу, что многие программисты говорят, что LinkedList, короче говоря, отстой. Это доказательство или я что-то упускаю?

Короткий ответ заключается в том, что массивы представляют собой структуры данных с произвольным доступом. Связанные списки — нет. Итак, в последнем случае, если это не Deque, вам нужно перебрать список, чтобы найти конец.

WJS 12.12.2020 00:20

Большинство реализаций связанных списков хранят хвостовой указатель в заголовке списка, чтобы найти последний элемент за одну операцию. Это верно для Java-реализации LinkedList<>, по крайней мере, в исходном коде, который я видел.

a guest 12.12.2020 00:23

@WJS, если нам нужно перебирать список, означает ли это, что LinkedList равен O (n)? чем их больше, тем больше нам приходится перебирать?

Ivan Syrups 12.12.2020 00:26

@IvanSyrups Не обязательно. Big O говорит о производительности чего-либо. Но нельзя говорить о производительности связанного списка отдельно. Это зависит от того, что вы делаете.

WJS 12.12.2020 00:35

@Гость. В реализации HashMap отдельные корзины представляют собой связанные списки, и вы обычно просто добавляете новые записи впереди. По крайней мере, так было раньше (давно не проверял). Но тогда еще не было хвостового указателя.

WJS 12.12.2020 00:43

@WJS LinkedList — это двусвязный список (так говорит javadoc), и список имеет ссылки как на начало, так и на конец списка, поэтому добавление к списку всегда O (1), поскольку ему никогда не нужно «перебирать список, чтобы найти конец». --- Вопрос конкретно о реализации LinkedList, а не о какой-либо другой реализации связанного списка в HashMap, так что эта ссылка полностью отсутствует и не имеет отношения к вопросу.

Andreas 12.12.2020 02:10

@Andreas, а не о какой-либо другой реализации связанного списка в HashMap. Это ваше мнение. Я не согласен.

WJS 12.12.2020 03:14

@WJS Код принимает List в качестве параметра. В вопросе упоминаются ArrayList и LinkedList. Там нет упоминания о Map, не говоря уже о HashMap, или о том, как хэш-карта обрабатывает коллизии, поэтому я очень озадачен, почему вы думаете, что этот вопрос каким-либо образом касается связанного списка потенциальной обработки коллизий за хешем. ведро карты.

Andreas 12.12.2020 04:37
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
0
8
517
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

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

Для добавления элемента в массив (который не требует изменения размера) требуется скопировать ссылку в пустую ячейку и увеличить количество элементов объекта в массиве.

Добавление элемента в связанный список требует выделения нового узла, указания «следующей» ссылки предыдущей последней записи на новую последнюю запись, обнуления «следующей» новой записи, указания «последней» ссылки головы на новую запись и указание предыдущей ссылки новой записи на предыдущую последнюю запись. А затем копирование ссылки на объект в новый узел и увеличение количества элементов в списке.

Короче говоря, связанный список требует выделения и на 4 записи больше, чем версия массива.

Однако, если вы считаете, что связанные списки — это отстой, попробуйте использовать массив в ситуации, когда вы постоянно удаляете передний элемент из своего массива из 10 миллионов записей.

Существуют методы, позволяющие избежать перетасовки всех элементов массива, но если это не круговой массив, он, вероятно, будет перетасовываться. Исходники ArrayList, которые я видел, перемешиваются, поэтому удаление первой из 10 000 000 записей приведет к перемещению оставшихся 9 999 999 записей вниз. А удаление следующей записи приведет к перемещению оставшихся 9 999 998 записей вниз...

Не говоря уже о том, что ваш массив из 10 миллионов записей должен иметь возможность получить непрерывные 40 или 80 мегабайт памяти.

Урок в том, что у разных структур данных есть разные точки соприкосновения.

Спасибо и урок очень ценен! Я думаю, именно поэтому очереди — это LinkedLists, а не ArrayLists!

Ivan Syrups 12.12.2020 00:24

Если вам нужен круговой буфер, используйте ArrayDeque, потому что это именно то, что нужно.

Andreas 12.12.2020 02:16

@IvanSyrups - Если ответ полезен (или он самый полезный из нескольких ответов), вы можете принять его . Этот шаг совершенно необязателен, но рекомендуется.

andrewJames 12.12.2020 02:17

Это деталь реализации, но большинство JVM имеют заголовок объекта, который требует двух дополнительных операций записи при выделении узла списка в случае LinkedList.

Holger 14.12.2020 15:12

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