Реализация списков: действительно ли 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 почти всегда является хорошей заменой для него, хотя он использует сладко больше памяти.

Мои вопросы:

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

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

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

Answer 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 в обоих концах списка значительно ускоряет реализацию структур данных, таких как Queues, Stacks и Deques.

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

Answer 2

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

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

Answer 3

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

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

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

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

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

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

Answer 6

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

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

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