Отличие ArrayList от LinkedList?

В чем отличие LinkedList от ArrayList? И в каких случаях на практике удобней использовать LinkedList?
    

Ответы

Ответ 1

ArrayList - это список на основе массива. 
LinkedList - связанный список на основе элементов и связи между ними.
В качестве LinkedList лучше всего подходит представление вагонов поезда сцепленных последовательно. 

ArrayList следует использовать, когда в приоритете доступ по индексу, так как эт
операции выполняются за константное время. Добавление в конец списка в среднем тож
выполняется за константное время. Кроме того в ArrayList нет дополнительных расходов на хранение связки между элементами. Минусы в скорости вставки/удаления элементов находящихся не в конце списка, так как при этой операции все элементы правее добавляемого/удаляемого сдвигаются. 

LinkedList удобен когда важнее быстродействие операций вставки/удаления, которы
в LinkedList выполняются за константное время. Операции доступа по индексу производятся перебором с начала или конца (смотря что ближе) до нужного элемента. Дополнительные затраты на хранение связки между элементами.

Одним словом - если часто вставляете/удаляете - выбирайте в пользу LinkedList, 
противном случае ArrayList


Ответ 2

ArrayList основан на обычном массиве. Данная коллекция динамически увеличивает разме
массива, если в нем не хватает места, при вызове методов add(T element), addAll(Collection other) Так же она может его уменьшать, если размер больше количества хранимых элементов, методом trimToSize()

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

Чтобы оценить эти структуры данных, можно прибегнуть к ассимптотической сложности выполнения операций:

                          |  ArrayList  |  LinkedList 
 add (в начало)           |     O(n)    |   O(1)
 add (в середину)         |     O(n)    |   O(n)
 add (в конец списка)     |     O(n)    |   O(1)   


В LinkedList вставка осуществляется так: находится элемент, за которым должен следовать вставляемый элемент, изменяются ссылки в нем и следующим за ним.

В ArrayList создается новый массив, если в текущем нет места. Те элементы которы
находятся до вставляемого, остаются на месте, или копируются в новый. Далее добавляется вставляемый элемент. Затем копируются оставщиеся элементы, которые были в исходном.

get (первый элемент)        |   O(1)    |   O(1)
get (из середины)           |   O(1)    |   O(n)
get (последний элемент)     |   O(1)    |   O(1)


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

delete (первый элемент)     |   O(n)    |   O(1)
delete (из середины)        |   O(n)    |   O(n)
delete (последний элемент)  |   O(1)    |   O(1)


В LinkedList удаление происходит аналогично вставке.
В ArrayList, примерно, так же как и при добавлении.

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

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

Код демонстрирующий разницу в производительности:

@Fork(1)
@Warmup(iterations = 10)
@Measurement(iterations = 10)
@BenchmarkMode(Mode.AverageTime)
@Threads(1)
@State(Scope.Benchmark)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class PerformanceTest {
   private static List