ArrayList предпочтительнее во многих случаях использования, чем LinkedList. Если вы не уверены - начните с ArrayList.
В ArrayList доступ к элементу занимает линейное время, а добавление элемента занимает время O(n) (худший случай). В LinkedList добавление элемента занимает O(n) времени, а доступ также занимает O(n) времени, но LinkedList использует больше памяти, чем ArrayList.
LinkedList и ArrayList - две разные реализации интерфейса List. LinkedList реализует его с помощью двусвязного списка. ArrayList реализует его с помощью массива динамического изменения размера.
Как и в случае стандартных операций со связанными списками и массивами, различные методы будут иметь разное время выполнения алгоритмов.
LinkedList<E> позволяет вставлять или удалять за постоянное время с помощью итераторов, но только для последовательного доступа к элементам. Другими словами, вы можете перемещаться по списку вперед или назад, но поиск позиции в списке требует времени, пропорционального размеру списка. Javadoc говорит: «операции, которые индексируют в списке, будут проходить по списку от начала или до конца, в зависимости от того, что ближе», поэтому эти методы в среднем составляют O(n), хотя O(1) для index = 0.
ArrayList<E>, с другой стороны, обеспечивает быстрый произвольный доступ для чтения, поэтому вы можете захватить любой элемент за постоянное время. Но добавление или удаление откуда угодно, кроме конца, требует смещения всех последних элементов, чтобы сделать отверстие или заполнить пробел. Кроме того, если вы добавляете больше элементов, чем емкость базового массива, выделяется новый массив (в 1,5 раза больше размера), а старый массив копируется в новый, поэтому добавление в ArrayList составляет O(n) в худшем случае, но в среднем постоянное.
Итак, в зависимости от операций, которые вы собираетесь выполнять, вам следует выбрать соответствующие реализации. Перебор любого типа List практически одинаково дешев. (Итерации по ArrayList технически быстрее, но если вы не делаете что-то действительно чувствительное к производительности, вам не стоит об этом беспокоиться - они обе константы.)
Основные преимущества использования LinkedList возникают, когда вы повторно используете существующие итераторы для вставки и удаления элементов. Затем эти операции можно выполнить в O(1), изменив список только локально. В списке массивов оставшуюся часть массива необходимо переместить (т.е. скопировать). С другой стороны, поиск в LinkedList означает переход по ссылкам в O(n) в худшем случае, тогда как в ArrayList желаемая позиция может быть вычислена математически и доступна в O(1).
Еще одно преимущество использования LinkedList возникает, когда вы добавляете или удаляете из заголовка списка, так как эти операции O(1), а для ArrayList они O(n). Обратите внимание, что ArrayDeque может быть хорошей альтернативой LinkedList для добавления и удаления из головы, но это не список.
Кроме того, если у вас большие списки, имейте в виду, что использование памяти также отличается. Каждый элемент LinkedList имеет больше накладных расходов, поскольку указатели на следующий и предыдущий элементы также сохраняются. ArrayLists не имеют этих накладных расходов. Однако списки ArrayLists занимают столько памяти, сколько выделено для емкости, независимо от того, были ли элементы добавлены на самом деле.
Если для понимания двух структур используется перспектива структур данных, LinkedList в основном представляет собой последовательную структуру данных, которая содержит головной узел. Узел - это оболочка для двух компонентов: значения типа T (принимаемого через универсальные шаблоны) и другой ссылки на узел, связанный с ним. Итак, мы можем утверждать, что это рекурсивная структура данных (узел содержит другой узел, у которого есть другой узел, и так далее ...). Добавление элементов в LinkedList занимает линейное время, как указано выше.
ArrayList - это растущий массив. Это похоже на обычный массив. Под капотом, когда элемент добавляется по индексу i, он создает другой массив с размером, который на 1 больше, чем предыдущий размер (так в общем случае, когда n элементов должны быть добавлены в ArrayList, новый массив размера предыдущего размера плюс n создается). Затем элементы копируются из предыдущего массива в новый, и элементы, которые должны быть добавлены, также помещаются в указанные индексы.
