Почему связанные списки быстрее, чем массивы?

Question

Я очень озадачен этим. Везде написано «связанные списки работают быстрее, чем массивы», но никто не пытается сказать «ПОЧЕМУ». Используя простую логику, я не могу понять, как связанный список может быть быстрее. В массиве все ячейки расположены рядом друг с другом, так что, если вы знаете размер каждой ячейки, легко достичь одной ячейки мгновенно. Например, если есть список из 10 целых чисел, и я хочу получить значение в четвертой ячейке, тогда я просто иду прямо к началу массива + 24 байта и читаю оттуда 8 байтов.

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

Так как, черт возьми, шаг за шагом идти быстрее, чем переходить непосредственно к элементу?

Answer 1

Заголовок этого вопроса вводит в заблуждение.

Он утверждает, что связанные списки на быстрее, чем массивы, без ограничения области действия. Существует множество случаев, когда массивы могут быть значительно быстрее, и несколько раз, когда связанный список может быть значительно быстрее: особый случай связанных списков " Быстрее "не поддерживается.

Есть две вещи, которые следует учитывать:

1. Теоретические границы связанных списков и массивов в конкретной операции ; и
2. Реальная модель реализации и использования, включая локальность и распределение кэша.

Что касается доступа к индексируемому элементу: операция - это O(1) в массиве , и, как указано, она очень быстрая (просто смещение). Операция - это O(k) в связанном списке (где k - индекс и всегда может быть << n, в зависимости) , но , если связанный список уже при обходе тогда это O(1) за шаг, который "совпадает" с массивом. Если массив обход (for(i=0;i<len;i++) быстрее (или медленнее), зависит от конкретной реализации / языка / времени выполнения.

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

Удачного кодирования.

---

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

Answer 2

Как и большинство проблем в программировании, контекст - это все . Вам нужно подумать об ожидаемых шаблонах доступа к вашим данным и затем соответствующим образом спроектировать систему хранения. Если вы вставляете что-то один раз, а затем обращаетесь к нему 1 000 000 раз, то кого это волнует, сколько стоит вставка? С другой стороны, если вы вставляете / удаляете так часто, как читаете, решение об этом влияют на эти затраты.

Answer 3

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

Последовательная итерация по списку один за другим - более или менее одинаковая скорость в связанном списке и массиве.

Получение одного определенного элемента в середине намного быстрее в массиве.

И массив может тратить пространство, потому что очень часто при расширении массива выделяется больше элементов, чем необходимо в данный момент времени (вспомним ArrayList в Java).

Так что вам нужно выбратьваша структура данных в зависимости от того, что вы хотите сделать:

много вставок и последовательная итерация -> использовать LinkedList

произвольный доступ и в идеале предварительно определенный размер -> использовать массив

Answer 4

Поскольку память не перемещается, когда вставка выполняется в середине массива. Для представленного вами случая это правда - массивы быстрее, арифметика нужна только для перехода от одного элемента к другому. Связанный список требует косвенности и фрагментов памяти. Ключ должен знать, какую структуру использовать и когда.

Answer 5

Связанные списки предпочтительнее массивов, когда:

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

б) вы не знаете, сколько предметов будет в списке.С массивами вам может потребоваться повторно объявить и скопировать память, если массив становится слишком большим

в) вам не нужен произвольный доступ к любым элементам

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

Массивы предпочтительнее, когда:

a) требуется индексированный / произвольный доступ к элементам

b) вы заранее знаете количество элементов в массиве, чтобы вы могли выделить правильный объем памяти для массива

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

г) память является проблемой.Заполненные массивы занимают меньше памяти, чем связанные списки.Каждый элемент в массиве - это просто данные.Каждый узел связанного списка требует данных, а также одного (или нескольких) указателей на другие элементы в связанном списке.

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

Ссылка: ответ Ламара https://stackoverflow.com/a/393578/6249148