Я использую много списков и массивов, но мне еще не приходилось сталкиваться со сценарием, в котором список массивов нельзя было бы использовать так же легко, как, если не проще, связанный список. Я надеялся, что кто-нибудь может дать мне несколько примеров, когда связанный список заметно лучше.
arrays
list
arraylist
linked-list
faceless1_14
источник
источник
Ответы:
Связанные списки предпочтительнее массивов, когда:
вам нужны постоянные вставки / удаления из списка (например, в вычислениях в реальном времени, где предсказуемость времени абсолютно необходима)
Вы не знаете, сколько предметов будет в списке. При использовании массивов может потребоваться повторное объявление и копирование памяти, если массив становится слишком большим
вам не нужен произвольный доступ к любым элементам
вы хотите иметь возможность вставлять элементы в середину списка (например, очередь с приоритетами)
Массивы предпочтительнее, когда:
вам нужен индексированный / произвольный доступ к элементам
Вы заранее знаете количество элементов в массиве, чтобы вы могли выделить правильный объем памяти для массива.
вам нужна скорость при переборе всех элементов в последовательности. Вы можете использовать указатель на массиве для доступа к каждому элементу, тогда как вам нужно искать узел на основе указателя для каждого элемента в связанном списке, что может привести к сбоям страницы, что может привести к падению производительности.
память является проблемой. Заполненные массивы занимают меньше памяти, чем связанные списки. Каждый элемент в массиве - это просто данные. Каждый узел связанного списка требует данных, а также одного (или нескольких) указателей на другие элементы в связанном списке.
Списки массивов (как и в .Net) дают вам преимущества массивов, но динамически распределяют ресурсы так, что вам не нужно слишком беспокоиться о размере списка, и вы можете удалять элементы в любом индексе без каких-либо усилий или повторных действий. шаркающие элементы вокруг. С точки зрения производительности, массивы работают медленнее, чем необработанные массивы.
источник
Массивы имеют O (1) произвольный доступ, но очень дорого добавлять или удалять вещи.
Связанные списки действительно дешевы, чтобы добавлять или удалять элементы в любом месте и повторять их, но произвольный доступ - это O (n).
источник
ArrayLists хороши для записи один раз для чтения или добавления, но плохо подходят для добавления / удаления спереди или посередине.
источник
Чтобы добавить к другим ответам, большинство реализаций списка массивов резервируют дополнительную емкость в конце списка, чтобы новые элементы могли быть добавлены в конец списка за O (1) раз. Когда емкость списка массивов превышена, новый, больший массив выделяется внутри, и все старые элементы копируются. Обычно новый массив в два раза больше старого. Это означает, что в среднем добавление новых элементов в конец списка массивов является операцией O (1) в этих реализациях. Таким образом, даже если вы заранее не знаете количество элементов, список массивов может все же быть быстрее, чем связанный список для добавления элементов, если вы добавляете их в конце. Очевидно, что вставка новых элементов в произвольные места в списке массивов все еще является операцией O (n).
Доступ к элементам в списке массивов также быстрее, чем в связанном списке, даже если доступ осуществляется последовательно. Это связано с тем, что элементы массива хранятся в непрерывной памяти и могут быть легко кэшированы. Узлы связанного списка потенциально могут быть разбросаны по разным страницам.
Я бы рекомендовал использовать только связанный список, если вы знаете, что собираетесь вставлять или удалять элементы в произвольных местах. Списки массивов будут быстрее почти для всего остального.
источник
Преимущество списков появляется, если вам нужно вставить элементы посередине, и вы не хотите начинать изменять размер массива и перемещать его.
Вы правы в том, что обычно это не так. У меня было несколько подобных случаев, но не слишком много.
источник
Все зависит от того, какой тип операции вы выполняете во время итерации, все структуры данных имеют компромисс между временем и памятью, и в зависимости от наших потребностей мы должны выбрать правильный DS. Так что в некоторых случаях LinkedList быстрее, чем массив, и наоборот. Рассмотрим три основные операции над структурами данных.
Поскольку массив - это структура данных, основанная на индексе, поиск в array.get (index) займет O (1) времени, в то время как связанный список не является индексным DS, поэтому вам нужно перейти к индексу, где index <= n, n - размер связанного списка, так что массив быстрее связывает список, когда имеет произвольный доступ к элементам.
Q. Так в чем красота этого?
Поскольку массивы являются смежными блоками памяти, их большие куски будут загружаться в кэш при первом доступе, что делает его сравнительно быстрым для доступа к остальным элементам массива, поскольку доступ к элементам в массиве приводит к увеличению локальности ссылок, что приводит к уменьшению улова. В противном случае локальность кэша относится к операциям, находящимся в кэше, и, таким образом, выполняется намного быстрее по сравнению с памятью, в основном в массиве мы максимально увеличиваем шансы последовательного доступа к элементам в кэше. Хотя связанные списки не обязательно находятся в смежных блоках памяти, нет гарантии, что элементы, которые последовательно появляются в списке, фактически располагаются рядом друг с другом в памяти, это означает, что меньше обращений в кэш, например
Это легко и быстро в LinkedList, так как вставка является операцией O (1) в LinkedList (в Java) по сравнению с массивом, рассмотрим случай, когда массив заполнен, нам нужно скопировать содержимое в новый массив, если массив заполнится, что делает вставку элемент в ArrayList из O (n) в худшем случае, в то время как ArrayList также должен обновить свой индекс, если вы вставляете что-либо где-нибудь, кроме конца массива, в случае связанного списка нам не нужно изменять его размер, вам просто нужно обновить указатели.
Он работает как вставки и лучше в LinkedList, чем массив.
источник
Это наиболее распространенные используемые реализации Collection.
ArrayList:
вставка / удаление в конце обычно O (1) худший случай O (n)
вставить / удалить в середине O (n)
восстановить любую позицию O (1)
LinkedList:
вставить / удалить в любой позиции O (1) (обратите внимание, если у вас есть ссылка на элемент)
получить в середине O (N)
получить первый или последний элемент O (1)
Вектор: не используйте его. Это старая реализация, похожая на ArrayList, но со всеми синхронизированными методами. Это не правильный подход для общего списка в многопоточной среде.
HashMap
вставить / удалить / получить по ключу в O (1)
TreeSet вставить / удалить / содержит в O (журнал N)
HashSet вставить / удалить / содержит / размер в O (1)
источник
В действительности локальность памяти оказывает огромное влияние на производительность при реальной обработке.
Более широкое использование потоковой передачи диска при обработке «больших данных» и произвольного доступа показывает, как структурирование вашего приложения может значительно повысить производительность в более широком масштабе.
Если есть какой-либо способ последовательного доступа к массиву, это, безусловно, самый эффективный способ. Проектирование с этой целью должно, по крайней мере, рассматриваться, если важна производительность.
источник
Хмм, Arraylist может быть использован в следующих случаях:
Например, вам нужно импортировать и получить доступ ко всем элементам в списке контактов (размер которых вам неизвестен)
источник
Используйте связанный список для Radix Sort по массивам и для полиномиальных операций.
источник
1) Как объяснено выше, операции вставки и удаления дают хорошую производительность (O (1)) в LinkedList по сравнению с ArrayList (O (n)). Следовательно, если существует требование частого добавления и удаления в приложении, тогда LinkedList является лучшим выбором.
2) Операции поиска (получения метода) выполняются быстро в Arraylist (O (1)), но не в LinkedList (O (n)), поэтому, если операций добавления и удаления меньше и требуется больше операций поиска, лучшим выбором будет ArrayList.
источник
Я думаю, что главное отличие в том, нужно ли вам часто вставлять или удалять что-либо из верхней части списка.
С массивом, если вы удаляете что-то из верхней части списка, сложность равна o (n), потому что все индексы элементов массива должны будут сдвигаться.
Для связанного списка это o (1), потому что вам нужно только создать узел, переназначить заголовок и назначить ссылку next как предыдущий заголовок.
При частой вставке или удалении в конце списка массивы предпочтительнее, поскольку сложность будет o (1), переиндексация не требуется, но для связанного списка это будет o (n), потому что вам нужно идти из головы до последнего узла.
Я думаю, что поиск в связанном списке и массивах будет o (log n), потому что вы, вероятно, будете использовать бинарный поиск.
источник
Я провел несколько тестов и обнаружил, что класс списка на самом деле быстрее, чем LinkedList для случайной вставки:
Требуется 900 мс для связанного списка и 100 мс для класса списка.
Создает списки последующих целых чисел. Каждое новое целое число вставляется после случайного числа, которое уже есть в списке. Может быть, класс List использует что-то лучше, чем просто массив.
источник
Массивы, безусловно, являются наиболее широко используемыми структурами данных. Тем не менее, связанные списки оказываются полезными по-своему уникальным способом, когда массивы неуклюжи - или, по меньшей мере, дороги.
Связанные списки полезны для реализации стеков и очередей в ситуациях, когда их размер может варьироваться. Каждый узел в связанном списке может быть выдвинут или вытолкнут, не нарушая большинство узлов. То же самое касается вставки / удаления узлов где-то посередине. В массивах, однако, все элементы должны быть сдвинуты, что является дорогостоящей работой с точки зрения времени выполнения.
Двоичные деревья и двоичные деревья поиска, хэш-таблицы и попытки - это некоторые структуры данных, в которых - по крайней мере в C - вам нужны связанные списки в качестве основного компонента для их построения.
Однако следует избегать связанных списков в ситуациях, когда ожидается, что он сможет вызывать любой произвольный элемент по его индексу.
источник
Простой ответ на вопрос можно дать, используя следующие пункты:
Массивы должны использоваться, когда требуется набор элементов данных аналогичного типа. Принимая во внимание, что связанный список представляет собой набор связанных данных элементов смешанного типа, известных как узлы.
В массиве можно посетить любой элемент за O (1) раз. Принимая во внимание, что в связанном списке нам нужно было бы пройти весь связанный список от головы до требуемого узла, занимая O (n) времени.
Для массивов конкретный размер должен быть объявлен изначально. Но связанные списки имеют динамический размер.
источник