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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 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 могут происходить свободно, без копирования исходных данных – очень важные функции, когда вы обрабатываете данные как неизменные.

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

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

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

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

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

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

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

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

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

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

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

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

  1. доступ

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

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

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

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

Две вещи:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В массиве у вас есть привилегия доступа к любому элементу в O (1) времени. Таким образом, он подходит для операций, таких как двоичный поиск Quick sort и т. Д. Связанный список, с другой стороны, подходит для удаления вставки как его в 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 шага

Что, если длина массива составляет один миллион? Является ли массив эффективным? Ответ – нет! 🙂

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

Надеюсь, это поможет! 🙂

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

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

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

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

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

ArrayList –

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

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

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

LinkedList –

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Давайте будем гением компьютера.