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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

iterator.insert(E element)

с итератором , полученным через

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 (), а также количество перемещений итератора по списку (e. g вы можете выполнить только один последовательный проход по списку, чтобы выполнить все необходимые вставки). Это делает его варианты использования весьма ограниченными по количеству, но тем не менее они встречаются очень и очень часто. И производительность LinkedList в них является причиной того, что он (и будет в будущем) храниться во всех коллекциях контейнеров на всех языках, а не только на Java.

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

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

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

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

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

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

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

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

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

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

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

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

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

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