Резюме ArrayList с ArrayDeque предпочтительнее в многих больше вариантов использования, чем LinkedList. Если вы не уверены, & mdash; просто начните с ArrayList.
LinkedList и ArrayList являются двумя различными реализациями интерфейса List. LinkedList реализует его с помощью двусвязного списка. ArrayList реализует его с помощью динамически изменяемого размера массива.
Как и в случае стандартных операций со связанными списками и массивами, различные методы будут иметь разные алгоритмические среды выполнения.
Для LinkedList<E>
get(int index) равно O (n) (при среднем n / 4 шагах) add(E element) - O (1) add(int index, E element) - это O (n) (с в среднем n / 4 шагами),
но O (1) при index = 0 <--- основное преимущество <code>LinkedList<E>remove(int index) - это O (n) (при среднем n / 4 шагах) Iterator.remove() - это O (1) . <--- основное преимущество <code>LinkedList<E>ListIterator.add(E element) - это O (1) Это одно из основных преимуществ LinkedList<E>
Примечание. Для многих операций требуется в среднем n / 4 шагов, константа количество шагов в лучшем случае (например, index = 0) и n / 2 шаги в худшем случае (середина списка)
Для ArrayList<E>
get(int index) равно O (1) <--- основное преимущество <code>ArrayList<E>add(E element) равно O (1) амортизировано, но O (n) в худшем случае, так как размер массива должен быть изменен и скопирован add(int index, E element) равно O (n) (при среднем n / 2 шагах) remove(int index) равно O (n) (при среднем n / 2 шагах) Iterator.remove() равно O (n) (при среднем n / 2 шагах) ListIterator.add(E element) равно O (n) (с n / 2 шагами в среднем)
Примечание: для многих операций требуется в среднем n / 2 шагов, константа количество шагов в лучшем случае (конец списка), n шаги в худшем случае (начало списка)
LinkedList<E> допускает вставки или удаления в постоянное время с использованием итераторов , но только последовательный доступ к элементам. Другими словами, вы можете перемещаться по списку вперед или назад, но нахождение позиции в списке занимает время, пропорциональное размеру списка. Javadoc говорит "операции, которые индексируют в списке, будут проходить по списку с начала или конца, в зависимости от того, что ближе" , поэтому эти методы O (n) ( n / 4 шагов) в среднем, хотя O (1) для index = 0.
ArrayList<E>, с другой стороны, разрешить быстрый произвольный доступ для чтения, так что вы можете получить любой элемент за постоянное время. Но добавление или удаление из любого места, кроме конца, требует сдвига всех последних элементов, чтобы сделать отверстие или заполнить пробел. Кроме того, если вы добавляете больше элементов, чем емкость базового массива, выделяется новый массив (в 1,5 раза больше размера), и старый массив копируется в новый, поэтому добавление в ArrayList равно O (n) в худшем случае, но в среднем постоянно.
Таким образом, в зависимости от операций, которые вы намереваетесь выполнить, вы должны выбрать соответствующие реализации. Перебор любого из списков практически одинаково дешев. (Итерация по ArrayList технически быстрее, но если вы не делаете что-то действительно чувствительное к производительности, вам не стоит об этом беспокоиться - они обе константы.)
Основные преимущества использования LinkedList возникают при повторном использовании существующих итераторов для вставки и удаления элементов. Эти операции затем можно выполнить в O (1) , изменив список только локально. В списке массивов остальная часть массива должна быть перемещена (т.е. скопирована). С другой стороны, поиск в LinkedList означает переход по ссылкам в O (n) ( n / 2 шагов) для наихудшего случая, тогда как в ArrayList желаемый позиция может быть вычислена математически и доступна в O (1) .
Другое преимущество использования LinkedList возникает, когда вы добавляете или удаляете из заголовка списка, поскольку эти операции O (1) , тогда как они O (n) для ArrayList. Обратите внимание, что ArrayDeque может быть хорошей альтернативой LinkedList для добавления и удаления из головы, но это не List.
Кроме того, если у вас большие списки, имейте в виду, что использование памяти также отличается. Каждый элемент LinkedList имеет больше накладных расходов, так как указатели на следующий и предыдущий элементы также сохраняются. ArrayLists нет этих накладных расходов. Однако ArrayLists занимает столько памяти, сколько выделено для емкости, независимо от того, были ли элементы фактически добавлены.
Начальная емкость по умолчанию ArrayList довольно мала (10 из Java 1.4 - 1.8). Но поскольку базовая реализация представляет собой массив, размер массива должен быть изменен, если вы добавите много элементов. Чтобы избежать высокой стоимости изменения размера, когда вы знаете, что собираетесь добавить много элементов, создайте ArrayList с более высокой начальной емкостью.