Когда использовать ArrayList, а когда LinkedList

ArrayList с ArrayDeque предпочтительнее во многих других случаях использования, чем LinkedList. Если вы не уверены - начните с ArrayList.

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

LinkedList и ArrayList - две разные реализации интерфейса List. LinkedList реализует его с помощью двусвязного списка. ArrayList реализует его с помощью массива динамического изменения размера.

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

Для LinkedList<E>

• get(int index) равно O(n) (в среднем n/4 шагов), но O(1), когда index = 0 или index = list.size() - 1 (в этом случае вы также можете использовать getFirst() и getLast()). Одно из основных преимуществ LinkedList<E>
• add(int index, E element) равно O(n) (в среднем n/4 шагов), но O(1), когда index = 0 или index = list.size() - 1 (в этом случае вы также можете используйте addFirst() и addLast()/add()). Одно из основных преимуществ LinkedList<E>
• remove(int index) равен O(n) (в среднем n/4 шагов), но O(1), когда index = 0 или index = list.size() - 1 (в этом случае вы также можете использовать removeFirst() и removeLast()). Одно из основных преимуществ LinkedList<E>
• Iterator.remove() - это O(1). Одно из основных преимуществ LinkedList<E>
• ListIterator.add(E element) равен O(1). Одно из основных преимуществ LinkedList<E>

Примечание: многие операции требуют в среднем n/4 шагов, постоянного количества шагов в лучшем случае (например, index = 0) и n/2 шагов в худшем случае (середина списка).

Для ArrayList<E>

• get(int index) равен O(1). Основное преимущество 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) в худшем случае, но в среднем постоянное.

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

Основные преимущества использования LinkedList возникают, когда вы повторно используете существующие итераторы для вставки и удаления элементов. Затем эти операции можно выполнить в O(1), изменив список только локально. В списке массивов оставшуюся часть массива необходимо переместить (т.е. скопировать). С другой стороны, поиск в LinkedList означает переход по ссылкам в O(n) (n/2 шагов) в худшем случае, тогда как в ArrayList желаемая позиция может быть вычислена математически и доступна в O(1).

Еще одно преимущество использования LinkedList возникает, когда вы добавляете или удаляете из заголовка списка, так как эти операции O(1), а для ArrayList они O(n). Обратите внимание, что ArrayDeque может быть хорошей альтернативой LinkedList для добавления и удаления из головы, но это не список.

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

По умолчанию начальная емкость ArrayList довольно мала (10 из Java 1.4 - 1.8). Но поскольку базовая реализация представляет собой массив, размер массива необходимо изменить, если вы добавляете много элементов. Чтобы избежать больших затрат на изменение размера, когда вы знаете, что собираетесь добавить много элементов, создайте ArrayList с большей начальной емкостью.

Если для понимания двух структур используется перспектива структур данных, LinkedList в основном представляет собой последовательную структуру данных, которая содержит головной узел. Узел - это оболочка для двух компонентов: значения типа T (принимаемого через универсальные шаблоны) и другой ссылки на узел, связанный с ним. Итак, мы можем утверждать, что это рекурсивная структура данных (узел содержит другой узел, у которого есть другой узел, и так далее ...). Добавление элементов в LinkedList занимает линейное время, как указано выше.

ArrayList - это растущий массив. Это похоже на обычный массив. Под капотом, когда элемент добавляется по индексу i, он создает другой массив с размером, который на 1 больше, чем предыдущий размер (так в общем случае, когда n элементов должны быть добавлены в ArrayList, новый массив размера предыдущего размера плюс n создается). Затем элементы копируются из предыдущего массива в новый, и элементы, которые должны быть добавлены, также помещаются в указанные индексы.

---

Читайте также:

• Коллекции, предоставляемые интерфейсом Map в Java
• Интерфейс Collection в Java
• Интерфейс Collection: коллекции представлений, неизменяемые коллекции

Канал в Телеграм