1.ArrayList реализует структуру данных на основе динамических массивов, а LinkedList реализует структуру данных на основе связанных списков.
2. Для произвольного доступа для получения и установки ArrayList лучше, чем LinkedList, поскольку ArrayList может располагаться случайным образом, в то время как LinkedList необходимо шаг за шагом перемещать указатель на узел. (Подумайте со ссылкой на массивы и связанные списки)
3. Для операций добавления и удаления нового и удаления более предпочтителен LinedList. Ему нужно только изменить указатель, а ArrayList необходимо переместить данные, чтобы заполнить пространство удаленного объекта.
ArrayList и LinkedList — это два класса коллекций, используемые для хранения серии ссылок на объекты. Например, мы можем использовать ArrayList для хранения серии строк или целых чисел. Так в чем же разница в производительности между ArrayList и LinkedList? Когда следует использовать ArrayList, а когда — LinkedList?
один. временная сложность
Первый ключевой момент заключается в том, что внутренняя реализация ArrayList основана на базовом массиве объектов. Поэтому, когда он использует метод get для доступа к любому элементу списка (произвольный доступ), он работает быстрее, чем LinkedList. Метод get в LinkedList проверяет порядок от одного конца списка до другого. Для LinkedList не существует более быстрого способа доступа к определенному элементу списка.
Предположим, у нас есть большой список, и элементы в нем отсортированы. Этот список может иметь тип ArrayList или LinkedList. Теперь мы выполняем двоичный поиск по этому списку. Для скорости запроса ArrayList и LinkedList. см. следующую программу:
LinkedList затрачено времени: 2596
Этот результат не фиксируется, но по сути время у ArrayList существенно меньше, чем у LinkedList. Поэтому LinkedList в этом случае использовать не следует. Метод двоичного поиска использует стратегию произвольного доступа (произвольного доступа), а LinkedList не поддерживает быстрый произвольный доступ. Время, затрачиваемое на произвольный доступ к LinkedList, пропорционально размеру списка. Соответственно, время, затраченное на произвольный доступ в ArrayList, фиксировано.
Означает ли это, что ArrayList всегда работает лучше, чем LinkedList? Это не обязательно так: в некоторых случаях LinkedList работает лучше, чем ArrayList, а некоторые алгоритмы более эффективны при реализации в LinkedList. Например, производительность повышается при использовании метода Collections.reverse для реверсирования списка.
Посмотрите на такой пример: если у нас есть список и мы хотим выполнить над ним большое количество операций вставки и удаления, в этом случае LinkedList — лучший выбор. Рассмотрим следующий крайний пример, где мы неоднократно вставляем элемент в начало списка:
На данный момент мой вывод: ArrayList занимает: 2463.
LinkedList занимает: 15
Это полностью противоположно результату предыдущего примера. При добавлении элемента в начало ArrayList все существующие элементы будут перемещены назад, что означает накладные расходы на перемещение и копирование данных. Напротив, добавление элемента в начало LinkedList просто присваивает элементу запись, а затем настраивает две ссылки. Стоимость добавления элемента в начало LinkedList фиксирована, а стоимость добавления элемента в начало ArrayList пропорциональна размеру ArrayList.
два. космическая сложность
В LinkedList есть закрытый внутренний класс, определенный следующим образом:
частный статический класс Entry {
Элемент объекта;
Вход следующий;
Запись предыдущая;
}
Каждый объект Entry ссылается на элемент в списке, а также на его предыдущий элемент и следующий элемент в LinkedList. Объект LinkedList с 1000 элементами будет иметь 1000 связанных между собой объектов Entry, каждый объект соответствует элементу в списке. В этом случае в структуре LinkedList будет много места, поскольку необходимо хранить соответствующую информацию об этих 1000 объектах Entity.
ArrayList использует встроенный массив для хранения элементов. Начальная емкость этого массива равна 10. Когда массиву необходимо увеличиться, новая емкость получается по следующей формуле: новая емкость = (старая емкость*3)/2+. 1, то есть емкость будет увеличиваться примерно на 50% каждый раз. Это означает, что если у вас есть объект ArrayList с большим количеством элементов, вы потеряете много места. Эта трата вызвана тем, как работает ArrayList. Если для хранения нового элемента недостаточно места, массив придется перераспределить, чтобы можно было добавить новый элемент. Перераспределение массива приведет к резкому падению производительности. Если мы знаем, сколько элементов будет иметь ArrayList, мы можем указать емкость через конструктор. Мы также можем использовать метод TrimToSize для удаления неиспользуемого пространства после выделения ArrayList.
три. Подвести итог
Каждый из ArrayList и LinkedList имеет свои преимущества и недостатки с точки зрения производительности, и каждый из них имеет свое собственное применение. В целом его можно описать следующим образом.
Краткое описание производительности:
| - | операция добавления() | операция удаления() | операция вставки | операция значения индекса | операция значения итератора |
|---|---|---|---|---|---|
| ArrayList/Вектор/Стек | хороший | Разница | Разница | Отличный | Отличный |
| Связанный список | хороший | хороший | хороший | Разница | Отличный |
1. Как для ArrayList, так и для LinkedList стоимость добавления элемента в конец списка фиксирована. Для ArrayList в основном добавляется элемент во внутренний массив, указывающий на добавленный элемент, что иногда может привести к перераспределению массива; для LinkedList эти издержки являются единообразными, выделяя внутренний объект Entry.
2. Вставка или удаление элемента в середине ArrayList означает, что оставшиеся элементы в списке будут перемещены, а вставка или удаление элемента в середине LinkedList имеет фиксированную стоимость.
3． LinkedList не поддерживает эффективный доступ к произвольным элементам.
4． Потеря пространства в ArrayList в основном отражается в резервировании определенного количества места в конце списка, тогда как потребление пространства в LinkedList отражается в том, что каждый его элемент должен занимать значительный объем места.
Это можно сказать так: когда операция заключается в добавлении данных после столбца данных, а не в начале или середине, и вам необходимо получить произвольный доступ к элементам, использование ArrayList обеспечит лучшую производительность, когда ваша операция находится перед; столбец данных. Когда вы добавляете или удаляете данные посередине и получаете доступ к элементам по порядку, вам следует использовать LinkedList.
Разница между ArrayList и List в Java
Коллекция списков
Список наследует интерфейс Collection. Список представляет собой упорядоченную коллекцию. Элементы в списке можно получить/удалить/вставить на основе индекса (порядковый номер: информация о положении элемента в коллекции).
В отличие от коллекции Set, List допускает дублирование элементов. Элементы объекта e1 и e2, соответствующие условиям e1.equals(e2), могут существовать в коллекции List одновременно. Конечно, существуют также классы реализации List, которые не допускают дублирования элементов.
В то же время List также предоставляет метод listIterator(), который возвращает объект интерфейса ListIterator. По сравнению с интерфейсом Iterator, ListIterator добавляет методы для добавления, удаления и установки элементов, а также может перемещаться вперед или назад.
Связь между списком и коллекцией:
java.util.Коллекция[I]
+--java.util.Список[I]
+--java.util.ArrayList [C]
+--java.util.LinkedList [C]
+--java.util.Вектор [C]
+--java.util.Stack [C]
Классы реализации интерфейса List в основном включают ArrayList, LinkedList, Vector, Stack и т. д.
Отношения отца и сына.
List — это интерфейс, а ArrayList наследует этот интерфейс и реализует его.
При его использовании я обычно использую ArrayList. Я никогда не использовал List. Вы можете использовать его следующим образом: List list = new ArrayList();
Интерфейс коллекции
Коллекция — это самый простой интерфейс коллекции. Коллекция представляет собой набор объектов, то есть элементов коллекции. Некоторые коллекции допускают идентичные элементы, а другие — нет. Некоторые вроде, а другие нет. Java SDK не предоставляет классы, которые напрямую наследуются от Collection. Все классы, предоставляемые Java SDK, представляют собой «подинтерфейсы», наследуемые от Collection, такие как List и Set.
Все классы, реализующие интерфейс Collection, должны предоставлять два стандартных конструктора: конструктор без параметров для создания пустой Collection и конструктор параметров Collection для создания новой Collection. Входная коллекция содержит те же элементы. Последний конструктор позволяет пользователю копировать коллекцию.
Как перебирать каждый элемент коллекции? Независимо от фактического типа коллекции, он поддерживает метод iterator(), который возвращает итератор, который можно использовать для доступа к каждому элементу коллекции один за другим. Типичное использование выглядит следующим образом:
Итератор it = Collection.iterator(); // Получаем итератор.
в то время как (it.hasNext ()) {
Object obj = it.next(); // Получаем следующий элемент.
}
Два интерфейса, производные от интерфейса Collection, — это List и Set.
Интерфейс списка:
Список представляет собой упорядоченную коллекцию. Используя этот интерфейс, вы можете точно контролировать позицию вставки каждого элемента. Пользователи могут получать доступ к элементам в списке, используя индекс (положение элемента в списке, аналогичный нижнему индексу массива), который аналогичен массиву Java.
В отличие от упомянутого ниже Set, List допускает те же элементы.
В дополнение к методу iterator(), необходимому для интерфейса Collection, List также предоставляет метод listIterator(), который возвращает интерфейс ListIterator. По сравнению со стандартным интерфейсом Iterator, ListIterator имеет еще несколько методов add() и других, позволяющих добавлять дополнения. Удаление, установка элементов и перемещение вперед или назад.
Распространенными классами, реализующими интерфейс List, являются LinkedList, ArrayList, Vector и Stack.
Класс LinkedList
LinkedList реализует интерфейс List и допускает нулевые элементы. Кроме того, LinkedList предоставляет дополнительные методы получения, удаления и вставки в начале или конце LinkedList. Эти операции позволяют использовать LinkedList в качестве стека, очереди или двухсторонней очереди.
Обратите внимание, что LinkedList не имеет синхронизированных методов. Если несколько потоков одновременно обращаются к списку, они должны сами реализовать синхронизацию доступа. Одним из обходных путей является создание синхронизированного списка при создании списка:
Список списка = Collections.synchronizedList(new LinkedList(...));
Класс ArrayList
ArrayList реализует массивы переменного размера. Он допускает все элементы, включая null. ArrayList не синхронизирован.
Время выполнения методов size, isEmpty, get и set является постоянным. Однако стоимость метода добавления является амортизируемой константой, а добавление n элементов требует времени O(n). Другие методы имеют линейное время работы.
Каждый экземпляр ArrayList имеет емкость (Capacity), которая представляет собой размер массива, используемого для хранения элементов. Эта емкость увеличивается автоматически по мере добавления новых элементов, но алгоритм роста не определен. Если необходимо вставить большое количество элементов, можно вызвать метод обеспеченияКапасити, чтобы увеличить емкость ArrayList перед вставкой и повысить эффективность вставки.
Как и LinkedList, ArrayList также не синхронизирован.
Резюме: Если задействованы такие операции, как стеки и очереди, вам следует рассмотреть возможность использования List. Если вам нужно быстро вставлять и удалять элементы, вам следует использовать LinkedList. Если вам нужен быстрый произвольный доступ к элементам, вам следует использовать ArrayList.
Попробуйте вернуть интерфейс, а не фактический тип, например вернуть List вместо ArrayList, чтобы, если в будущем вам понадобится заменить ArrayList на LinkedList, клиентский код не нужно было менять. Это программирование для абстракции.