38

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

3 ответа 3

53

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

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

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

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

2
  • 1
    "в ArrayList нет дополнительных расходов на хранение связки между элементами", но в нём выделяется память для дополнительных элементов. И всегда поддерживается массив с большим размером, чем количество элементов в контейнере. Однако при объёмах памяти на устройствах это не критично, как и не критична память расходуемая в LinkedList-е
    – s_klepcha
    19 сен 2016 в 19:13
  • 2
    @s_klepcha верно, выделяется. Но во-первых trimToSize() примененный в нужном месте нивелирует эту проблему, а во-вторых каждый элемент LinkedList'а содержит ссылку на текущий объект + 2 соседних и от этих затрат уже никуда не деться. И сколько бы не было доступно памяти при определенных задачах и её может не хватить, а если даже и хватает, то ни к чему использовать более необходимого.
    – GreyGoblin
    19 сен 2016 в 19:28
37

ArrayList основан на обычном массиве. Данная коллекция динамически увеличивает размер массива, если в нем не хватает места, при вызове методов add(T element), addAll(Collection<T> 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<Object> arrayList;
   private static List<Object> linkedList;

   private static final int count = 100_000;

   public static void main(String[] args) throws Exception {
    Main.main(args);
   }

   @Setup
   public static void setup() {
      arrayList = new ArrayList<>(count);
      linkedList = new LinkedList<>();

      for (int i = 0; i < count; i++)
         arrayList.add(new Object());

      linkedList.addAll(arrayList);
   }

   @Benchmark
   public void removeFromLinkedList(Blackhole blackhole) throws Exception {
      Object object = new Object();
      linkedList.remove(count / 2);
      linkedList.add(count / 2, object);
   }

   @Benchmark
   public void removeFromArrayList(Blackhole blackhole) throws Exception {
      Object object = new Object();
      arrayList.remove(count / 2);
      arrayList.add(count / 2, object);
   }
} 

На моем компьютере получилось следующее:

Benchmark                             Mode  Cnt  Score    Error  Units
PerformanceTest.removeFromArrayList   avgt   10  0.011 ±  0.001  ms/op
PerformanceTest.removeFromLinkedList  avgt   10  0.148 ±  0.001  ms/op

Из результатов видно, что LinkedList в 14 раз медленнее.

2
  • Сложность добавления в ArrayList в конец списка должна быть по идее логарифмическая, а не линейная. Ведь в общем случае список масштабируется в два раза при достижении границ внутреннего массива.
    – GreyGoblin
    6 фев 2017 в 11:22
  • @GreyGoblin это уже детали реализации 6 фев 2017 в 11:40
12

При выборе ArrayList в качестве имплементации списка следует понимать что операция добавления элементов может вызвать необходимость увеличения размера массива, что приведет к операции копирования всех элементов из одного массива в другой. В связи с этим следует обращать внимание на первоначальную вместимость, которая может быть указана в конструкторе при создании списка public ArrayList(int initialCapacity).

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

Понимать чем отличаются различные типы коллекций действительно важно, но на практике для большинства прикладных задач, где речь идет о десятках и сотнях элементов, выбор конкретной имплементации коллекции не играет большой роли как в отношении производительности так и в отношении используемой памяти. Гораздо болле важным моментом является выбор интерфейса коллекции которую вы собираетесь использовать:

  • java.util.Collection
  • java.util.List
  • java.util.Set

Выбор интерфейса будет влиять непосредственно на логику работы вашего кода. Интерфейсы также лучше использовать в качестве параметров и возвращаемых типов публичных методов.

1
  • 1
    Если создавать instance LinkedList то можно приводить не к интерфейсу List а к Dequeue, при этом изменяются доступные методы.
    – Arch
    20 сен 2016 в 7:00

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.