Питання Коли використовувати LinkedList за ArrayList?


Я завжди був одним, щоб просто використовувати:

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

Я використовую інтерфейс як ім'я типу для переносимість, тому, коли я задаю такі питання, як ці, я можу змінити свій код.

Коли треба LinkedList бути використаний ArrayList і навпаки?


2568
2017-11-27 01:36


походження


Дивись також: Масив проти пов'язаних списків - Hawkeye Parker
Просто див. Цитату з автора LinkedList stackoverflow.com/a/42529652/2032701 і ви отримаєте практичний сенс проблеми. - Ruslan


Відповіді:


Резюме  ArrayList з ArrayDeque є кращими в багато чого більше випадків використання, ніж LinkedList. Не впевнений - просто почати з ArrayList.


LinkedList і ArrayList це дві різні реалізації інтерфейсу List. LinkedList реалізує його за допомогою подвійного списку. ArrayList реалізує його за допомогою динамічно змінюваного масиву.

Як і у випадку зі стандартним пов'язаним списком і операціями масиву, різні методи матимуть різні алгоритмічні режими роботи.

Для LinkedList<E>

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

Примітка. Багато операцій потрібно н / 4 кроки в середньому постійна кількість кроків у кращому випадку (наприклад, index = 0), і н / 2 кроки в гіршому випадку (середня частина списку)

Для ArrayList<E>

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

Примітка. Багато операцій потрібно н / 2 кроки в середньому постійна кількість кроків у кращому випадку (кінець списку), н кроки в гіршому випадку (початок списку)

LinkedList<E> дозволяє вставляти або видаляти незмінно часу використовуючи ітератори, але лише послідовний доступ елементів. Іншими словами, ви можете піти в список вперед або назад, але пошук позиції у списку займає час, пропорційний розміру списку. Джавадоч каже "операції, що входять до списку, переміщатимуться з початку або кінця, залежно від того, який з них ближче", так що ці методи є O (n) (н / 4 кроки) в середньому, однак O (1) за index = 0.

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

Отже, залежно від операцій, які ви маєте намір зробити, ви повинні вибрати відповідні реалізації. Ітерація над тими чи іншими списками практично однаково дешева. (Ітерація над ArrayList технічно швидше, але якщо ви не робите щось дійсно чутливо до дії, вам не слід турбуватися про це - вони одночасно є постійними.)

Основні переваги використання a LinkedList виникатиме при повторному використанні існуючих ітераторів для вставки та видалення елементів. Потім ці операції можна виконати в O (1) змінюючи цей список лише локально. У списку масивів решту масиву повинно бути переїхав (тобто скопійовано). З іншого боку, шукаючи в a LinkedList означає наступні посилання в O (n) (н / 2 кроки) для найгіршого випадку, тоді як в ArrayList бажана позиція може бути математично обчислена і доступна в O (1).

Інша перевага використання a LinkedList виникає при додаванні або видаленні з голови списку, оскільки ці операції є O (1), поки вони є O (n) за ArrayList. Зауважте, що ArrayDeque може бути гарною альтернативою LinkedList для додавання і видалення з голови, але це не а List.

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

Початкова потужність за замовчуванням ArrayList досить маленький (10 з Java 1.4 - 1.8). Але оскільки основна реалізація є масивом, масив повинен змінюватися, якщо ви додаєте багато елементів. Щоб уникнути високої вартості зміни розміру, коли ви знаєте, що збираєтеся додати багато елементів, створіть ArrayList з вищою вихідною потужністю.


2847
2017-10-06 06:46



Забули згадати витрати на введення. У LinkedList, коли ви маєте правильне положення, витрати на вставку O (1), а в ArrayList - до O (n) - всі елементи, що перетинають точку вставки, повинні бути перенесені. - David Rodríguez - dribeas
Щодо використання Векторів: справді немає потреби повернутися до Вектор. Спосіб це зробити з вашою пріоритетною реалізацією списку та викликом для синхронізованого списку, щоб дати йому синхронізовану обгортку. Побачити: java.sun.com/docs/books/tutorial/collections/implementations/... - Ryan Cox
Ні, для LinkedList, отримати, як і раніше, є O (n), навіть якщо ви знаєте цю позицію, тому що для того, щоб досягти цієї позиції, основна реалізація повинна піти за посиланням "наступного" покажчика пов'язаного списку, щоб досягти значення цієї позиції. Немає такого поняття як випадковий доступ. Для позиції 2, прогулянка покажчиків може бути дешевою, але для позиції 1 млн., Не так вже й дешево. Справа в тому, що вона пропорційна позиції, що означає, що це O (n). - Jonathan Tran
@Kevin Можливо, важливо, що пам'ять "близька". Апаратне забезпечення буде кешувати сусідні блоки пам'яті (динамічна ОЗУ) у більш швидку статичну ОЗУ в кеші L1 або L2. У теорії та більшості випадків практично пам'ять можна розглядати як випадковий доступ. Але насправді, читання через пам'ять послідовно буде трохи швидше, ніж у довільному порядку. Для критичного циклу продуктивності це може мати значення. Вони називають це "просторовою місцевістю" або місцеположення довідки. - Jonathan Tran
Такого немає такого O(n/2) або O(n/4). Велика позначка O розповідає вам, як операція ваги з більшим н. і потрібна операція n/2 кроки точно подібно до операції, що потребує n кроки, що є причиною, через яку постійні суми або чинники видаляються. O(n/2) і O(n/4) обидва справедливі O(n). LinkedList і ArrayList у будь-якому випадку мають різні постійні фактори, тому не буде суттєво порівняти a O(n/2) одного з а O(n/4) з іншого, обидва лише позначають операції лінійного масштабування. - Holger


На жаль, ніхто, схоже, не звернув уваги на пам'ять кожного з цих списків, окрім загального консенсусу, що a LinkedList це "набагато більше", ніж а ArrayList таким чином я зробив деяке число crunching щоб продемонструвати точно скільки обидва списки займають для N нульових посилань.

Оскільки посилання на них - 32 або 64 біта (навіть при нульовій) їх відносних систем, я включив 4 набори даних для 32 і 64 бітових LinkedLists і ArrayLists.

Примітка: Розміри, показані для ArrayList лінії для обрізані списки - На практиці, ємність основного масиву в a ArrayList зазвичай більший, ніж його поточний елемент.

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


Graph of LinkedList and ArrayList No. of Elements x Bytes


Результат чітко показує, що 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)

535
2017-11-27 14:20



Цікаво, що LinkedList вимагає якнайбільше пам'яті, як ArrayList для зберігання одного елемента. Як неінфункціональне! Що станеться, якщо ви запустите свій приклад з -XX: + UseCompressedOops? - jontejj
Проблема з вашою математикою полягає в тому, що ваш графік сильно перебільшує вплив. Ви моделюєте об'єкти, кожен з яких містить лише int, тобто 4 або 8 байт даних. У зв'язаному списку є по суті 4 "слова" накладних витрат. Таким чином, ваш графік створює враження, що пов'язані списки використовують "п'ять разів" зберігання списків масивів. Це неправильно. Накладні витрати - 16 або 32 байти на об'єкт, як коригування адитивних, а не масштабний коефіцієнт. - Heath Hunnicutt
Жоден з об'єктів ArrayList / LinkedList / Node не містить лише int, тому я не отримую те, що ви там говорите. Я переформулював "об'єкт накладання" на "заголовок об'єкта" на clarfy - для кожного об'єкта, незалежно від системи, є заголовок 8 байтів, і так, що вставляє всі об'єкти вузла в LinkedList, котрі всі вважаються правильними, наскільки я можу скажи До речі, знову дивлячись на це, я знайшов пару інших проблем з моєю математикою в LinkedList, яка фактично змушує розділити її і ArrayList гірше. Я радий продовжувати його оновлювати, тому будь ласка, не соромтеся уточнювати та деталізувати його. - Numeron
Слід зазначити, що CompressedOops це за замовчуванням у всіх останніх JDK (7, 8 та оновлень 6 на кілька років), тому 64-розрядна версія не змінить значення ArrayList або LinkedList розміри, якщо ви чітко не вимкнули стиснуте запитання. - BeeOnRope
Це зображення графіка доступне для комерційного використання? Я хотів би його використовувати. - Ogen


ArrayList це те, що ви хочете. LinkedList це майже завжди (помилка виконання).

Чому LinkedList смокче:

  • Він використовує безліч маленьких об'єктів пам'яті, і тому впливає на продуктивність у процесі.
  • Багато малих об'єктів погано для кеш-локації.
  • Будь-яка індексована операція вимагає переходу, тобто має O (n) продуктивність. Це не є очевидним у вихідному коді, що приводить до алгоритмів O (n) повільніше, ніж якщо ArrayListбув використаний.
  • Отримання хорошої продуктивності складне.
  • Навіть коли продуктивність великої O є такою ж, як і ArrayList, вочевидь це буде набагато повільніше.
  • Це байдуже LinkedList у джерелі, тому що це, мабуть, неправильний вибір.

190
2018-01-01 20:23



Вибачте позначив вас вниз. LinkedList не смокче. Є ситуації, коли LinkedList є правильним класом для використання. Я погоджуюсь з тим, що ситуацій, де це краще, ніж арраліст, існує не так багато, але вони існують. Навчати людей, які роблять дурні речі! - David Turner
Вибачте, що у вас є багато голосуючих голосів за це. Існує дійсно дуже мало причин використовувати Java LinkedList. Окрім поганої продуктивності, він також використовує набагато більше пам'яті, ніж інші конкретні класні списки (у кожного вузла є два додаткових покажчика, і кожен вузол є окремим обгортковим об'єктом з додатковими накладними байтами, які йдуть з ними). - Kevin Brock
Це один з найбільш корисних відповідей тут. На жаль, багато програмістів не розуміють (а) різниці між абстрактними типами даних та конкретними реалізаціями, і (б) реальним значенням постійних факторів та накладних витрат на пам'ять при визначенні продуктивності. - Porculus
-1: це досить побіжний вигляд. Так, це правда, що ArrayList - це дуже універсальний інструмент. Однак він має свої обмеження. Є випадки, коли це спричинить вам проблеми, і вам доведеться використовувати LinkedList. Звичайно, це дуже спеціалізоване рішення, і, як і будь-який спеціалізований інструмент, в більшості випадків він перевершує універсальний. Але це не означає, що він "засмоктує" або щось подібне, вам просто потрібно знати, коли це використовувати. - Malcolm
@DavidTurner: Вони існують, але я думаю, що Тома стверджував, що якщо ви повинні запитати, ви, мабуть, хочете, щоб ArrayList. - Mehrdad


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

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

ArrayList - це кращий вибір для продуктивності, якщо все, що ви маєте на увазі за продуктивністю, є пропускною спроможністю, і ви можете ігнорувати затримку. У моєму досвіді на моїй роботі я не можу нехтувати невчасною латентністю.


125
2018-04-08 20:33



Чи не було б іншим рішенням керувати розміром списку програмним шляхом за допомогою методу ensureCapacity () ArrayList? На моє запитання, чому так багато речей зберігаються в купі хрупких структур даних, коли їх краще зберігати в механізмі кешування або дБ? Одного разу у мене було співбесіду, де вони поклялися про злу ArrayList, але я приходжу сюди, і я вважаю, що аналіз складності є все більш вдалим! ВЕЛИКЕ ПУНКТ ДЛЯ ОБГОВОРЕННЯ, ДУЖЕ. ДЯКУЮ! - ingyhere
як тільки ви отримаєте Java-додатки з купою 10 Гб, ви можете припинити блокування додатка протягом 25 секунд під час повного нагадування, що призводить до тайм-аутів Насправді за допомогою LinkedList ви вбиваєте смітник під час повних GC, він повинен ітератувати надмірно великий LinkedList з кеш-пам'яттю на кожному вузлі. - bestsss
Це ... жахливе рішення. ви в основному залежите від збирання GC для вас, що є неймовірно дорогим, коли ви можете просто викликати sureCapacity () замість арраліста ... - Philip Devine
@Andreas: A LinkedList  завжди виділяє в п'ять разів пам'ять, ніж звичайний масив посилань, так що ArrayList тимчасово вимагаючи в 2,5 рази все ще споживає набагато менше пам'яті, навіть якщо пам'ять не відновлена. Оскільки розміщення великих масивів обходить простір Eden, вони не впливають на поведінку GC, за винятком випадків, коли пам'яті насправді недостатньо, в цьому випадку LinkedList підірвав набагато раніше ... - Holger
@Andreas Інша проблема полягає в тому, як виділяється пам'ять. LinkedList потрібно лише невеликий фрагмент вільної пам'яті для виділення наступного елемента. ArrayList буде потрібно великий і безперервний Вільний простір для розміщення зміненого масиву. Якщо купа буде фрагментована, тоді GC може завершити переоблаштування всієї купи, щоб лише звільнити відповідний окремий блок пам'яті. - Piotr Kusmierczyk


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 Notation

ArrayLists є корисними для написання одного разу читати-багато чи додатків, але погано для додавання / видалення з фронту чи середини.


111
2018-05-19 11:21



Ви не можете порівняти великі значення O безпосередньо, не замислюючись про постійні фактори. Для малих списків (а більшість списків невеликі), O (N) ArrayList швидше, ніж O (1) LinkedList. - Porculus
Я не дбаю про продуктивність невеликих списків, а також не працює мій комп'ютер якщо не він використовується як-то в циклі. - Maarten Bodewes
LinkedList неможливо вставити в середину O(1). Він повинен пройти через половину списку, щоб знайти точку вставки. - Thomas Ahle
LinkedList: вставити в середину O (1) - це НЕПРАВИЛЬНЕ! Я дізнався, що навіть розміщення в 1/10 позиції розміру LinkedList відбувається повільніше, ніж додавання елемента в 1/10 позиції ArrayList. І ще гірше: кінець колекції. вставляючи в останні позиції (не останню) ArrayList швидше, то в останні позиції (не останню) LinkedList - kachanov
@ качанов Вставити в a LinkedList  є  O(1)  якщо у вас є ітератор до позиції вставки, тобто ListIterator.add нібито O(1) для LinkedList. - Anony-Mousse


Так, я знаю, це давнє запитання, але я кину у свої два центи:

LinkedList є майже завжди неправильний вибір, продуктивність. Існує кілька дуже специфічних алгоритмів, для яких викликається LinkedList, але вони дуже, дуже рідкісні, і алгоритм зазвичай залежить від можливості LinkedList вставляти та видаляти елементи в середині списку порівняно швидко, коли ви вже перейшли туди за допомогою ListIterator.

Існує один загальний випадок використання, у якому LinkedList перевершує ArrayList: у черзі. Однак, якщо вашою метою є продуктивність, замість LinkedList слід також розглянути можливість використання ArrayBlockingQueue (якщо ви можете визначити верхню межу вашого розміру черги заздалегідь, і може дозволити собі виділити всю пам'ять перед собою), або це Реалізація CircularArrayList. (Так, це з 2001 року, тому вам доведеться породжувати його, але я отримав співставні показники ефективності до того, що цитується в статті лише зараз у нещодавній JVM)


92
2017-11-27 01:39



З Java 6 ви можете використовувати ArrayDeque. docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html - Thomas Ahle
ArrayDeque повільніше ніж LinkedList якщо всі операції не мають однакового кінця. Це добре, коли використовується як стека, але це не робить хорошої черги. - Jeremy List
Невірно - принаймні для реалізації Oracle в jdk1.7.0_60 та в наступному тесті. Я створив тест, де я петляв понад 10 мільйонів разів, і у мене десять мільйонів випадкових цілих чисел. Всередині циклу я опросую один елемент і пропоную постійний елемент. На моєму комп'ютері, LinkedList більш ніж у 10 разів повільніше, ніж ArrayDeque і використовує менше пам'яті). Причиною є те, що, на відміну від ArrayList, ArrayDeque тримає покажчик на голову масиву, так що йому не потрібно переміщувати всі елементи, коли голову видалено. - Henno Vermeulen
ArrayDeque швидше за все, буде швидше, ніж Stack коли використовується як стек, і швидше, ніж LinkedList коли використовується як черга. - i_am_zero
Зауважте, що коментар akhil_mittal є цитатою з ArrayDeque документація - Stuart Marks


Це питання ефективності. LinkedList швидко для додавання та видалення елементів, але повільний доступ до певного елемента. ArrayList швидко для доступу до певного елемента, але може бути повільним додати до кінця, і особливо повільно видаляти в середині.

Масив проти ArrayList проти LinkedList vs Vectorйде глибше, як це робить Пов'язаний список.


50
2017-09-21 22:59





Правильно або неправильно: будь ласка, виконайте тест локально і самі вирішите!

Редагування / видалення відбувається швидше 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);
    }
}

49
2018-04-21 00:03



Для точності, ArrayList не потрібно подвоїтись. Спочатку перевірте джерела. - Danubian Sailor
Слід зазначити, що у вашому прикладі є недоліки ... Ви видаляєте з рядка між: 18 + [2, 12] байтами ("true0false", "true500000false"), в середньому 25 байт, які є розмірами елементів посередині. Відомо, що, оскільки розмір байтів елементів збільшує зв'язковий список, він покращується, оскільки збільшується розмір списку, суміжний масив (список) буде кращим. Найголовніше, що ви робите .equals () на рядках - це не дешева операція. Якщо ви замість цього використовуєте цілі числа, я думаю, що буде різниця. - Centril
- і це, мабуть, також пояснює, чому для видалення / містить дуже мало відмінностей. - Centril
"... гірше при застосуванні великого обсягу": Це непорозуміння. LinkedList має набагато більший обсяг пам'яті, тому що для кожного елемента є об'єкт вузла з п'ятьма полями. На багатьох системах, що становить 20 байт накладних витрат. Середня кількість пам'яті, що накладаються на елемент для ArrayList це слово з половиною, що складає 6 байт, і 8 байт у гіршому випадку. - Lii
Я зробив кращу версію вашого тесту тут, з результатами - додавання-закінчення продуктивності для ар-реліста є штучно низьким для вашої, тому що addAll надає масив пам'яті ТІЛЬКИ вихідний розмір, тому перша вставка завжди викликає арраїкопію. Також це включає цикли розігріву, щоб дозволити збирання JIT до збирання даних. - BobMcGee


ArrayList по суті є масивом. LinkedList реалізований як подвійний список, пов'язаний.

The get досить ясно. O (1) для ArrayList, оскільки ArrayList дозволити випадковий доступ за допомогою індексу. O (n) для LinkedList, тому що потрібно знайти індекс першим. Примітка: існують різні версії add і remove.

LinkedList швидше додавати і видаляти, але повільніше отримувати. Коротко, LinkedList має бути кращим, якщо:

  1. немає великої кількості випадкового доступу елемента
  2. існує велика кількість операцій "додавання / видалення"

=== ArrayList ===

  • додати (E e)
    • додати в кінці ArrayList
    • вимагати витрати на зміну розміру пам'яті.
    • O (n) найгірше, O (1) амортизується
  • додати (int-індекс, елемент E)
    • додати до певної позиції індексу
    • вимагає переміщення та можлива вартість зміни розміру пам'яті
    • O (n)
  • видалити (int index)
    • видалити вказаний елемент
    • вимагає переміщення та можлива вартість зміни розміру пам'яті
    • O (n)
  • видалити (об'єкт o)
    • видаліть перше входження вказаного елемента з цього списку
    • потрібно спочатку шукати елемент, а потім змінити вартість зміни розміру пам'яті
    • O (n)

=== LinkedList ===

  • додати (E e)

    • додати до кінця списку
    • O (1)
  • додати (int-індекс, елемент E)

    • Вставити у вказану позицію
    • Потрібно знайти перше місце
    • O (n)
  • видалити ()
    • видалити перший елемент списку
    • O (1)
  • видалити (int index)
    • видалити елемент з вказаним індексом
    • потрібно спочатку знайти елемент
    • O (n)
  • видалити (об'єкт o)
    • видалити перше входження вказаного елемента
    • потрібно спочатку знайти елемент
    • O (n)

Ось фігура з programcreek.com (add і remove є першим типом, тобто додати елемент у кінці списку та видалити елемент у вказаній позиції у списку.):

enter image description here


38
2017-11-27 01:41



"LinkedList швидше, ніж додавати / видаляти". Неправильно, перевірте відповідь вище stackoverflow.com/a/7507740/638670 - Nerrve