Реализация списков: действительно ли LinkedList так плохо работает по сравнению с ArrayList и TreeList?

Question

Взято из Apache TreeList doc :

Следующая относительная статистика производительности свидетельствует об этом Класс:

             get  add  insert  iterate  remove
 TreeList       3    5       1       2       1
 ArrayList      1    1      40       1      40
 LinkedList  5800    1     350       2     325

Далее говорится:

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

Мои вопросы:

• Что с ArrayList add, insert и remove раз дробления LinkedList? Должны ли мы ожидать, для один, это реальные случаи вставки и удаления очень благосклонно ArrayList?

• Это TreeList просто положить гвоздь в гроб почтенного LinkedList?

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

Answer 1

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

Это ясно показывает, что TreeList быстрее для достаточно больших списков, что касается вставки / удаления в произвольных позициях. Но AFAIK, TreeLists реализованы в виде двоичного дерева поиска и имеют гораздо большую константу, связанную с его операциями O (logn), чем аналогичные операции с ArrayLists, которые являются просто обертками вокруг массива. Это делает TreeList более медленным для небольших списков. Кроме того, если все, что вы делаете - это добавляете элемент в список, производительность O (1) ArrayList / LinkedList явно выше. Кроме того, часто число вставок / удалений намного меньше, чем количество обращений, что в большинстве случаев приводит к ускорению ArrayList в целом. Постоянное время вставки / удаления LinkedList в обоих концах списка значительно ускоряет реализацию структур данных, таких как очереди, стеки и запросы.

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

Answer 2

Это связано с структурами данных , стоящими за этими коллекциями. TreeList - это дерево , которое обеспечивает относительно быстрое чтение, вставку, удаление (все O (log n)). ArrayList использует массив для хранения данных, поэтому при вставке или удалении каждый элемент в массиве должен быть смещен вверх или вниз (O (n) в худшем случае). Массивы также имеют фиксированный размер, поэтому, если он переполняет емкость текущего массива, необходимо создать новый, более крупный (обычно удваивающий размер последнего, чтобы сохранить размеры до минимума). LinkedList использовал ... связанный список . Связанный список обычно имеет ссылку на первые (а иногда и последние) элементы в списке. Затем каждый элемент в списке имеет ссылку на следующий элемент в списке (для односвязного списка) или на следующий и предыдущий элементы (для двойного связанного списка). Из-за этого, чтобы получить доступ к определенному элементу, вы должны пройти через каждый элемент, прежде чем он попадет туда (O (n) наихудший случай). При вставке или удалении определенных элементов вы должны найти позицию для вставки или удаления их, что занимает время (O (n) в худшем случае). Однако очень просто добавить еще один элемент в начало или конец (O (1)).

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

Answer 3

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

LinkedList::add(int index, E element) 
          Inserts the specified element at the specified position in this list.

, который, похоже, использовался для получения статистики, но

iterator.insert(E element)

с iterator, полученным через

public abstract ListIterator<E> listIterator(int index)
Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list.

или

public Iterator<E> iterator()
Returns an iterator over the elements in this list (in proper sequence).

, тогда вы непременно получите лучшую произвольную производительность вставки. Это, конечно, подразумевает, что вы можете ограничить количество вызовов iterator () и listIterator () и количество перемещений итератора по списку (например, вы можете сделать только один последовательный проход по списку, чтобы выполнить все необходимые вставки ). Это делает его варианты использования весьма ограниченными по их количеству, но, тем не менее, они встречаются очень и очень часто. И производительность LinkedList в них является причиной того, что она (и будет в будущем) хранится во всех коллекциях контейнеров всех языков, не только Java.

PS. Все вышеперечисленное, конечно, относится ко всем другим операциям, таким как get (), remove () и т. Д. Т.е. тщательно спроектированный доступ через итератор сделает их всех O (1) с очень маленькой фактической константой. То же самое, конечно, можно сказать и для всех других списков, то есть доступ итератора ускорит их все (хотя и незначительно). Но не для вставки ArrayList () и удаления () - они все равно будут O (n) ... И не для вставки TreeList () и удаления () - затраты на балансировку дерева - это не то, чего вы можете избежать ... И TreeList вероятно, у меня больше памяти ... Вы поняли мою идею. Чтобы подвести итог всего этого, LinkedList предназначен для небольших высокопроизводительных сканирующих операций над списками. Нужен ли вам этот вариант использования или нет - только вы можете сказать.

PSS. Тем не менее, поэтому я тоже остаюсь

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

Answer 4

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

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

Если они сделают ArrayList надлежащего размера, начинать с растущих болей не будет ничего. Если ArrayList маленький, растущие боли не имеют значения.

Для LinkedList, если все операции находятся в начале списка, это повлияет гораздо меньше, чем если бы они были в конце.

То, что вы должны делать, это всегда использовать интерфейс, например: список при объявлении переменных и параметров, тогда вы можете изменить "new LinkedList ();" в "новый ArrayList ();" и профилируйте код, чтобы увидеть, как он работает в вашем конкретном коде.

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

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

Answer 5

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

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

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

Answer 6

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

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

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

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