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

Question

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

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

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

Этот вопрос не является дубликатом this question, потому что другой вопрос задает конкретно конкретный класс Java, в то время как этот вопрос касается общих структур данных.

Answer 1

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

Answer 2

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

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

Answer 3

Это быстро: Удаление предметов происходит быстрее.

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

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

Answer 8

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

Answer 9

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

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

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

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

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

Answer 10

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

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

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

Answer 11

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

Answer 12

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

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

Answer 13

Две вещей :

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

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

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

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

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

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

Answer 14

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

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

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

Answer 15

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

Answer 16

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

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

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

Answer 17

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

Например, вы можете иметь совершенно разные списки обмена же концевая секция

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 

без необходимости копировать эти данные, на которые указывает в Ь и с.

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

Answer 18

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

Answer 19

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

Answer 20

Общепринятый аргумент для ArrayList и LinkedList заключается в том, что Связанные списки неудобны при отладке. Время, затраченное разработчиками обслуживания на понимание программы, например. для поиска ошибок, увеличения и 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 и поиск конкретных объекты становится Expand-The-Tree щелкающего кошмар, не говоря уже о познавательной нагрузке, необходимой для фильтрации 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> 

Answer 21

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

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

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

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

Answer 22

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

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

Answer 23

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

1. Доступ

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

2. Хранения

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

3. Размер

   • Размер Linked списков динамичны по своей природе.
   • Размер массив ограничен декларацией.

4. Вставка/Удаление

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

Answer 24

Люди, использующие linklist должны читать. Люди снова будут влюблены в массив. Это говорит о Out Of Order exeuction, аппаратной предвыборки, латентности памяти и т.д.

http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html

Answer 25

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

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

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

Answer 26

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

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

Answer 27

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

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

1 -> 3 -> 4

Вставка (2)

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

Наконец

1 -> 2 -> 3 -> 4

Одна стрелки от 2-й точек 3 и стрелка 1 точек на 2

Простой!

Но из массива

| 1 | 3 | 4 |

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

Ну любой может визуализировать разницу! Только для индекса 4 мы выполняем 3 этапа

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

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

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

Answer 28

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

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

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

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

Answer 29

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

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

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

Answer 30

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

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

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

Answer 31

Разница между ArrayList и LinkedList

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

ArrayList -

1. ArrayList внутренне использует динамический массив для хранения элементов.

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

3. ArrayList класс может выступать в качестве списка только потому, что он осуществляет только List.
4. ArrayList лучше хранить и доступ к данным.

LinkedList -

1. LinkedList внутренне использует дважды связанный список для хранения элементов.

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

3. LinkedList класс может выступать в качестве списка и стоять в очереди, поскольку он реализует List и интерфейсы Deque.

4. LinkedList лучше для управления данными.

Answer 32

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

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