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

Ответ 1

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

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

Ответ 2

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

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

Ответ 3

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

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

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

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

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

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

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

Ответ 4

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

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

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

iterator.insert(E element)

с a 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).

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

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

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

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

Ответ 5

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

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

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

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

Ответ 6

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

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

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