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

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

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

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

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

27.11.2008 01:36:35
Hawkeye Parker 12.10.2016 03:58:29
Просто посмотрите цитату автора LinkedList stackoverflow.com/a/42529652/2032701, и вы получите практическое понимание проблемы.
Ruslan 26.12.2017 19:17:59
30 ОТВЕТОВ
РЕШЕНИЕ

Резюме ArrayList с ArrayDequeпредпочтительнее во многих случаях использования, чем LinkedList. Если вы не уверены - просто начните с ArrayList.


LinkedListи ArrayListдве разные реализации интерфейса List. LinkedListреализует его с помощью двусвязного списка. ArrayListреализует его с помощью динамически изменяемого размера массива.

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

За LinkedList<E>

  • get(int index)равно O (n) ( в среднем n / 4 шагов)
  • add(E element)является O (1)
  • add(int index, E element)равно O (n) ( в среднем n / 4 шага), но O (1), когда index = 0 <--- основное преимуществоLinkedList<E>
  • remove(int index)равно O (n) ( в среднем n / 4 шагов)
  • Iterator.remove()является O (1) . <--- главное преимуществоLinkedList<E>
  • ListIterator.add(E element)это O (1) Это одно из основных преимуществLinkedList<E>

Примечание. Многие операции требуют в среднем n / 4 шагов, в лучшем случае постоянное количество шагов (например, index = 0) и n / 2 шагов в худшем случае (середина списка)

За ArrayList<E>

  • get(int index)это O (1) <--- Основное преимуществоArrayList<E>
  • add(E element)является O (1) амортизируется, но О (п) в худшем случае , так как массив должен быть изменен и скопирован
  • add(int index, E element)равно O (n) ( в среднем n / 2 шагов)
  • remove(int index)равно O (n) ( в среднем n / 2 шагов)
  • Iterator.remove()равно O (n) ( в среднем n / 2 шагов)
  • ListIterator.add(E element)равно O (n) ( в среднем n / 2 шагов)

Примечание. Многие операции требуют в среднем n / 2 шагов, постоянное количество шагов в лучшем случае (конец списка), n шагов в худшем случае (начало списка)

LinkedList<E>допускает вставки или удаления в постоянное время с использованием итераторов , но только последовательный доступ к элементам. Другими словами, вы можете перемещаться по списку вперед или назад, но нахождение позиции в списке занимает время, пропорциональное размеру списка. Javadoc говорит «операции, индекс в списке будет проходить по списку с начала или конца, в зависимости от того что ближе» , так что эти методы являются O (п) ( п / 4 стадии) в среднем, хотя O (1) для index = 0.

ArrayList<E>с другой стороны, разрешить быстрый произвольный доступ для чтения, так что вы можете получить любой элемент за постоянное время. Но добавление или удаление из любого места, кроме конца, требует сдвига всех последних элементов, чтобы сделать отверстие или заполнить пробел. Кроме того, если вы добавляете больше элементов, чем емкость базового массива, выделяется новый массив (в 1,5 раза больше размера), и старый массив копируется в новый, так что добавление в a ArrayListявляется O (n) в худшем случае. случай, но постоянный в среднем.

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

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

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

Кроме того, если у вас большие списки, имейте в виду, что использование памяти также отличается. Каждый элемент LinkedListимеет больше издержек, так как указатели на следующий и предыдущий элементы также сохраняются. ArrayListsне надо накладных расходов Однако ArrayListsзанимайте столько памяти, сколько выделено для емкости, независимо от того, были ли элементы фактически добавлены.

Начальная емкость по умолчанию ArrayListдовольно мала (10 из Java 1.4 - 1.8). Но поскольку базовая реализация представляет собой массив, размер массива должен быть изменен, если вы добавите много элементов. Чтобы избежать высокой стоимости изменения размера, когда вы знаете, что собираетесь добавить много элементов, создайте их ArrayListс более высокой начальной емкостью.

3351
17.12.2019 01:23:25
Забыл упомянуть стоимость вставки. В LinkedList, если у вас есть правильная позиция, вставка стоит O (1), тогда как в ArrayList она достигает O (n) - все элементы после точки вставки должны быть перемещены.
David Rodríguez - dribeas 27.11.2008 07:20:28
Что касается использования Vector: на самом деле нет необходимости возвращаться к Vector. Способ сделать это с вашей предпочтительной реализацией List и вызовом synchronizedList, чтобы получить синхронизированную оболочку. См .: java.sun.com/docs/books/tutorial/collections/implementations/…
Ryan Cox 27.11.2008 12:19:18
Нет, для LinkedList get по-прежнему равен O (n), даже если вы знаете позицию, потому что для того, чтобы добраться до этой позиции, базовая реализация должна пройтись по указателям «next» связанного списка, чтобы получить значение этой позиции. Не существует такого понятия, как произвольный доступ. Для позиции 2 ход указателей может быть дешевым, но для позиции 1 миллион не таким дешевым. Дело в том, что оно пропорционально позиции, что означает, что это O (n).
Jonathan Tran 11.03.2011 19:03:11
@Kevin Может быть, что память "близко друг к другу". Аппаратное обеспечение будет кэшировать непрерывные блоки памяти (динамическое ОЗУ) в более быстрое статическое ОЗУ в кеше L1 или L2. В теории и в большинстве случаев практически, память может рассматриваться как произвольный доступ. Но на самом деле чтение в памяти последовательно будет немного быстрее, чем в случайном порядке. Для цикла, критичного к производительности, это может иметь значение. Они называют это «пространственной местностью» или местностью ссылки .
Jonathan Tran 5.05.2011 20:25:10
Там нет такой вещи, как O(n/2)или O(n/4). Большая нотация O говорит вам, как операция масштабируется с большим n . и операция, требующая n/2этапов, масштабируется точно так же, как операция, требующая nэтапов, что является причиной удаления постоянных слагаемых или факторов. O(n/2)и O(n/4)оба справедливы O(n). LinkedListи в ArrayListлюбом случае иметь разные постоянные коэффициенты, так что не имеет смысла сравнивать O(n/2)одно с O(n/4)другим, оба просто обозначают операции линейного масштабирования.
Holger 4.07.2016 09:57:35

Это вопрос эффективности. LinkedListбыстр для добавления и удаления элементов, но медленный доступ к определенному элементу. ArrayListбыстро для доступа к определенному элементу, но может быть медленным, чтобы добавить к любому концу, и особенно медленно, чтобы удалить в середине.

Массив vs ArrayList vs LinkedList vs Vector более детален, как и Linked List .

64
20.04.2018 06:12:45

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

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

34
20.04.2018 06:14:16
LinkedList не дешев для добавления элементов. Почти всегда быстрее добавить миллион элементов в ArrayList, чем добавить их в LinkedList. И большинство списков в реальном коде не содержат даже миллиона элементов.
Porculus 10.09.2010 17:21:52
В любой момент вы знаете стоимость добавления элемента в свой LinkedList. ArrayList у вас нет (в общем). Добавление одного элемента в ArrayList, содержащий миллион элементов, может занять очень много времени - это операция O (n) плюс двойное хранилище, если только вы не распределили пространство. Добавление элемента в LinkedList - O (1). Мое последнее утверждение остается в силе.
Dustin 10.09.2010 23:03:04
Добавление одного элемента в ArrayList - это O (1), независимо от того, 1 миллион или 1 миллиард. Добавление элемента в LinkedList также является O (1). «Добавление» означает ДОБАВЛЕНИЕ В КОНЕЦ.
kachanov 13.05.2012 14:36:09
Должно быть, вы прочитали реализацию иначе, чем я. По моему опыту, копирование массива с 1 миллиардом элементов занимает больше времени, чем копирование массива с 1 миллиардом элементов.
Dustin 14.05.2012 05:57:35
@kachanov Вы должны неправильно понять Дастина. Если вы не объявили массив из 1 миллиарда элементов, вам в конечном итоге потребуется изменить размер массива, в этом случае вам нужно будет скопировать все элементы в новый больший массив, поэтому иногда вы получите O (N), однако со связанным списком вы всегда будете получить O (1)
Stan R. 18.03.2013 21:51:39

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

ArrayListбыстрее получить доступ к индексированному значению. Это гораздо хуже при вставке или удалении объектов.

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

9
20.04.2018 06:14:59
Чтобы узнать больше, не читайте, просто напишите код. и вы обнаружите, что реализация ArrayList быстрее, чем LinkedList при вставке и удалении.
kachanov 18.05.2012 02:53:36

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

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

14
20.04.2018 06:15:53

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

Почему LinkedListотстой:

  • Он использует множество небольших объектов памяти и, следовательно, влияет на производительность всего процесса.
  • Множество мелких объектов плохо влияют на локальность кэша.
  • Любая индексированная операция требует обхода, то есть имеет производительность O (n). Это неочевидно в исходном коде, что приводит к тому, что алгоритмы O (n) работают медленнее, чем при ArrayListиспользовании.
  • Получить хорошую производительность сложно.
  • Даже если производительность big-O такая же, как ArrayListона, она все равно будет значительно медленнее.
  • Это неприятно видеть LinkedListв источнике, потому что это, вероятно, неправильный выбор.
238
9.10.2017 13:27:37
Сожалею. отметил вас вниз LinkedList не сосет. Есть ситуации, когда LinkedList является правильным классом для использования. Я согласен, что не так много ситуаций, когда это лучше, чем arraylist, но они существуют. Обучайте людей, которые делают глупости!
David Turner 27.11.2008 17:50:43
Жаль видеть, что вы получили много отрицательных голосов за это. Существует действительно очень мало причин для использования Java LinkedList. В дополнение к плохой производительности он также использует намного больше памяти, чем другие конкретные классы List (каждый узел имеет два дополнительных указателя, и каждый узел является отдельным объектом-оберткой с дополнительными байтами служебной информации, которые идут вместе с ними).
Kevin Brock 23.03.2010 00:46:34
Это один из самых полезных ответов здесь. Обидно, что многие программисты не понимают (а) разницу между абстрактными типами данных и конкретными реализациями, и (б) реальную важность постоянных факторов и накладных расходов памяти при определении производительности.
Porculus 10.09.2010 17:25:59
-1: Это довольно тупое представление. Да, это правда, что ArrayList - очень универсальный инструмент. Однако у него есть свои ограничения. В некоторых случаях это может вызвать проблемы, и вам придется использовать LinkedList. Конечно, это очень специализированное решение, и, как и любой специализированный инструмент, в большинстве случаев оно превосходит универсальное. Но это не значит, что это «отстой» или что-то в этом роде, вы просто должны знать, когда его использовать.
Malcolm 8.08.2011 13:43:14
@DavidTurner: они существуют, но я думаю, что точка зрения Тома состояла в том, что если вам нужно спросить, вы, вероятно, захотите ArrayList.
user541686 18.01.2013 05:07:51

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

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

24
20.04.2018 06:16:46
Для небольших списков ArrayList.add (0) по-прежнему всегда будет работать быстрее, чем LinkedList.addFirst ().
Porculus 10.09.2010 17:20:32
@Porculus Я постоянно слышу этот аргумент о том, что для маленьких списков ArrayList.add (0) будет быстрее, насколько мал этот маленький? 10 элементов, 10 миллионов?
garg10may 20.09.2016 12:07:08
@ garg10may small меньше 10.
Jesse Wilson 21.09.2016 14:53:12
@Porculus small означает меньшую, чем максимальная емкость внутреннего массива, лежащего в основе ArrayList.
Janac Meena 3.03.2020 17:07:06

Да, я знаю, это древний вопрос, но я добавлю два моих цента:

LinkedList - почти всегда неправильный выбор с точки зрения производительности. Существует несколько очень специфических алгоритмов, для которых требуется LinkedList, но они очень, очень редки, и алгоритм обычно будет конкретно зависеть от способности LinkedList относительно быстро вставлять и удалять элементы в середине списка, как только вы перейдете туда с ListIterator.

Существует один общий случай использования, в котором LinkedList превосходит ArrayList: это очереди. Однако, если ваша цель - производительность, вместо LinkedList вы также должны рассмотреть возможность использования ArrayBlockingQueue (если вы можете заранее определить верхнюю границу размера очереди и можете позволить себе выделять всю память заранее) или эту реализацию CircularArrayList , (Да, это с 2001 года, поэтому вам нужно будет его обобщить, но я получил сопоставимые коэффициенты производительности с тем, что только что цитировалось в статье в недавней JVM)

107
19.05.2009 11:21:20
С Java 6 вы можете использовать ArrayDeque. docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html
Thomas Ahle 30.12.2011 15:01:32
ArrayDequeмедленнее, чем LinkedListесли все операции находятся на одном конце. Это нормально, когда используется в качестве стека, но это не делает хорошую очередь.
Jeremy List 30.04.2015 02:12:27
Неверно - по крайней мере, для реализации Oracle в jdk1.7.0_60 и в следующем тесте. Я создал тест, в котором я повторяю цикл 10 миллионов раз, и у меня есть Deque из 10 миллионов случайных целых чисел. Внутри цикла я опрашиваю один элемент и предлагаю постоянный элемент. На моем компьютере LinkedList более чем в 10 раз медленнее, чем ArrayDeque и использует меньше памяти). Причина в том, что в отличие от ArrayList, ArrayDeque хранит указатель на заголовок массива, чтобы при удалении заголовка не приходилось перемещать все элементы.
Henno Vermeulen 22.05.2015 10:18:58
ArrayDequeскорее всего будет быстрее, чем Stackпри использовании в качестве стека, и быстрее, чем LinkedListпри использовании в качестве очереди.
akhil_mittal 17.06.2015 15:44:47
Обратите внимание, что комментарий akhil_mittal является цитатой из ArrayDequeдокументации.
Stuart Marks 28.11.2015 22:47:55

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

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

7
23.05.2017 12:02:46
Как так? Это может быть верно для структур данных связанного списка, но не для объекта Java LinkList. Вы не можете просто указать nextодин список на первый узел во втором списке. Единственный способ - использовать addAll()последовательное добавление элементов, хотя это лучше, чем циклический просмотр и вызов add()каждого элемента. Чтобы сделать это быстро в O (1), вам понадобится класс композитинга (например, org.apache.commons.collections.collection.CompositeCollection), но тогда это будет работать для любого вида List / Collection.
Kevin Brock 23.03.2010 00:42:31
Да, верно. Я отредактировал ответ соответственно. но посмотрите этот ответ, чтобы узнать, «как» сделать это с LinkedList: stackoverflow.com/questions/2494031/…
Karussell 23.03.2010 12:47:46
Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

Алгоритмы: обозначение Big-Oh

ArrayLists хороши для записи один раз для чтения или добавления, но плохо подходят для добавления / удаления спереди или посередине.

128
28.07.2016 08:46:18
Вы не можете сравнивать значения Big-O напрямую, не думая о постоянных факторах. Для небольших списков (а большинство списков маленькие) O (N) ArrayList быстрее, чем O (1) LinkedList.
Porculus 10.09.2010 17:23:15
Меня не волнует производительность небольших списков, и мой компьютер тоже не заботится, если он не используется каким-либо образом в цикле.
Maarten Bodewes 18.08.2011 16:35:34
LinkedList не может вставлять посередине O(1). Он должен пройти через половину списка, чтобы найти точку вставки.
Thomas Ahle 30.12.2011 15:02:56
LinkedList: вставить в середину O (1) - НЕПРАВИЛЬНО! Я обнаружил, что даже вставка в 1/10-ю позицию размера LinkedList медленнее, чем вставка элемента в 1/10-ю позицию ArrayList. И еще хуже: конец коллекции. вставка в последние позиции (не самые последние) ArrayList быстрее, чем в последние позиции (не самые последние) LinkedList
kachanov 13.05.2012 14:29:12
@kachanov Вставка в a LinkedList , O(1) если у вас есть итератор для позиции вставки , т.е. ListIterator.addпредположительно O(1)для a LinkedList.
Has QUIT--Anony-Mousse 18.08.2013 08:13:07

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

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

8
20.04.2010 15:32:01

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

Точно так же вы можете получить лучшую пропускную способность в приложении из стандартного сборщика мусора с пропускной способностью по умолчанию, но как только вы получите Java-приложения с кучами 10 ГБ, вы можете заблокировать приложение на 25 секунд во время полного GC, что приводит к тайм-аутам и сбоям в приложениях SOA и дует ваши SLA, если это происходит слишком часто. Несмотря на то, что сборщик CMS потребляет больше ресурсов и не достигает той же исходной пропускной способности, это гораздо лучший выбор, поскольку он имеет более предсказуемую и меньшую задержку.

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

138
1.01.2011 20:23:52
Разве другое решение не будет управлять размером списка программно с помощью метода ArrayList sureCapacity ()? Мой вопрос: почему так много вещей хранится в куче хрупких структур данных, когда их лучше хранить в механизме кэширования или БД? На днях у меня было интервью, где они ругались вверх и вниз по поводу зла ArrayList, но я прихожу сюда и обнаруживаю, что анализ сложности намного лучше! БОЛЬШАЯ ТОЧКА ДЛЯ ОБСУЖДЕНИЯ, ХОТЯ. СПАСИБО!
ingyhere 30.10.2012 05:33:47
как только вы получаете Java - приложения с 10GB осыпает вы можете наматывать запирание приложения в течение 25 секунд , в течение полного ШСА , который вызывает таймаут На самом деле с LinkedList вы убиваете сборщик мусор во время полного ГКСА, он должен итерации чрезмерно большой LinkedList с кэш - промахом на каждый узел.
bestsss 17.12.2014 20:15:47
Это ... ужасное решение. вы в основном полагаетесь на то, что GC убирает за вас, что невероятно дорого, когда вместо этого вы можете просто вызвать sureCapacity () для массива ...
Philip Devine 19.06.2015 14:03:14
@Andreas: A LinkedList всегда выделяет в пять раз больше памяти, чем простой массив ссылок, поэтому ArrayListвременно требующий 2,5 раза по-прежнему потребляет гораздо меньше памяти, даже если память не освобождается. Поскольку выделение большого массива обходит пространство Eden, они не оказывают никакого влияния на поведение GC, если только на самом деле не хватает памяти, в этом случае LinkedListвзрыв произошел намного раньше…
Holger 5.07.2016 09:04:52
@Andreas Другая проблема заключается в том, как распределяется память. LinkedListнужен только небольшой кусок свободной памяти, чтобы выделить для следующего элемента. ArrayListпотребуется большой и непрерывный свободный блок пространства для выделения массива с измененным размером. Если куча фрагментируется, то GC может в конечном итоге переупорядочить всю кучу только для того, чтобы освободить подходящий отдельный блок памяти.
Piotr Kusmierczyk 1.11.2016 23:12:45
9
5.09.2011 06:33:52
Привет @chharvey, ссылка только ответы получить 6 Upvotes? Пожалуйста, добавьте несколько пунктов, которые могут поддержать ссылку. Что если oracle изменит свою ссылку?
user8898216 14.11.2017 06:08:22

Верно или неправильно: Пожалуйста, выполните тест на месте и решите сами!

Редактировать / Удалить быстрее, LinkedListчем ArrayList.

ArrayList, поддерживаемый Array, который должен быть вдвое больше, хуже в приложениях большого объема.

Ниже приведен результат модульного теста для каждой операции. Время указывается в наносекундах.


Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

Вот код:

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}
54
20.04.2018 06:23:23
ArrayList не нужно дублировать, если быть точным. Пожалуйста, проверьте источники в первую очередь.
Danubian Sailor 6.05.2013 14:40:49
Следует отметить, что ваш пример имеет недостатки ... Вы удаляете из строки: 18 + [2, 12] байтов ("true0false", "true500000false"), в среднем 25 байтов, которые являются размерами элементов в середине. Известно, что при увеличении размера байта элемента связанный список работает лучше, а при увеличении размера списка непрерывный массив (список) будет работать лучше. Самое главное, вы делаете .equals () для строк - это не дешевая операция. Если бы вы вместо этого использовали целые числа, я думаю, что будет разница.
Centril 21.08.2014 09:40:10
«... хуже в приложениях большого объема »: это недоразумение. LinkedListимеет намного больше памяти, потому что для каждого элемента есть объект узла с пятью полями. Во многих системах это занимает 20 байтов. Среднее количество служебной памяти на элемент для элемента ArrayListсоставляет полтора слова, что составляет 6 байтов, а в худшем - 8 байтов.
Lii 15.09.2015 09:53:40
Я сделал лучшую версию вашего эталонного теста здесь с результатами - производительность add-on-end для arraylist искусственно низка для вас, потому что addAll предоставляет массив хранения ТОЧНО начального размера, поэтому первая вставка всегда вызывает ArrayCopy. Кроме того, это включает в себя циклы прогрева, чтобы обеспечить компиляцию JIT перед сбором данных.
BobMcGee 10.03.2016 18:48:54
@BillK, начиная с Java 8, вы можете использовать removeIf(element -> condition)там, где он подходит, что может быть значительно быстрее по ArrayListсравнению с циклом и удалением с помощью итератора, поскольку не требуется сдвигать весь остаток для каждого отдельного элемента. Работает ли это лучше или хуже, чем LinkedListзависит от конкретного сценария, как LinkedListтеоретически O (1), но удаление только одного узла требует нескольких обращений к памяти, которые могут легко превысить число, необходимое для ArrayListудаления при значительном количестве элементов ,
Holger 14.05.2019 17:05:54

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

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

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

Что касается ArrayList, я согласен, что, по крайней мере, вы всегда должны использовать конструктор с начальной емкостью, чтобы минимизировать дублирование массивов в максимально возможной степени.

6
3.10.2011 23:23:00

До сих пор, похоже, никто не обращал внимания на объем памяти каждого из этих списков, кроме общего консенсуса о том, что a LinkedList«намного больше», чем a, ArrayListпоэтому я сделал некоторое сжатие чисел, чтобы продемонстрировать, насколько точно оба списка занимают N пустых ссылок.

Так как ссылки являются либо 32 или 64 бита (даже тогда , когда нулевые) от их относительных систем, я включил 4 набора данных для 32 и 64 бит LinkedListsи ArrayLists.

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

Примечание 2: (спасибо BeeOnRope) Так как CompressedOops теперь используется по умолчанию начиная с середины JDK6 и выше, приведенные ниже значения для 64-битных машин будут в основном соответствовать их 32-битным аналогам, если, конечно, вы специально не отключите его.


График LinkedList и ArrayList Количество элементов х байтов


Результат ясно показывает, что LinkedListэто намного больше ArrayList, особенно с очень большим количеством элементов. Если память является фактором, держитесь подальше LinkedLists.

Формулы, которые я использовал, следуют, дайте мне знать, если я сделал что-то не так, и я исправлю это. «b» - это 4 или 8 для 32- или 64-разрядных систем, а «n» - количество элементов. Обратите внимание, что причина для модов в том, что все объекты в java будут занимать кратное 8 байт пространство независимо от того, все они используются или нет.

ArrayList:

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

LinkedList:

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

627
11.12.2018 22:15:07
Довольно интересно видеть, что LinkedList требует столько же памяти, сколько и ArrayList для хранения одного элемента. Как не интуитивно понятно! Что произойдет, если вы запустите свой пример с -XX: + UseCompressedOops?
jontejj 17.04.2013 15:31:56
Проблема с вашей математикой в ​​том, что ваш график сильно преувеличивает влияние. Вы моделируете объекты, каждый из которых содержит только int4 или 8 байтов данных. В связанном списке есть, по сути, 4 «слова» накладных расходов. Таким образом, ваш график создает впечатление, что связанные списки используют «пять раз» хранилище списков массивов. Это не верно. Накладные расходы составляют 16 или 32 байта на объект, как аддитивная корректировка, а не коэффициент масштабирования.
Heath Hunnicutt 6.09.2013 00:18:13
Ни один из объектов ArrayList / LinkedList / Node не содержит только int, поэтому я не понимаю, что вы там говорите. Я перефразировал «накладные расходы объекта» на «заголовок объекта», чтобы уточнить - для каждого объекта существует 8-байтовый заголовок, независимо от системы, и да, он включает в себя все объекты Node в LinkedList, которые все подсчитываются правильно, насколько я могу рассказать. Кстати, при повторном рассмотрении я обнаружил пару других проблем с моей математикой в ​​LinkedList, что фактически ухудшает разделение и ArrayList . Я рад продолжать обновлять его, поэтому, пожалуйста, не стесняйтесь уточнять и уточнять дальше.
Numeron 17.10.2013 06:24:16
Следует отметить, что CompressedOopsтеперь это значение по умолчанию во всех последних JDK (7, 8 и обновления 6 в течение нескольких лет), поэтому 64-разрядная версия не будет иметь значения ArrayListили LinkedListразмеров, если вы явно не отключили сжатые параметры для некоторая причина.
BeeOnRope 7.11.2013 05:29:09
@jontejj увеличение емкости по умолчанию составляет 50%, поэтому при заполнении ArrayListбез указания начальной емкости оно все равно будет использовать значительно меньше памяти, чем a LinkedList.
Holger 29.08.2019 09:35:36

Когда я должен использовать LinkedList? При работе в основном со стеками или при работе с буферами. Когда я должен использовать ArrayList? Только при работе с индексами, в противном случае вы можете использовать HashTable со связанным списком, тогда вы получите:

Хеш-таблица + связанный список

  • Доступ по клавише O (1),
  • Вставьте ключом O (1),
  • Удалить ключом O (1)
  • и есть хитрость для реализации RemoveAll / SetAll с O (1) при использовании контроля версий

Это кажется хорошим решением, и в большинстве случаев это так, как вам следует знать: HashTable занимает много дискового пространства, поэтому, когда вам нужно управлять 1 000 000 списков элементов, это может стать вопросом, который имеет значение. Это может происходить в реализациях сервера, в клиентах это происходит редко.

Также взгляните на Red-Black-Tree

  • Журнал произвольного доступа (n),
  • Вставить журнал (n),
  • Удалить журнал (n)
-1
3.11.2016 12:05:44
Я хотел бы дать это больше чем один -1: LinkedList дает O (N) для всех операций вставки, удаления и произвольного доступа, потому что вы должны пройти по списку, чтобы сначала добраться до правильной точки. Также вас может удивить, что в хэш-таблице / таблице используются массивы изменения размеров, такие как ArrayList, и, учитывая, что наиболее распространенное использование списков - это просто индексирование по числу, использование одного из них над ArrayList - худшая идея.
Numeron 29.07.2013 06:40:10
@ Нумерон, ты прав, непонятно, что я ответил. На самом деле, когда вы пытаетесь получить доступ к связанному списку по индексу, это будет O (n), как бы я ни хотел вставлять в связанный список по элементам. Тогда это O (1), а также взаимодействует по всему списку, так же, как список массивов.
Ilya Gazman 3.10.2013 06:58:03

Вот запись 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)

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

18
20.04.2018 06:29:10
>>>> ArrayList add -> O (1) <- не правда. В некоторых случаях ArrayList придется увеличивать, чтобы добавить еще один элемент
kachanov 8.02.2013 00:54:05
Удаление LinkedList - это не O (1), ему нужно будет найти удаляемый элемент, поэтому наихудший O (n) и средний O (n / 2)
garg10may 20.09.2016 12:05:51
Ни один LinkedList.add(), хотя большинство ответов здесь говорят так.
user207421 9.10.2019 19:56:58

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

21
20.04.2018 06:29:50

ArrayListэто по сути массив. LinkedListреализован в виде двойного связанного списка.

Это getдовольно ясно. O (1) для ArrayList, потому что ArrayListразрешить произвольный доступ с помощью индекса. O (n) for LinkedList, потому что сначала нужно найти индекс. Примечание: есть разные версии addи remove.

LinkedListбыстрее в добавлении и удалении, но медленнее в получении. Вкратце, LinkedListследует отдавать предпочтение, если:

  1. нет большого количества произвольного доступа элемента
  2. существует большое количество операций добавления / удаления

=== ArrayList ===

  • добавить (E e)
    • добавить в конце ArrayList
    • требуют изменения размера памяти.
    • O (n) худший, O (1) амортизированный
  • добавить (int индекс, E элемент)
    • добавить к определенной позиции индекса
    • требуется сдвиг и возможная стоимость изменения размера памяти
    • На)
  • удалить (int index)
    • удалить указанный элемент
    • требуется сдвиг и возможная стоимость изменения размера памяти
    • На)
  • удалить (Объект o)
    • удалить первое вхождение указанного элемента из этого списка
    • нужно сначала поискать элемент, а затем сдвиг и возможные изменения размера памяти
    • На)

=== LinkedList ===

  • добавить (E e)

    • добавить в конец списка
    • O (1)
  • добавить (int индекс, E элемент)

    • вставить в указанное положение
    • сначала нужно найти позицию
    • На)
  • удалять()
    • удалить первый элемент списка
    • O (1)
  • удалить (int index)
    • удалить элемент с указанным индексом
    • сначала нужно найти элемент
    • На)
  • удалить (Объект o)
    • удалить первое вхождение указанного элемента
    • сначала нужно найти элемент
    • На)

Вот фигура из programcreek.com ( addи removeотносится к первому типу, т.е. добавьте элемент в конец списка и удалите элемент в указанной позиции в списке.):

введите описание изображения здесь

50
27.05.2018 10:29:49
Msgstr "LinkedList быстрее, чем добавить / удалить". Неправильно, проверьте ответ выше stackoverflow.com/a/7507740/638670
Nerrve 5.11.2013 10:00:00

Операция get (i) в ArrayList выполняется быстрее, чем LinkedList, потому что:
ArrayList: реализация массива изменяемого размера интерфейса List
LinkedList: реализация двусвязного списка интерфейсов List и Deque

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

5
9.11.2016 10:48:34

Оба метода remove () и insert () имеют эффективность времени выполнения O (n) для ArrayLists и LinkedLists. Однако причина времени линейной обработки обусловлена ​​двумя очень разными причинами:

В ArrayList вы получаете доступ к элементу в O (1), но на самом деле удаление или вставка чего-либо делает его O (n), потому что все следующие элементы должны быть изменены.

В LinkedList для достижения необходимого элемента требуется O (n), потому что мы должны начинать с самого начала, пока не достигнем желаемого индекса. На самом деле удаление или вставка является константой, потому что нам нужно изменить только 1 ссылку для remove () и 2 ссылки для insert ().

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

Бонус: хотя нет никакого способа сделать эти два метода O (1) для ArrayList, на самом деле есть способ сделать это в LinkedLists. Допустим, мы хотим пройтись по всему списку, удаляя и вставляя элементы на нашем пути. Обычно вы начинаете с самого начала для каждого элемента, используя LinkedList, мы также можем «сохранить» текущий элемент, над которым мы работаем, с помощью итератора. С помощью Итератора мы получаем эффективность O (1) для remove () и insert () при работе в LinkedList. Делая это единственным преимуществом в производительности, я знаю, что LinkedList всегда лучше, чем ArrayList.

2
24.07.2018 16:14:23

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

ArrayList против LinkedList

1) Search: ArrayListоперация поиска довольно быстрая по сравнению с LinkedListоперацией поиска. get(int index)в ArrayListдает производительность, O(1)а LinkedListпроизводительность есть O(n).

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

2) Deletion: LinkedListоперация удаления дает O(1)производительность, а ArrayListдает переменную производительность: O(n)в худшем случае (при удалении первого элемента) и O(1)в лучшем случае (при удалении последнего элемента).

Вывод: удаление элемента LinkedList происходит быстрее по сравнению с ArrayList.

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

3) Inserts Performance: LinkedListметод add дает O(1)производительность, а в худшем - ArrayListдает O(n). Причина та же, что и для удаления.

4) Memory Overhead: ArrayListподдерживает индексы и данные элемента, в то же время LinkedListподдерживает данные элемента и два указателя для соседних узлов

следовательно, потребление памяти в LinkedList относительно высокое.

Между этими классами есть несколько общих черт:

  • И ArrayList, и LinkedList являются реализацией интерфейса List.
  • Они оба поддерживают порядок вставки элементов, что означает, что при отображении элементов ArrayList и LinkedList набор результатов будет иметь тот же порядок, в котором элементы были вставлены в список.
  • Оба эти класса не синхронизированы и могут быть явно синхронизированы с помощью метода Collections.synchronizedList.
  • Эти iteratorи listIteratorклассы возвращаются и возвращаются fail-fast(если список структурно изменяется в любое время после создания итератора, любым способом, кроме использования iterator’sсобственных методов удаления или добавления, итератор будет throwa ConcurrentModificationException).

Когда использовать LinkedList, а когда использовать ArrayList?

  • Как объяснено выше, операции вставки и удаления дают хорошую производительность (O(1))по LinkedListсравнению с ArrayList(O(n)).

    Следовательно, если есть требование частого добавления и удаления в приложении, тогда LinkedList является лучшим выбором.

  • get methodОперации поиска ( ) выполняются быстро, Arraylist (O(1))но не вLinkedList (O(n))

    так что если будет меньше операций добавления и удаления и больше требований к поисковым операциям, ArrayList будет вашим лучшим выбором.

5
2.11.2016 09:00:23

Давайте сравним LinkedList и ArrayList с параметрами ниже:

1. Реализация

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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


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

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

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


5. Объем памяти

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

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


Источник

17
24.07.2018 15:49:31

Джошуа Блох, автор LinkedList:

Кто-нибудь на самом деле использует LinkedList? Я написал это, и я никогда не использую это.

Ссылка: https://twitter.com/joshbloch/status/583813919019573248

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

47
25.04.2017 10:23:06

ArrayList и LinkedList имеют свои плюсы и минусы.

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

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

Если у вас есть частые операции поиска в вашем приложении, используйте ArrayList. Если вы часто вставляете и удаляете, используйте LinkedList.

6
21.10.2017 01:58:43

ArrayList расширяет AbstractList и реализует интерфейс List. ArrayList - это динамический массив.
Можно сказать, что он был в основном создан для преодоления недостатков массивов.

Класс LinkedList расширяет AbstractSequentialList и реализует интерфейсы List, Deque и Queue.
Производительность
arraylist.get()- O (1), тогда linkedlist.get()как O (n)
arraylist.add()- O (1), linkedlist.add()0 (1)
arraylist.contains()- O (n), linkedlist.contains()O (n)
arraylist.next()- O (1) и linkedlist.next()O (1)
arraylist.remove()- O (n) в то время как linkedlist.remove()O (1)
В Arraylist
iterator.remove()является O (n),
тогда как В в связном списке
iterator.remove()O (1)

1
20.02.2018 21:51:19

1) Базовая структура данных

Первое различие между ArrayList и LinkedList связано с тем, что ArrayList поддерживается Array, а LinkedList поддерживается LinkedList. Это приведет к дальнейшим различиям в производительности.

2) LinkedList реализует Deque

Еще одно различие между ArrayList и LinkedList состоит в том, что помимо интерфейса List, LinkedList также реализует интерфейс Deque, который обеспечивает операции first-first-out для add () и poll () и некоторых других функций Deque. 3) Добавление элементов в ArrayList Добавление элемента в ArrayList - это операция O (1), если она не вызывает изменение размера массива, в этом случае он становится O (log (n)), с другой стороны, добавление элемента в LinkedList - это операция O (1), так как она не требует навигации.

4) Удаление элемента из позиции

Чтобы удалить элемент из определенного индекса, например, вызвав remove (index), ArrayList выполняет операцию копирования, которая приближает его к O (n), в то время как LinkedList необходимо перейти к этой точке, что также делает его O (n / 2) , так как он может перемещаться в любом направлении на основе близости.

5) Итерации по ArrayList или LinkedList

Итерация - это операция O (n) для LinkedList и ArrayList, где n - это номер элемента.

6) Извлечение элемента из позиции

Операция get (index) - это O (1) в ArrayList, а O (n / 2) в LinkedList, так как она должна проходить до этой записи. Хотя в обозначении Big O O (n / 2) - это просто O (n), потому что мы игнорируем константы.

7) Память

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

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

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

Из всех вышеупомянутых различий между ArrayList и LinkedList, похоже, ArrayList - лучший выбор, чем LinkedList, почти во всех случаях, кроме случаев, когда вы выполняете частую операцию add (), а не remove () или get ().

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

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

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

5
24.07.2018 16:01:05
Я думаю, что это лучший заявленный ответ всей группы здесь. Это точно и информативно. Я бы предложил изменить последнюю строку - в конце добавить «помимо очередей», которые являются очень важными структурами, которые действительно не имеют смысла для связанного списка вообще.
Bill K 28.12.2018 18:33:04

Один из тестов, которые я видел здесь, проводит тест только один раз. Но что я заметил, так это то, что вам нужно запускать эти тесты много раз, и в итоге их время будет сходиться. По сути, JVM необходимо разогреть. Для моего конкретного случая использования мне нужно было добавить / удалить элементы в список, который увеличивается примерно до 500 элементов. В моих тестах LinkedListполучилось быстрее: LinkedListоколо 50 000 н.с. и ArrayListоколо 90 000 н.с. Смотрите код ниже.

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}
3
3.03.2020 18:11:00

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


В теории LinkedList имеет O (1) для add(E element)

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

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

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

введите описание изображения здесь

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

введите описание изображения здесь

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

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

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

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

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

Ключевым элементом для запоминания является то, что стоимость выборки блока памяти, является более значительной, чем стоимость доступа к одной ячейке памяти. Вот почему считыватель 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 . Еще больше данных можно найти в его блоге

26
19.10.2018 03:06:19
Я бы не назвал очередь уникальной или экстремальной! Очередь fifo гораздо проще реализовать в LinkedList вместо ArrayList. Это на самом деле кошмар для ArrayList, так как вы должны отслеживать свой собственный запуск, остановку и перераспределение, вы также можете использовать массив, но Linked List - это fifo. Я не уверен насчет реализации Java, но LinkedList может выполнять O (1) для операций как очереди, так и удаления очереди (Требуется специальный указатель на элемент tail для удаления, который, как я предполагаю, есть в Java, но я не проверял дважды .)
Bill K 28.12.2018 18:26:46