Массив против связанного списка

Ответ 1

• Легче хранить данные разных размеров в связанном списке. Массив предполагает, что каждый элемент имеет точно такой же размер.
• Как вы упомянули, легче связать список, чтобы органично расти. Размер массива должен быть известен заранее или воссоздан, когда ему нужно расти.
• Перетасовка связанного списка - это просто вопрос изменения того, что указывает на что. Перетасовка массива сложнее и/или занимает больше памяти.
• Пока ваши итерации происходят в контексте "foreach", вы не теряете производительность на итерации.

Ответ 2

Еще одна веская причина в том, что связанные списки хорошо поддаются эффективному многопоточному внедрению. Причиной этого является то, что изменения, как правило, локальны - затрагивают только указатель или два для вставки и удаления в локализованной части структуры данных. Таким образом, у вас может быть много потоков, работающих в одном и том же связанном списке. Более того, можно создавать версии без блокировки с использованием операций типа CAS и вообще избегать блокировок большого веса.

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

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

Ответ 3

В Википедии есть очень хороший раздел о различиях.

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

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

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

http://en.wikipedia.org/wiki/Linked_list

Ответ 4

Я добавлю еще один - списки могут действовать как чисто функциональные структуры данных.

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

a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)

то есть:

b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next  

без необходимости копировать данные, на которые указывают a в b и c.

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

Ответ 5

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

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

Ответ 6

Объединение двух связанных списков (особенно двух дважды связанных списков) происходит гораздо быстрее, чем объединение двух массивов (при условии, что слияние является разрушительным). Первый принимает O (1), последний принимает O (n).

EDIT: Чтобы уточнить, я имел в виду "слияние" здесь в неупорядоченном смысле, а не в сортировке слияния. Возможно, "конкатенирование" было бы лучшим словом.

Ответ 7

Прежде всего, в С++ связанных списках не должно быть больше проблем с работой, чем с массивом. Вы можете использовать std:: list или список указателей boost для связанных списков. Ключевыми проблемами со связанными списками против массивов являются дополнительное пространство, необходимое для указателей и ужасный случайный доступ. Вы должны использовать связанный список, если вы

• вам не нужен произвольный доступ к данным
• вы будете добавлять/удалять элементы, особенно в середине списка.

Ответ 8

Широко недооцененный аргумент для ArrayList и LinkedList заключается в том, что LinkedLists неудобны при отладке. Время, затраченное разработчиками обслуживания на понимание программы, например. для поиска ошибок, увеличения и IMHO иногда не оправдывает наносекунды улучшением производительности или байтами в потреблении памяти в корпоративных приложениях. Иногда (ну, конечно, это зависит от типа приложений), лучше потратить несколько байтов, но иметь приложение, которое более удобно или легко понять.

Например, в среде Java и использовании отладчика Eclipse отладка ArrayList покажет очень понятную структуру:

arrayList   ArrayList<String>
  elementData   Object[]
    [0] Object  "Foo"
    [1] Object  "Foo"
    [2] Object  "Foo"
    [3] Object  "Foo"
    [4] Object  "Foo"
    ...

С другой стороны, просмотр содержимого LinkedList и поиск определенных объектов становится кошмаром для разворачивания-дерева, не говоря уже о когнитивных накладных расходах, необходимых для фильтрации внутренних объектов LinkedList:

linkedList  LinkedList<String>
    header  LinkedList$Entry<E>
        element E
        next    LinkedList$Entry<E>
            element E   "Foo"
            next    LinkedList$Entry<E>
                element E   "Foo"
                next    LinkedList$Entry<E>
                    element E   "Foo"
                    next    LinkedList$Entry<E>
                    previous    LinkedList$Entry<E>
                    ...
                previous    LinkedList$Entry<E>
            previous    LinkedList$Entry<E>
        previous    LinkedList$Entry<E>

Ответ 9

Для меня это так:

• Доступ

  • Связанные списки позволяют использовать только последовательный доступ к элементам. Таким образом, алгоритмические сложности - порядок O (n)
  • Массивы позволяют произвольный доступ к своим элементам, и, следовательно, сложность - это порядок O (1)

• хранения

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

• Размер

  • Размер Связанные списки динамичны по своей природе.
  • Размер массива ограничен объявлением.

• Установка/удаление

  • Элементы можно вставлять и удалять в связанных списках неограниченно.
  • Вставка/удаление значений в массивах очень дорого. Это требует перераспределения памяти.

Ответ 10

Две вещи:

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

Никогда не кодируйте связанный список при использовании С++. Просто используйте STL. Как трудно реализовать, никогда не должно быть основанием для выбора одной структуры данных над другой, поскольку большинство из них уже реализовано там.

Что касается фактических различий между массивом и связанным списком, для меня важна то, как вы планируете использовать структуру. Я буду использовать термин vector, так как этот термин для изменяемого размера массива в С++.

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

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

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

Ответ 11

Эрик Липперт недавно опубликовал сообщение по одной из причин, по которым массивы следует использовать консервативно.

Ответ 12

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

Ответ 13

Здесь быстрый: удаление предметов происходит быстрее.

Ответ 14

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

Ответ 15

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

Ответ 16

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

В наши дни создание связанного списка - это просто упражнение для студентов, чтобы они могли понять концепцию. Вместо этого каждый использует предварительно построенный список. В С++, основываясь на описании в нашем вопросе, это, вероятно, означает stl-вектор (#include <vector>).

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

Ответ 17

Это действительно вопрос эффективности, накладные расходы на вставку, удаление или перемещение (где вы не просто свопинг) элементы внутри связанного списка минимальны, то есть сама операция O (1), стихи O (n) для массив. Это может иметь существенное значение, если вы сильно работаете над списком данных. Вы выбрали свои типы данных, основываясь на том, как вы будете работать на них, и выберите наиболее эффективные для используемого вами алгоритма.

Ответ 18

Массивы имеют смысл, когда будет известно точное количество элементов, и где поиск по индексу имеет смысл. Например, если бы я хотел сохранить точное состояние вывода видео в данный момент без сжатия, я бы, вероятно, использовал массив размером [1024] [768]. Это даст мне именно то, что мне нужно, и список будет намного, намного медленнее, чтобы получить значение данного пикселя. В тех местах, где массив не имеет смысла, обычно существуют лучшие типы данных, чем список для эффективного использования данных.

Ответ 19

Массивы Vs Связанный список:

• Распределение памяти массива иногда происходит из-за фрагментированной памяти.
• Кэширование лучше в массивах, так как всем элементам выделено смежное пространство памяти.
• Кодирование более сложное, чем массивы.
• Ограничение размера в Linked List, в отличие от массивов
• Вставка/удаление быстрее в списке ссылок и доступ быстрее в массивах.
• Связанный список лучше с точки зрения многопоточности.

Ответ 20

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

Ответ 21

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

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

Ваша первая проблема, как вы отметили сами, - это список, связанный с вставкой, который позволяет вставлять в O (1), но для массива обычно требуется O (n). Эту проблему можно частично преодолеть - можно создать структуру данных, которая дает массивный, как по порядку интерфейс доступа, где и чтение, и запись, в худшем случае, логарифмические.

Вторая, и более серьезная проблема заключается в том, что для элемента, находящего следующий элемент, является O (n). Если набор не был изменен, вы могли бы сохранить индекс элемента как ссылку вместо указателя, тем самым сделав find-next операцию O (1), но поскольку это все, что у вас есть, это указатель на сам объект и никоим образом для определения его текущего индекса в массиве, кроме как путем сканирования всего "массива". Это непреодолимая проблема для массивов - даже если вы можете оптимизировать вставки, вы ничего не можете сделать, чтобы оптимизировать операцию поиска следующего типа.

Ответ 22

В массиве у вас есть привилегия доступа к любому элементу в O (1) времени. Таким образом, он подходит для операций, таких как двоичный поиск Quick sort и т.д. Связанный список, с другой стороны, подходит для удаления вставки как его в O (1) раз. Оба имеют преимущества, а также недостатки и предпочитают, чтобы один над другим сводился к тому, что вы хотите реализовать.

- Большой вопрос: можем ли мы иметь гибрид обоих. Что-то вроде того, что python и perl реализуют как списки.

Ответ 23

Связанный список

Его более предпочтительно, когда речь заходит о вставке! В основном, что происходит, это то, что он имеет дело с указателем

1 → 3 → 4

Вставить (2)

1........ 3...... 4
..... 2

Наконец

1 → 2 → 3 → 4

Одна стрелка из 2 точек в 3 и стрелка 1 точки при 2

Simple!

Но из массива

| 1 | 3 | 4 |

Вставить (2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

Хорошо, кто-нибудь может визуализировать разницу! Только для 4-х индексов мы выполняем 3 шага

Что делать, если длина массива составляет один миллион? Является ли массив эффективным? Ответ - нет!:)

То же самое касается удаления! В Linked List мы можем просто использовать указатель и аннулировать элемент и следующий в классе объектов! Но для массива нам нужно выполнить shiftLeft()

Надеюсь, что это поможет!:)

Ответ 24

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

Предположим, что вы хотите хранить несколько вещей с данными, тогда их можно легко расширить в связанном списке.

Контейнеры STL обычно имеют связанную реализацию списка за сценой.

Ответ 25

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

Недостатком может быть то, что указатели занимают много места.

И о том, что кодирование сложнее: Обычно вам не нужен связанный с кодом список (или только один раз), они включены в STL  и это не так сложно, если вы все еще должны это делать.

Ответ 26

Я также считаю, что список ссылок лучше, чем массивы. потому что мы перемещаемся в списке ссылок, но не в массивах

Ответ 27

В зависимости от вашего языка некоторые из этих недостатков и преимуществ можно было бы рассмотреть:

C Язык программирования: при использовании связанного списка (обычно с помощью указателей на структуру) особое внимание следует уделить тому, чтобы вы не пропускали память. Как уже упоминалось ранее, связанные списки легко перетасовать, потому что все делали, это изменение указателей, но будем ли мы забывать освобождать все?

Java: у Java есть автоматический сбор мусора, поэтому утечка памяти не будет проблемой, но скрытая от программиста высокого уровня информация о реализации того, что является связанным списком. Такие методы, как удаление node из середины списка, сложнее процедуры, чем ожидали бы некоторые пользователи этого языка.

Ответ 28

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

Но, может быть, нам не нужно жить с границами обоих, и получить лучшее из обоих, в то же время... а??

Для удаления массива вы можете использовать байт "Удаленный", чтобы представить факт, что строка была удалена, поэтому переупорядочение массива больше не требуется. Чтобы облегчить нагрузку на вставки или быстро меняющиеся данные, используйте для этого связанный список. Затем, обратившись к ним, сначала попросите свою логику, а затем другую. Таким образом, использование их в комбинации дает вам лучшее из обоих.

Если у вас действительно большой массив, вы можете объединить его с другим, гораздо меньшим массивом или связанным списком, где меньший вмещает 20, 50, 100 самых последних использованных элементов. Если необходимый не находится в более коротком связанном списке или массиве, вы переходите к большому массиву. Если вы найдете там, вы можете добавить его к меньшему связанному списку/массиву с предположением, что "все, что было недавно использовано, наиболее похоже на повторное использование" (и да, возможно, ударяя последний список из списка). Во многих случаях это верно, и я решил проблему, с которой я должен был справиться в модуле проверки разрешений безопасности .ASP с легкостью, элегантностью и впечатляющей скоростью.

Ответ 29

В то время как многие из вас затронули основной файл adv./dis связанного списка с массивом, большинство сравнений - это то, как один лучше/хуже другого. Eg. вы можете делать произвольный доступ в массиве, но не возможно в связанном списке и других. Однако это предполагает, что списки ссылок и массив будут применяться в аналогичном приложении. Однако правильным ответом должно быть то, как список ссылок будет предпочтительнее, чем массив, и наоборот, в конкретном развертывании приложения. Предположим, вы хотите реализовать приложение для словарей, что бы вы использовали? Массив: mmm это позволит легко найти через двоичный поиск и другой поиск algo.. но позволяет подумать, как список ссылок может быть лучше. Скажем, вы хотите искать "Blob" в словаре. Имеет ли смысл иметь список ссылок A- > B- > C- > D ---- > Z, а затем каждый элемент списка также указывает на массив или другой список всех слов, начинающихся с этой буквы.

A -> B -> C -> ...Z
|    |    |
|    |    [Cat, Cave]
|    [Banana, Blob]
[Adam, Apple]

Теперь лучший подход или плоский массив [Адам, Яблоко, Банан, Боб, Кошка, Пещера]? Возможно ли это с массивом? Таким образом, основным преимуществом списка ссылок является то, что вы можете иметь элемент, который не просто указывает на следующий элемент, но также и на другой список ссылок/массив/кучу/или любую другую ячейку памяти. Массив - это одна плоская конхистическая память, нарезанная блоками размером элемента, который он собирается хранить. Список ссылок, с другой стороны, представляет собой куски несвязанных блоков памяти (может быть любого размера и может хранить что угодно) и указывая на каждый другой так, как вы хотите. Аналогичным образом можно сказать, что вы делаете USB-накопитель. Теперь вы хотите, чтобы файлы сохранялись как любой массив или список ссылок? Я думаю, вы поняли, что я указываю:)

Ответ 30

Почему кто-то хочет использовать связанный список по массиву?

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