ArrayList vs LinkedList

Довольно часто встречающийся вопрос на собеседовании на Java программиста. Может быть задан в разных формах:

1) В чем отличие ArrayList от LinkedList?

2) Что лучше использовать ArrayList или LinkedList?

3) Какая временная сложность добавления (в начало, в конец и в середину списка), удаления (из начала, из конца и из середины списка)  и поиска элементов в ArrayList и LinkedList?

Вначале давайте разберемся в чем их отличия.

ArrayList - это реализация интерфейса List с изменяемым размером массива. Т.е. под капотом это просто массив. Его начальный размер определяется параметром initialCapacity, который можно передать в качестве аргумента конструктора: List list = new ArrayList(initialCapacity). Если initialCapacity не указывать, то изначальный размер будет всего 10 элементов. Если мы продолжим добавлять элементы в массив и его размера не будет хватать, то будет создан новый массив, большего размера, и элементы из первого будут скопированные во второй массив. Такая же ситуация будет с добавление и удалением элемента из середины массива. Нам нужно в таком случае переместить весь хвост массива. Т.е. ArrayList не эффективен, если нам нужно часто манипулировать с элементами в начале или середине списка. Более того, в некоторых случаях даже добавление в конец списка может быть долгим (когда нужно увеличить размер массива). Когда же ArrayList полезен? Основное его преимущество это то, что получить элемент по индексу это O(1) операция как и в любом массиве. Т.е. если мы в основном добавляем в конец списка и нам более важно иметь быстрый доступ по индексу элемента - то ArrayList лучше. Еще одно преимущество ArrayList это то, что на один элемент массива он требует меньше памяти по сравнению с LinkedList (который хранит еще указатели на следующий и предыдущий элементы).

Кратко, суммирую временные сложности разных операций с ArrayList:

1) Получить элемент по индексу, get(int index) - O(1). Основное преимущество ArrayList.

2) Добавить в конец списка, add(E element) - O(1). В худшем случае O(n). Т.к. нужно увеличить размер массива и скопировать все элементы в новый массив.

3) Добавить по индексу (например, в середину или начало), add(int index, E element) - O(n). В этом случае требуется перемещение хвоста массива.

4) Удаление по индексу, remove(int index) - O(n). В этом случае требуется перемещение хвоста массива.

5) Удаление при помощи итератора, Iterator.remove() - O(n). В этом случае требуется перемещение хвоста массива.

6) Добавление при помощи итератора, ListIterator.add(E element) - O(n).

Давайте теперь рассмотрим LinkedList. Это реализация List и Deque при помощи двусвязного списка. Операции по добавлению и удалению элементов в начало и в конец очень быстрые  - O(1). Поиск по индексу медленный - O(n), т.к. требуется итерироваться от начала списка пока мы не найдем нужный по счету элемент списка. Для ArrayList эта операция O(1). Если же мы имеем доступ к итератору, то добавление или удаление при помощи итератора O(1). Т.к. не нужно копировать хвост массива как в ArrayList. В силу того, что LinkedList реализует интерфейс Deque его можно использоваться как очередь, стек и двустороннюю очередь. В нем есть специальные быстрые методы для добавления и удаления элементов из начала и из конца списка: getFirst(), getLast(), removeFirst(), removeLast(), addFirst(), addLast() и т.д. Но при этом LinkedList требует больше памяти для хранения каждого элемента списка, т.к. он хранит еще указатели на следующий и предыдущий элемент списка. Добавление и удаление из середины списка также медленные - O(n). Но по другой причине, чем в ArrayList (в ArrayList это было из-за перемещения хвоста массива). Чтобы удалить или добавить элемент по индексу в LinkedList нам нужно доитерироваться до нужного элемента, а это линейная операция.

Кратко, суммирую временные сложности разных операций с LinkedList:

1) Получить элемент по индексу, get(int index) - O(n). Т.к. нужно доитерироваться до этого элемента последовательно от начала списка. Но для доступа к началу или концу списка - O(1). В том, числе для методов getFirst(), getLast().

2) Добавить по индексу, add(int index, E element) - O(n). Т.к. нужно доитерироваться до этого элемента последовательно от начала списка. Но для для добавление в начало и конец - O(1). В том, числе для методов addFirst(), addLast().

4) Удаление по индексу, remove(int index) - O(n). Т.к. нужно доитерироваться до этого элемента последовательно от начала списка. Но для для удаления из начала и конца списка - O(1). В том, числе для методов removeFirst(), removeLast().

5) Удаление при помощи итератора, Iterator.remove() - O(1). Одно из преимуществ LinkedList.

6) Добавление при помощи итератора, ListIterator.add(E element) - O(1). Одно из преимуществ LinkedList.

Кратко суммирую:

ArrayList хорош для доступа по индексу (get(int index) - O(1), в LinkedList  это O(n)). Также он требует меньше памяти на один элемент списка.

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