Массив против связанного списка
https://stackoverflow.com/questions/166884
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Зачем кому-то использовать связанный список вместо массива?
Кодирование связанного списка, без сомнения, требует немного больше усилий, чем использование массива, и можно задаться вопросом, что оправдывает дополнительные усилия.
Я думаю, что вставка новых элементов в связанный список тривиальна, но в массиве это большая рутина.Есть ли другие преимущества использования связанного списка для хранения набора данных по сравнению с хранением его в массиве?
Этот вопрос не является дубликатом этот вопрос потому что другой вопрос касается конкретного класса Java, а этот вопрос касается общих структур данных.
Решение
- В связанном списке проще хранить данные разного размера.Массив предполагает, что все элементы имеют одинаковый размер.
- Как вы упомянули, связанному списку легче органично расти.Размер массива необходимо знать заранее или создавать заново, когда ему необходимо вырасти.
- Перетасовка связанного списка — это всего лишь вопрос изменения того, что на что указывает.Перетасовка массива более сложна и/или требует больше памяти.
- Пока все ваши итерации выполняются в контексте foreach, вы не теряете производительности при итерации.
Другие советы
Еще одна веская причина в том, что связанные списки прекрасно подходят для эффективных многопоточных реализаций. Причина этого заключается в том, что изменения имеют тенденцию быть локальными - затрагивать только один или два указателя для вставки и удаления в локализованной части структуры данных. Таким образом, вы можете иметь много потоков, работающих над одним и тем же связанным списком. Более того, можно создавать версии без блокировок с использованием операций типа CAS и вообще избегать тяжелых блокировок.
С помощью связанного списка итераторы также могут просматривать список во время внесения изменений. В оптимистическом случае, когда модификации не сталкиваются, итераторы могут продолжаться без конфликтов.
В случае массива любое изменение, которое изменяет размер массива, вероятно, потребует блокировки большой части массива, и на самом деле редко, когда это делается без глобальной блокировки для всего массива, поэтому изменения становятся остановкой мировые дела.
В Википедии есть очень хороший раздел о различиях.
Связанные списки имеют несколько преимуществ над массивами. Элементы могут быть вставлены в связанные списки на неопределенный срок, в то время как массив в конечном итоге либо заполнит или нужно изменить размер, дорогой операция, которая может даже не быть возможно, если память фрагментирована. Точно так же массив из которого многие элементы удаляются могут стать расточительно пустой или должен быть сделан меньше.
С другой стороны, массивы допускают случайное доступ, в то время как связанные списки разрешают только последовательный доступ к элементам. Односвязные списки, по сути, могут только быть пройденным в одном направлении. это делает связанные списки непригодными для приложения, где полезно смотреть быстро увеличить элемент по его индексу, такой как heapsort. Последовательный доступ на массивы также быстрее, чем на связанных списки на многих машинах из-за местности кэш-памяти ссылок и данных. связанный списки почти не получают никакой пользы от кеш.
Еще один недостаток связанных списков это дополнительное хранилище, необходимое для ссылки, которые часто делают их непрактично для списков небольших данных такие элементы, как символы или логические ценности. Это также может быть медленным, и с на & # 239; ве распределитель, расточительный выделить память отдельно для каждого новый элемент, проблема вообще решено с помощью пулов памяти.
Добавлю еще - списки могут выступать в качестве чисто функциональный структуры данных.
Например, у вас могут быть совершенно разные списки, имеющие один и тот же конечный раздел.
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 операции могут выполняться свободно без необходимости копирования исходных данных — это очень важная функция, когда вы рассматриваете данные как неизменяемые.
Помимо того, что вставка в середину списка более проста, ее также легче удалить из середины связанного списка, чем из массива.
Но, честно говоря, я никогда не использовал связанный список. Всякий раз, когда мне требовалась быстрая вставка и удаление, мне также требовался быстрый поиск, поэтому я переходил на HashSet или словарь.
Объединение двух связанных списков (особенно двух двусвязных списков) происходит намного быстрее, чем объединение двух массивов (при условии, что объединение разрушительно). Первый принимает O (1), второй принимает O (n).
РЕДАКТИРОВАТЬ . Чтобы уточнить, я имел в виду " слияние " здесь в неупорядоченном смысле, а не в виде слияния. Возможно & Quot; объединение & Quot; было бы лучшим словом.
Широко недооцененный аргумент для 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 и поиск конкретных объектов превращаются в кошмарный клик по 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>
Прежде всего, в C++ работать со связанными списками не должно быть намного сложнее, чем с массивом.Вы можете использовать станд::список или список указателей повышения для связанных списков.Ключевые проблемы связанных списков по сравнению с массивами — это дополнительное пространство, необходимое для указателей, и ужасный произвольный доступ.Вам следует использовать связанный список, если вы
- вам не нужен произвольный доступ к данным
- вы будете добавлять/удалять элементы, особенно в середине списка
Для меня это так,
Доступ
- Связанные списки разрешить только последовательный доступ к элементам.Таким образом, алгоритмическая сложность порядка O(n)
- Массивы разрешить произвольный доступ к его элементам, и, следовательно, сложность порядка O (1)
Хранилище
- Связанные списки требуется дополнительное хранилище для ссылок.Это делает их непрактичными для списков небольших элементов данных, таких как символы или логические значения.
- Массивы не требуется дополнительное хранилище для указания следующего элемента данных.Доступ к каждому элементу можно получить через индексы.
Размер
- Размер Связанные списки динамичны по своей природе.
- Размер множество ограничивается декларацией.
Вставка/удаление
- Элементы можно вставлять и удалять в связанные списки на неопределенный срок.
- Вставка/удаление значений в массивы очень дорогие.Это требует перераспределения памяти.
Две вещи:
Кодирование связанного списка, без сомнения, немного сложнее, чем использование массива, и он задумался над тем, что оправдало бы дополнительные усилия.
Никогда не кодируйте связанный список при использовании C ++. Просто используйте STL. То, насколько сложно это реализовать, никогда не должно быть причиной для выбора одной структуры данных над другой, потому что большинство из них уже реализовано.
Что касается реальных различий между массивом и связанным списком, для меня очень важно то, как вы планируете использовать структуру. Я буду использовать термин вектор, так как это термин для массива с изменяемым размером в C ++.
Индексирование в связанный список происходит медленно, потому что вам нужно пройти по списку, чтобы добраться до заданного индекса, в то время как вектор непрерывен в памяти, и вы можете попасть туда с помощью математики указателей.
Добавить в конец или начало связанного списка легко, поскольку вам нужно обновить только одну ссылку, где в векторе вам может потребоваться изменить размер и скопировать содержимое.
Удалить элемент из списка очень просто, поскольку вам просто нужно разорвать пару ссылок и затем снова соединить их. Удаление элемента из вектора может происходить быстрее или медленнее, в зависимости от того, заботитесь ли вы о порядке. Поменять местами последний элемент поверх элемента, который вы хотите удалить, быстрее, а сместить все после него медленнее, но сохранить порядок.
Эрик Липперт недавно получил сообщение. По одной из причин массивы следует использовать консервативно.
Быстрая вставка и удаление действительно лучшие аргументы для связанных списков. Если ваша структура растет динамически и доступ к любому элементу в постоянном времени не требуется (например, к динамическим стекам и очередям), хорошим выбором будут связанные списки.
Вот один из них: удаление элементов происходит быстрее.
Linked-list особенно полезны, когда коллекция постоянно растет & amp; сокращается. Например, трудно представить себе попытку реализовать Очередь (добавить в конец, удалить спереди) с помощью массива - вы бы потратили все свое время на смещение вещей вниз. С другой стороны, это тривиально со связанным списком.
Помимо добавления и удаления из середины списка, мне больше нравятся связанные списки, потому что они могут динамически увеличиваться и уменьшаться.
Никто больше не кодирует свой собственный связанный список. Это было бы глупо. Предположение, что использование связанного списка требует больше кода, просто неверно.
В наши дни создание связного списка - это просто упражнение для студентов, чтобы они могли понять концепцию. Вместо этого каждый использует предварительно составленный список. В C ++, основываясь на описании в нашем вопросе, это, вероятно, означало бы вектор stl (#include <vector>).
Следовательно, выбор связанного списка и массива целиком предполагает взвешивание различных характеристик каждой структуры в соответствии с потребностями вашего приложения. Преодоление дополнительного бремени программирования должно иметь нулевое влияние на решение.
Это действительно вопрос эффективности, накладные расходы на вставку, удаление или перемещение (где вы не просто меняете) элементов внутри связанного списка минимальны, то есть сама операция - это O (1), стихи O (n) для массив. Это может иметь существенное значение, если вы интенсивно работаете со списком данных. Вы выбрали свои типы данных в зависимости от того, как вы будете работать с ними, и выберите наиболее эффективный для используемого вами алгоритма.
Массивы имеют смысл, где точное число элементов будет известно, и где поиск по индексу имеет смысл. Например, если бы я хотел сохранить точное состояние моего видеовыхода в данный момент без сжатия, я бы, вероятно, использовал массив размером [1024] [768]. Это даст мне именно то, что мне нужно, и список будет намного, намного медленнее, чтобы получить значение данного пикселя. В местах, где массив не имеет смысла, как правило, существуют лучшие типы данных, чем список, для эффективной обработки данных.
Массив и связанный список:
<Ол>, поскольку массивы статичны по своей природе, поэтому все операции как распределение памяти происходит во время компиляции только. Таким образом, процессор должен прикладывать меньше усилий во время выполнения.
Предположим, у вас есть упорядоченный набор, который вы также хотите изменить, добавив и удалив элементы. Кроме того, вам нужна возможность сохранить ссылку на элемент таким образом, чтобы позже вы могли получить предыдущий или следующий элемент. Например, список дел или набор абзацев в книге.
Во-первых, мы должны отметить, что если вы хотите сохранить ссылки на объекты вне самого набора, вы, скорее всего, в конечном итоге будете хранить указатели в массиве, а не сами объекты. В противном случае вы не сможете вставить в массив - если объекты встроены в массив, они будут перемещаться во время вставки, и любые указатели на них станут недействительными. То же самое верно для индексов массива.
Ваша первая проблема, как вы сами отметили, заключается в том, что список, связанный со вставкой, позволяет вставлять в O (1), но для массива обычно требуется O (n). Эта проблема может быть частично преодолена - возможно создать структуру данных, которая дает массивоподобный обычный порядок доступа, где чтение и запись в худшем случае являются логарифмическими.
Ваша вторая и более серьезная проблема заключается в том, что заданным элементом для нахождения следующего элемента является O (n). Если набор не был изменен, вы могли бы сохранить индекс элемента в качестве ссылки вместо указателя, таким образом делая find-next операцией O (1), но, как и все, что у вас есть, это указатель на сам объект и никак определить его текущий индекс в массиве, кроме как путем сканирования всего " array " ;. Это непреодолимая проблема для массивов - даже если вы можете оптимизировать вставки, вы ничего не можете сделать для оптимизации операции поиска следующего типа.
В массиве вы имеете право доступа к любому элементу за 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 действия
Что, если длина массива равна миллиону?Эффективен ли массив?Ответ - нет!:)
То же самое касается и удаления!В связанном списке мы можем просто использовать указатель и обнулить элемент и следующий в классе объекта!Но для массива нам нужно выполнить сдвигLeft().
Надеюсь, это поможет!:)
Связанные списки требуют больших затрат на обслуживание, чем массивы, они также требуют дополнительной памяти, все эти точки согласованы. Но есть несколько вещей, которые массив не может сделать. Во многих случаях предположим, что вам нужен массив длиной 10 ^ 9, вы не можете его получить, потому что там должна быть одна непрерывная ячейка памяти. Связанный список может быть спасителем здесь.
Предположим, что вы хотите хранить несколько вещей с данными, тогда их можно легко расширить в связанном списке.
Контейнеры STL обычно имеют реализацию связанного списка за сценой.
Единственная причина для использования связанного списка - простота вставки элемента (также удаления).
Разочарование может заключаться в том, что указатели занимают много места.
А с этим кодированием сложнее: Обычно вам не нужен список связанных кодов (или только один раз), они включены в STL и это не так сложно, если вам все еще придется это делать.
Я также думаю, что список ссылок лучше, чем массивы. потому что мы делаем обход в списке ссылок, а не в массивах
В зависимости от вашего языка, могут быть рассмотрены некоторые из этих недостатков и преимуществ:
Язык программирования C . При использовании связанного списка (как правило, с помощью указателей структуры) особое внимание следует уделить тому, чтобы не допустить утечки памяти. Как упоминалось ранее, связанные списки легко перетасовать, потому что все, что делали, меняли указатели, но не забудем ли мы все освободить?
Java : Java имеет автоматический сборщик мусора, поэтому утечка памяти не будет проблемой, но скрытый от программиста высокого уровня - детали реализации того, что представляет собой связанный список. Такие методы, как удаление узла из середины списка, являются более сложными процедурами, чем ожидают некоторые пользователи языка.
Почему связанный список над массивом? Ну, как некоторые уже сказали, большая скорость вставки и удаления.
Но, может быть, нам не нужно жить с ограничениями обоих и одновременно получать лучшее от обоих ... а?
Для удаления массива вы можете использовать байт 'Deleted', чтобы представить факт удаления строки, поэтому перестановка массива больше не требуется. Чтобы облегчить бремя вставок или быстро меняющихся данных, используйте для этого связанный список. Затем, обращаясь к ним, попросите свою логику сначала найти один, а затем другой. Таким образом, использование их в комбинации дает вам лучшее из обоих.
Если у вас действительно большой массив, вы можете объединить его с другим, гораздо меньшим массивом или связанным списком, где меньший содержит 20, 50, 100 последних использованных элементов. Если нужного вам нет в более коротком связанном списке или массиве, вы переходите к большому массиву. Если он найден там, вы можете добавить его в меньший связанный список / массив, исходя из предположения, что «последние использованные вещи наиболее вероятны для повторного использования» (и, да, возможно, удаляют наименее недавно использованный элемент из списка). Это верно во многих случаях и решило проблему, которую мне пришлось решать в модуле проверки разрешений безопасности .ASP, с легкостью, элегантностью и впечатляющей скоростью.
Несмотря на то, что многие из вас затронули основные элементы adv./dis связанного списка и массива, большинство сравнений показывают, насколько одно лучше / хуже другого. Например. Вы можете сделать произвольный доступ в массиве, но не возможно в связанном списке и других. Однако это предполагает, что списки ссылок и массив будут применены в аналогичном приложении. Однако правильный ответ должен заключаться в том, каким образом список ссылок будет предпочтительнее массива и наоборот при развертывании конкретного приложения. Предположим, вы хотите реализовать приложение-словарь, что бы вы использовали? Массив: ммм, это позволит легко извлекать данные с помощью бинарного поиска и других алгоритмов поиска ... но давайте подумаем, как может быть лучше список ссылок ... Скажем, вы хотите искать & Quot; Blob & Quot; в словаре. Имеет ли смысл иметь список ссылок A - & G -; B - & Gt; C - & Gt; D ---- & Gt; Z, а затем каждый элемент списка, также указывающий на массив или другой список всех слов, начинающихся с этой буквы ..
A -> B -> C -> ...Z
| | |
| | [Cat, Cave]
| [Banana, Blob]
[Adam, Apple]
Теперь вышеперечисленный подход лучше или плоский набор [Адам, Apple, Банан, Blob, Cat, Cave]? Будет ли это возможно с массивом? Таким образом, главное преимущество списка ссылок заключается в том, что вы можете иметь элемент, указывающий не только на следующий элемент, но также на какой-либо другой список ссылок / массив / кучу / или любую другую область памяти. Массив - это одна плоская непрерывная память, разделенная на блоки размером элемента, который он собирается сохранить. С другой стороны, список ссылок - это куски неконтактных блоков памяти (могут быть любого размера и могут хранить что угодно), указывающие на каждую иначе, как вы хотите. Точно так же скажем, что вы делаете USB-накопитель. Теперь вы хотите, чтобы файлы были сохранены в виде любого массива или в виде списка ссылок? Я думаю, вы поняли, на что я указываю:)
Почему кто-то хочет использовать связанный список над массивом?
Это только одна причина - если вам нужна структура данных связанного списка и используемый вами язык программирования не поддерживает указатели.
