Почему кто-то хочет использовать связанный список над массивом?
Кодирование связанного списка, без сомнения, немного сложнее, чем использование массива, и можно задаться вопросом, что оправдывает дополнительные усилия.
Я думаю, что вставка новых элементов тривиальна в связанном списке, но это основная работа в массиве. Есть ли другие преимущества использования связанного списка для хранения набора данных по сравнению с хранением его в массиве?
Этот вопрос не является дубликатом этого вопроса, потому что другой вопрос касается конкретно конкретного класса Java, в то время как этот вопрос касается общих структур данных.
arrays
data-structures
linked-list
language-agnostic
Onorio Catenacci
источник
источник
Ответы:
источник
Другая веская причина в том, что связанные списки прекрасно подходят для эффективных многопоточных реализаций. Причина этого заключается в том, что изменения, как правило, носят локальный характер - затрагивают только один или два указателя для вставки и удаления в локализованной части структуры данных. Таким образом, вы можете иметь много потоков, работающих над одним и тем же связанным списком. Более того, можно создавать версии без блокировок с использованием операций типа CAS и вообще избегать тяжелых блокировок.
Со связанным списком итераторы также могут просматривать список во время внесения изменений. В оптимистическом случае, когда модификации не сталкиваются, итераторы могут продолжаться без конфликтов.
В случае массива любое изменение, которое изменяет размер массива, вероятно, потребует блокировки большой части массива, и на самом деле, редко, когда это делается без глобальной блокировки всего массива, поэтому модификации становятся остановкой мировых дел.
источник
ConcurrentSkipListMap
илиConcurrentSkipListMap
не являются списками, даже если «Список» встречается где-то в их имени. Оба требуют ключи, которые будут отсортированы и уникальны. Если вам нужнаList
, то есть структура данных, которая позволяет дублировать элементы в произвольном порядке, это не подходит, и вам придется приложить большие усилия, чтобы сделать структуру данных похожейLinkedList
на обновляемую вещь. Если вам нужна только параллельная очередь или очередь, ну да, есть даже существующие примеры, но параллельныеList
... Я не уверен, что это даже возможно.В Википедии есть очень хороший раздел о различиях.
http://en.wikipedia.org/wiki/Linked_list
источник
Я добавлю еще один - списки могут действовать как чисто функциональные структур данных.
Например, вы можете иметь совершенно разные списки, разделяющие один и тот же конечный раздел
то есть:
без необходимости копировать данные того , на который указывает
a
вb
иc
.Вот почему они так популярны в функциональных языках, которые используют неизменяемые переменные -
prepend
иtail
операции могут выполняться свободно без необходимости копировать исходные данные - очень важные функции, когда вы рассматриваете данные как неизменные.источник
Помимо того, что вставка в середину списка более проста, ее также легче удалить из середины связанного списка, чем из массива.
Но, честно говоря, я никогда не использовал связанный список. Всякий раз, когда мне нужно было быстро вставлять и удалять, мне также требовался быстрый поиск, поэтому я переходил на HashSet или словарь.
источник
Объединение двух связанных списков (особенно двух дважды связанных списков) происходит намного быстрее, чем объединение двух массивов (при условии, что объединение разрушительно). Первый принимает O (1), второй принимает O (n).
РЕДАКТИРОВАТЬ: Чтобы уточнить, я имел в виду «слияния» здесь в неупорядоченном смысле, а не в виде слияния. Возможно, «объединение» было бы лучшим словом.
источник
Часто недооцениваемый аргумент для ArrayList и против LinkedList заключается в том, что LinkedLists неудобны при отладке. . Время, затрачиваемое разработчиками обслуживания на понимание программы, например, на поиск ошибок, увеличивается, и IMHO иногда не оправдывает наносекунды в повышении производительности или байты в потреблении памяти в корпоративных приложениях. Иногда (ну, конечно, это зависит от типа приложений), лучше потратить несколько байтов, но есть приложение, которое легче обслуживать или легче понять.
Например, в среде Java и с использованием отладчика Eclipse отладка ArrayList покажет очень простую для понимания структуру:
С другой стороны, наблюдение за содержимым LinkedList и поиск конкретных объектов становится кошмаром кликов по Expand-The-Tree, не говоря уже о когнитивных издержках, необходимых для фильтрации внутренних компонентов LinkedList:
источник
Прежде всего, в C ++ связанных списков не должно быть гораздо больше проблем, чем с массивом. Вы можете использовать std :: list или список повышенных указателей для связанных списков. Ключевыми проблемами связанных списков и массивов являются дополнительное пространство, необходимое для указателей, и ужасный произвольный доступ. Вы должны использовать связанный список, если вы
источник
Для меня это так,
доступ
Место хранения
Размер
Вставка / удаление
источник
Две вещи:
Никогда не кодируйте связанный список при использовании C ++. Просто используйте STL. То, насколько сложно это реализовать, никогда не должно быть причиной выбора одной структуры данных над другой, поскольку большинство из них уже реализованы.
Что касается реальных различий между массивом и связанным списком, то для меня очень важно то, как вы планируете использовать структуру. Я буду использовать термин вектор, так как это термин для массива с изменяемым размером в C ++.
Индексирование в связанный список происходит медленно, потому что вам нужно пройти по списку, чтобы добраться до заданного индекса, в то время как вектор непрерывен в памяти, и вы можете получить его с помощью математики указателя.
Добавить в конец или начало связанного списка легко, поскольку вам нужно обновить только одну ссылку, где в векторе вам может потребоваться изменить размер и скопировать содержимое.
Удалить элемент из списка очень просто, так как вам просто нужно разорвать пару ссылок и затем снова соединить их вместе. Удаление элемента из вектора может быть быстрее или медленнее, в зависимости от того, заботитесь ли вы о порядке. Поменять местами последний элемент поверх элемента, который вы хотите удалить, быстрее, а сместить все после него медленнее, но сохранить порядок.
источник
Эрик Липперт недавно получил пост по одной из причин, по которой массивы следует использовать консервативно.
источник
Быстрая вставка и удаление действительно лучшие аргументы для связанных списков. Если ваша структура растет динамически и доступ к любому элементу в постоянном времени не требуется (например, к динамическим стекам и очередям), хорошим выбором будут связанные списки.
источник
Вот быстрый: удаление предметов происходит быстрее.
источник
Связанные списки особенно полезны, когда коллекция постоянно растет и сокращается. Например, трудно представить себе попытку реализовать Очередь (добавить в конец, удалить спереди) с использованием массива - вы бы потратили все свое время на смещение вещей вниз. С другой стороны, это тривиально со связанным списком.
источник
Помимо добавления и удаления из середины списка, мне больше нравятся связанные списки, потому что они могут динамически увеличиваться и уменьшаться.
источник
Никто никогда не кодирует свой собственный связанный список больше. Это было бы глупо. Предположение, что использование связанного списка требует больше кода, просто неверно.
В наши дни создание связного списка - это просто упражнение для студентов, чтобы они могли понять концепцию. Вместо этого каждый использует предварительно составленный список. В C ++, основываясь на описании в нашем вопросе, это, вероятно, означало бы вектор stl (
#include <vector>
).Следовательно, выбор связанного списка и массива целиком заключается в взвешивании различных характеристик каждой структуры в соответствии с потребностями вашего приложения. Преодоление дополнительного бремени программирования должно иметь нулевое влияние на решение.
источник
Это действительно вопрос эффективности, затраты на вставку, удаление или перемещение (где вы не просто меняете) элементов внутри связанного списка минимальны, то есть сама операция - O (1), стихи O (n) для массива. Это может иметь существенное значение, если вы интенсивно работаете со списком данных. Вы выбрали свои типы данных в зависимости от того, как вы будете работать с ними, и выберите наиболее эффективный для используемого вами алгоритма.
источник
Массивы имеют смысл там, где будет известно точное количество элементов, и где имеет смысл поиск по индексу. Например, если бы я хотел сохранить точное состояние моего видеовыхода в данный момент без сжатия, я бы, вероятно, использовал массив размером [1024] [768]. Это даст мне именно то, что мне нужно, и список будет намного, намного медленнее, чтобы получить значение данного пикселя. В местах, где массив не имеет смысла, как правило, существуют лучшие типы данных, чем список, для эффективной обработки данных.
источник
Массивы против связанного списка:
источник
поскольку массивы статичны по своей природе, поэтому все операции, такие как выделение памяти, выполняются только во время компиляции. Таким образом, процессор должен прикладывать меньше усилий во время работы.
источник
Предположим, у вас есть упорядоченный набор, который вы также хотите изменить, добавив и удалив элементы. Кроме того, вам нужна возможность сохранить ссылку на элемент таким образом, чтобы позже вы могли получить предыдущий или следующий элемент. Например, список дел или набор абзацев в книге.
Во-первых, мы должны отметить, что если вы хотите сохранить ссылки на объекты вне самого набора, вы, скорее всего, в конечном итоге будете хранить указатели в массиве, а не сами объекты. В противном случае вы не сможете вставить в массив - если объекты встроены в массив, они будут перемещаться во время вставки, и любые указатели на них станут недействительными. То же самое верно для индексов массива.
Ваша первая проблема, как вы сами отметили, заключается в том, что связанный с вставкой список позволяет вставлять в O (1), но массив обычно требует O (n). Эта проблема может быть частично преодолена - возможно создать структуру данных, которая предоставляет массивоподобный обычный порядок доступа, где чтение и запись в худшем случае являются логарифмическими.
Ваша вторая и более серьезная проблема заключается в том, что заданным элементом для нахождения следующего элемента является O (n). Если набор не был изменен, вы могли бы сохранить индекс элемента в качестве ссылки вместо указателя, тем самым делая операцию find-next операцией O (1), но, как и все, что у вас есть, это указатель на сам объект и никак определить его текущий индекс в массиве, кроме как путем сканирования всего «массива». Это непреодолимая проблема для массивов - даже если вы можете оптимизировать вставки, вы ничего не можете сделать, чтобы оптимизировать операцию поиска следующего типа.
источник
В массиве у вас есть привилегия доступа к любому элементу за время O (1). Таким образом, он подходит для таких операций, как Бинарный поиск, Быстрая сортировка и т. Д. Связанный список, с другой стороны, подходит для удаления вставки, как и в O (1) раз. Оба имеют как преимущества, так и недостатки, и предпочтение одного перед другим сводится к тому, что вы хотите реализовать.
- Большой вопрос, можем ли мы иметь гибрид обоих. Что-то вроде того, что Python и Perl реализуют в виде списков.
источник
Связанный список
Его предпочтительнее, когда дело доходит до вставки! В основном, это то, что он имеет дело с указателем
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 шага
Что, если длина массива равна миллиону? Является ли массив эффективным? Ответ - нет! :)
То же самое касается удаления! В связанном списке мы можем просто использовать указатель и обнулить элемент и следующий в классе объекта! Но для массива нам нужно выполнить shiftLeft ()
Надеюсь, это поможет! :)
источник
Связанные списки - это больше затрат на поддержку, чем массив, они также требуют дополнительной памяти, все эти точки согласованы. Но есть несколько вещей, которые массив не может сделать. Во многих случаях предположим, что вам нужен массив длиной 10 ^ 9, вы не можете его получить, потому что там должна быть одна непрерывная ячейка памяти. Связанный список может быть спасителем здесь.
Предположим, что вы хотите хранить несколько вещей с данными, тогда они могут быть легко расширены в связанном списке.
Контейнеры STL обычно имеют реализацию связанного списка за сценой.
источник
1. Связанный список - это динамическая структура данных, поэтому он может увеличиваться и уменьшаться во время выполнения, выделяя и освобождая память. Таким образом, нет необходимости указывать начальный размер связанного списка. Вставка и удаление узлов действительно проще.
2 - размер связанного списка может увеличиваться или уменьшаться во время выполнения, поэтому нет потерь памяти. В случае с массивом происходит много потерь памяти, например, если мы объявляем массив размером 10 и храним в нем только 6 элементов, пространство из 4 элементов теряется. В связанном списке такой проблемы нет, так как память выделяется только при необходимости.
3- Структуры данных, такие как стек и очереди, могут быть легко реализованы с использованием связанного списка.
источник
Единственная причина для использования связанного списка заключается в том, что вставить элемент легко (удаление также).
Разочарование может быть в том, что указатели занимают много места.
А с этим кодированием сложнее: обычно вам не нужен список связанных кодов (или только один раз), они включены в STL, и это не так сложно, если вам все равно придется это делать.
источник
Я также думаю, что список ссылок лучше, чем массивы. потому что мы делаем обход в списке ссылок, но не в массивах
источник
В зависимости от вашего языка, некоторые из этих недостатков и преимуществ могут быть рассмотрены:
Язык программирования C : при использовании связанного списка (обычно с помощью указателей структуры) особое внимание следует уделить тому, чтобы у вас не было утечки памяти. Как упоминалось ранее, связанные списки легко перетасовать, потому что все, что делали, это изменение указателей, но будем ли мы помнить, чтобы освободить все?
Java : Java имеет автоматический сборщик мусора, поэтому утечка памяти не будет проблемой, но скрытый от программиста высокого уровня - детали реализации того, что представляет собой связанный список. Такие методы, как удаление узла из середины списка, являются более сложными процедурами, чем ожидают некоторые пользователи языка.
источник
Почему связанный список над массивом? Ну, как некоторые уже сказали, большая скорость вставки и удаления.
Но, может быть, нам не нужно жить с ограничениями обоих и одновременно получать лучшее от обоих ... а?
Для удаления массива вы можете использовать байт 'Deleted', чтобы представить факт удаления строки, поэтому перестановка массива больше не требуется. Чтобы облегчить бремя вставок или быстро меняющихся данных, используйте для этого связанный список. Затем, обращаясь к ним, попросите свою логику сначала найти один, а затем другой. Таким образом, использование их в комбинации дает вам лучшее из обоих.
Если у вас действительно большой массив, вы можете объединить его с другим, гораздо меньшим массивом или связанным списком, где меньший содержит 20, 50, 100 последних использованных элементов. Если нужного вам нет в более коротком связанном списке или массиве, вы переходите к большому массиву. Если он найден там, вы можете добавить его в меньший связанный список / массив, исходя из предположения, что «последние использованные вещи наиболее вероятны для повторного использования» (и, да, возможно, удаляют наименее недавно использованный элемент из списка). Это верно во многих случаях и решило проблему, которую мне пришлось решать в модуле проверки разрешений безопасности .ASP, с легкостью, элегантностью и впечатляющей скоростью.
источник
В то время как многие из вас касались основных нативов / массивов связанных списков и массивов, большинство сравнений показывают, насколько одно лучше / хуже другого. Например. Вы можете сделать произвольный доступ в массиве, но не возможно в связанном списке и других. Однако это предполагает, что списки ссылок и массив будут применены в аналогичном приложении. Однако правильным ответом должно быть то, каким образом список ссылок будет предпочтительнее массива и наоборот в конкретном развертывании приложения. Предположим, вы хотите реализовать приложение-словарь, что бы вы использовали? Массив: ммм, он позволил бы легко получить доступ через бинарный поиск и другой алгоритм поиска ... но давайте подумаем, как список ссылок может быть лучше ... Скажем, вы хотите искать "Blob" в словаре. Имеет ли смысл иметь список ссылок A-> B-> C-> D ---->
Теперь вышеприведенный подход лучше или плоский набор [Адам, Apple, Банан, Blob, Cat, Cave]? Будет ли это возможно с массивом? Таким образом, главное преимущество списка ссылок состоит в том, что вы можете иметь элемент, указывающий не только на следующий элемент, но также на какой-либо другой список ссылок / массив / кучу / или любую другую область памяти. Массив - это единая плоская непрерывная память, разделенная на блоки размером элемента, который он будет хранить. С другой стороны, список ссылок - это куски не непрерывных блоков памяти (могут быть любого размера и могут хранить что угодно), указывающие на каждую иначе, как вы хотите. Точно так же предположим, что вы делаете USB-накопитель. Теперь вы хотите, чтобы файлы были сохранены в виде любого массива или в виде списка ссылок? Я думаю, вы поняли, на что я указываю :)
источник