Я узнал, что добавление элемента в конец 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, короче говоря, отстой. Это доказательство или я что-то упускаю?
Большинство реализаций связанных списков хранят хвостовой указатель в заголовке списка, чтобы найти последний элемент за одну операцию. Это верно для Java-реализации LinkedList<>, по крайней мере, в исходном коде, который я видел.
@WJS, если нам нужно перебирать список, означает ли это, что LinkedList равен O (n)? чем их больше, тем больше нам приходится перебирать?
@IvanSyrups Не обязательно. Big O говорит о производительности чего-либо. Но нельзя говорить о производительности связанного списка отдельно. Это зависит от того, что вы делаете.
@Гость. В реализации HashMap отдельные корзины представляют собой связанные списки, и вы обычно просто добавляете новые записи впереди. По крайней мере, так было раньше (давно не проверял). Но тогда еще не было хвостового указателя.
@WJS LinkedList — это двусвязный список (так говорит javadoc), и список имеет ссылки как на начало, так и на конец списка, поэтому добавление к списку всегда O (1), поскольку ему никогда не нужно «перебирать список, чтобы найти конец». --- Вопрос конкретно о реализации LinkedList
, а не о какой-либо другой реализации связанного списка в HashMap
, так что эта ссылка полностью отсутствует и не имеет отношения к вопросу.
@Andreas, а не о какой-либо другой реализации связанного списка в HashMap. Это ваше мнение. Я не согласен.
@WJS Код принимает List
в качестве параметра. В вопросе упоминаются ArrayList
и LinkedList
. Там нет упоминания о Map
, не говоря уже о HashMap
, или о том, как хэш-карта обрабатывает коллизии, поэтому я очень озадачен, почему вы думаете, что этот вопрос каким-либо образом касается связанного списка потенциальной обработки коллизий за хешем. ведро карты.
Для добавления элемента в массив (который не требует изменения размера) требуется скопировать ссылку в пустую ячейку и увеличить количество элементов объекта в массиве.
Добавление элемента в связанный список требует выделения нового узла, указания «следующей» ссылки предыдущей последней записи на новую последнюю запись, обнуления «следующей» новой записи, указания «последней» ссылки головы на новую запись и указание предыдущей ссылки новой записи на предыдущую последнюю запись. А затем копирование ссылки на объект в новый узел и увеличение количества элементов в списке.
Короче говоря, связанный список требует выделения и на 4 записи больше, чем версия массива.
Однако, если вы считаете, что связанные списки — это отстой, попробуйте использовать массив в ситуации, когда вы постоянно удаляете передний элемент из своего массива из 10 миллионов записей.
Существуют методы, позволяющие избежать перетасовки всех элементов массива, но если это не круговой массив, он, вероятно, будет перетасовываться. Исходники ArrayList, которые я видел, перемешиваются, поэтому удаление первой из 10 000 000 записей приведет к перемещению оставшихся 9 999 999 записей вниз. А удаление следующей записи приведет к перемещению оставшихся 9 999 998 записей вниз...
Не говоря уже о том, что ваш массив из 10 миллионов записей должен иметь возможность получить непрерывные 40 или 80 мегабайт памяти.
Урок в том, что у разных структур данных есть разные точки соприкосновения.
Спасибо и урок очень ценен! Я думаю, именно поэтому очереди — это LinkedLists, а не ArrayLists!
Если вам нужен круговой буфер, используйте ArrayDeque
, потому что это именно то, что нужно.
@IvanSyrups - Если ответ полезен (или он самый полезный из нескольких ответов), вы можете принять его . Этот шаг совершенно необязателен, но рекомендуется.
Это деталь реализации, но большинство JVM имеют заголовок объекта, который требует двух дополнительных операций записи при выделении узла списка в случае LinkedList
.
Короткий ответ заключается в том, что массивы представляют собой структуры данных с произвольным доступом. Связанные списки — нет. Итак, в последнем случае, если это не Deque, вам нужно перебрать список, чтобы найти конец.