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

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

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

Answer 5

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

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

Answer 6

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

РЕДАКТИРОВАТЬ: Чтобы уточнить, я имел в виду «слияния» здесь в неупорядоченном смысле, а не в сортировке слияния. Возможно, «объединение» было бы лучшим словом.

Answer 7

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

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

Answer 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 и поиск конкретных объектов превращаются в кошмарный клик 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 9

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

1. Доступ

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

2. Хранение

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

3. размер

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

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

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

Answer 10

Две вещи:

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

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

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

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

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

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