Какой из них работает быстрее, ArrayList или LinkedList?

List li = new LinkedList();

for (int i = 0; i &lt; 100; i++) {
    li.add(i);
}

long start1 = System.nanoTime();
li.get(57);

long end1 = System.nanoTime();
long diff1 = end1-start1;

System.out.println("Time taken by LinkedList = "+diff1);

List al = new ArrayList();
for (int i = 0; i < 100; i++) {
    al.add(i);
}

Какие операции я выполняю в обоих списках, когда я распечатываю время, ArrayList всегда работает быстрее, чем LinkedList. Может ли кто-нибудь объяснить, что лучше работает с точки зрения времени? Также дайте мне знать, если что-то не так в коде. Спасибо!

Ответ 1

Если вам нужно выполнить много вставок и не очень частого поиска, используйте LinkedList. Используйте ArrayList, если вы выполняете больше поиска, чем вставки.

Причина такова: ArrayList поддерживается массивом, который имеет начальную емкость. Таким образом, если вы продолжаете вставлять элементы в список, в какой-то момент ему придется повторно настроить его емкость массива для размещения вновь вставленных элементов, а также, возможно, придется перемещать существующие элементы, если вы выполняете индексированные вставки. С другой стороны, LinkedList поддерживается связанным списком, где создание элемента всегда выполняется в постоянное время - создайте элемент и назначьте его в конец списка. Здесь не происходит повторной настройки.

Теперь, чтобы получить элемент из ArrayList, он всегда будет занимать постоянное время, так как он может легко индексировать массив поддержки в постоянное время. Но выбор элемента из LinkedList может привести к тому, что вы пройдете весь связанный список, чтобы найти элемент node. В результате в этом случае он выполняет менее ArrayList.

Из приведенного выше обсуждения вы можете видеть, что когда у вас больше вложений, LinkedList всегда превосходит ArrayList, потому что у последнего есть внутренняя стоимость изменения размера, связанная со вставками, а первая - нет. С другой стороны, если у вас есть редкие вставки и часто встречающиеся запросы, ArrayList всегда превосходит LinkedList, потому что для последнего вам, возможно, придется пройти всю структуру связанного списка, чтобы найти нужный элемент, в то время как первый сможет быстро найдите свои элементы с индексированием массива в постоянные моменты времени.

Все вышеупомянутые эффекты будут видны и будут влиять на производительность вашего приложения, когда вы имеете дело с большим количеством предметов (например, тысяч предметов). Для меньшего количества элементов разница в производительности не совсем понятна.

Теперь, о вашем коде, у вас есть серьезные проблемы с ним. Для стартера вы используете сырой тип, что плохо, поскольку вы теряете всю безопасность типов, которую могут предложить дженерики. Вы всегда должны использовать общую версию API Collection при написании нового кода. Итак, измените свой код следующим образом:

List<Integer> li = new LinkedList<Integer>();
for (int i = 0; i < 100; i++) {
    li.add(i);
}

long start1 = System.nanoTime();
li.get(57);

long end1 = System.nanoTime();
long diff1 = end1 - start1;

System.out.println("Time taken by LinkedList = "+diff1);

List<Integer> al = new ArrayList<Integer>();
for (int i = 0; i < 100; i++) {
    al.add(i);
}

См. Эффективная Java. Пункт 23: Не используйте необработанные типы в новом коде для подробного объяснения.

ИЗМЕНИТЬ

Из обсуждения в комментариях вам должно быть очевидно, что если вам нужно вставить элементы в середине списка или в произвольной позиции, то ArrayList превосходит LinkedList с точки зрения производительности, поскольку бывший будет использовать memcpy, чтобы сместить элементы, которые являются чрезвычайно быстрыми, и последний должен пройти до нужного индекса, чтобы правильно вставить новый элемент, который медленнее. Таким образом, для случайных вставок ArrayList также превосходит LinkedList. Единственный случай LinkedList превосходит ArrayList, если вы только вставляете в конце своего списка, и есть много этих вставок.

Ответ 2

ArrayList поддерживается массивом и LinkedList с поддержкой Node, связанным с refernece.

Таким образом, операция на ArrayList - операция actaully evalute в массиве. Операция add работает в режиме амортизированного постоянного времени, то есть для добавления n элементов требуется время O(n). Все остальные операции выполняются в линейном времени (грубо говоря). Постоянный коэффициент является низким по сравнению с тем, что для реализации LinkedList.

и LinkedList все операции выполняются так, как можно было бы ожидать для двусвязного списка. Операции, которые индексируются в список, будут перемещаться по списку от начала или до конца, в зависимости от того, что ближе к указанному индексу.

Подробнее о документации -

Ответ 3

Список массивов будет всегда быстрее, чем Связанный список с точки зрения чтения. ArrayList - это в основном реализация массива, и память, выделенная для массива, последовательно считывается быстрее. Но когда вы используете список, который требует вставки или удаления между списком, тогда Linked List выполняется быстрее. Потому что ему просто нужно было добавлять ссылки между узлами. В этих двух случаях список массивов будет медленнее. Использование может быть:

ArrayList - более быстрая операция чтения, вставка, удаление между списком происходит медленнее. Связанный список - медленная работа чтения по сравнению с массивом, но вставка, удаление между списком выполняется быстрее.

Ответ 4

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

Если вы знаете размер inital, тогда передайте его ArrayList при создании, он избегает восстановления массива как новый ArrayList (100);