Когда использовать LinkedList поверх ArrayList в Java?

Question

Я всегда был одним, чтобы просто использовать:

List<String> names = new ArrayList<>();

Я использую интерфейс в качестве имени типа для переносимость , поэтому, когда я задаю такие вопросы, я могу переделать свой код.

Когда следует использовать LinkedList вместо ArrayList и наоборот?

Answer 1

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

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

Answer 2

Если в вашем коде есть add(0) и remove(0), используйте LinkedList, и он красивее addFirst() и removeFirst(). В противном случае используйте ArrayList.

И, конечно же, Гуава s ImmutableList - ваш лучший друг.

Answer 3

Я знаю, что это старый пост, но, честно говоря, не могу поверить, что никто не упомянул, что LinkedList реализует Deque. Просто посмотрите на методы в Deque (и Queue); если вы хотите честное сравнение, попробуйте запустить LinkedList против ArrayDeque и выполнить сравнение по функциям.

Answer 4

Здесь обозначение Big-O в ArrayList и LinkedList, а также CopyOnWrite-ArrayList:

ArrayList

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

LinkedList

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite-ArrayList

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

Исходя из этого, вы должны решить, что выбрать. :)

Answer 5

Давайте сравним LinkedList и ArrayList w.r.t. ниже параметров:

1. Осуществление

ArrayList - реализация массива интерфейса списка с изменяемым размером, тогда как

LinkedList - реализация списка с двойными связями интерфейса списка.

---

2. Производительность

• get (int index) или операция поиска

  ArrayList Операция get (int index) выполняется в постоянное время, т.е. O (1), в то время как

  LinkedList Время выполнения операции get (int index) равно O (n).

  Причина, по которой ArrayList быстрее, чем LinkedList, заключается в том, что ArrayList использует систему на основе индекса для своих элементов, поскольку он внутренне использует структуру данных массива, с другой стороны,

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

• операция вставки () или добавления (объекта)

  Вставки в LinkedList обычно бывают быстрыми по сравнению с ArrayList. В LinkedList добавление или вставка является операцией O (1).

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

• операция удаления (int)

  Операция удаления в LinkedList обычно аналогична ArrayList, т. Е. O (n).

  В LinkedList есть два перегруженных метода удаления. один - удалить () без какого-либо параметра, который удаляет заголовок списка и работает в постоянном времени O (1). Другим перегруженным методом удаления в LinkedList является метод remove (int) или remove (Object), который удаляет Object или int, переданные в качестве параметра. Этот метод пересекает LinkedList до тех пор, пока не найдет объект и не отсоединит его от исходного списка. Следовательно, время выполнения этого метода O (n).

  В то время как в метод ArrayList remove (int) включает копирование элементов из старого массива в новый обновленный массив, следовательно, его время выполнения равно O (n).

---

3. Обратный итератор

LinkedList можно повторять в обратном направлении, используя downndingIterator (), тогда как

В ArrayList нет убывающего элемента () *, поэтому нам нужно написать собственный код для перебора ArrayList в обратном направлении.

---

4. Начальная емкость

Если конструктор не перегружен, то ArrayList создает пустой список начальной емкости 10, тогда как

LinkedList создает только пустой список без какой-либо начальной емкости.

---

5. Затраты памяти

Переполнение памяти в LinkedList больше по сравнению с ArrayList, поскольку узлу в LinkedList необходимо поддерживать адреса следующего и предыдущего узла. Пока

В ArrayList каждый индекс содержит только фактический объект (данные).

---

Источник

Answer 6

TL; DR из-за современной компьютерной архитектуры ArrayList будет значительно более эффективным практически для любого возможного варианта использования - и поэтому следует избегать LinkedList, за исключением некоторых очень уникальных и экстремальных случаев.

---

Теоретически, LinkedList имеет O (1) для add(E element)

Добавление элемента в середине списка также должно быть очень эффективным.

Практика сильно отличается, так как LinkedList представляет собой Cache Hostile Структура данных. От производительности POV - очень мало случаев, когда LinkedList мог бы быть лучше, чем Cache-friendly ArrayList.

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

Работа на оборудовании более позднего поколения (большие, более эффективные кэши) - результаты еще более убедительны:

LinkedList занимает гораздо больше времени для выполнения той же работы. source Исходный код

Для этого есть две основные причины:

1. В основном - что узлы LinkedList случайно разбросаны по памяти. ОЗУ («Память с произвольным доступом») на самом деле не является случайным, и блоки памяти должны быть извлечены для кэширования. Эта операция занимает много времени, и когда такие выборки происходят часто - страницы памяти в кеше необходимо постоянно заменять -> Cache misses -> Cache неэффективен. ArrayList элементов хранятся в непрерывной памяти - именно для этого оптимизируется современная архитектура ЦП.

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

DynamicIntArray , кстати, является пользовательской реализацией ArrayList, содержащей Int (примитивный тип), а не объекты - следовательно, все данные действительно хранятся смежно - следовательно, даже более эффективно.

Ключевым элементом, который следует помнить, является то, что стоимость выборки блока памяти более значительна, чем стоимость доступа к одной ячейке памяти. Вот почему считыватель последовательной памяти объемом 1 МБ работает в х400 раз быстрее, чем считывает этот объем данных из разных блоков памяти:

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

Источник: Числа задержки, которые должен знать каждый программист

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

Примечание: это тест C ++ Std lib, но мой предыдущий опыт показал, что результаты C ++ и Java очень похожи. Исходный код

Копирование последовательного объема памяти - это операция, оптимизированная современными ЦП - изменяющая теория и фактически делающая, опять же, ArrayList / Vector намного более эффективной

---

Кредиты: Все опубликованные тесты созданы Kjell Hedström . Еще больше данных можно найти в его блоге

Answer 7

В дополнение к другим хорошим аргументам, приведенным выше, вы должны заметить, что ArrayList реализует RandomAccess интерфейс, тогда как LinkedList реализует Queue.

Таким образом, они как-то решают несколько иные проблемы, с разницей в эффективности и поведении (см. Их список методов).

Answer 8

См. Учебные руководства по Java - Список реализаций .

Answer 9

Список массивов - это, по сути, массив с методами для добавления элементов и т. Д. (Вместо этого следует использовать общий список). Это набор элементов, к которым можно получить доступ через индексатор (например, [0]). Это предполагает переход от одного предмета к другому.

Связанный список определяет переход от одного элемента к другому (Элемент a -> элемент b). Вы можете получить тот же эффект со списком массивов, но связанный список абсолютно говорит, какой элемент должен следовать за предыдущим.

Answer 10

Важной особенностью связанного списка (который я не читал в другом ответе) является объединение двух списков. Для массива это O (n) (+ накладные расходы на некоторые перераспределения), для связанного списка это только O (1) или O (2); -)

Важно : для Java это LinkedList это не так! См. Существует ли быстрый метод concat для связанного списка в Java?