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

200

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

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

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

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

Onorio Catenacci
источник
1
Связанный - Когда использовать LinkedList <> поверх ArrayList <>? - это Java, но массивы (ArrayList) и связанные списки предположительно имеют одинаковую производительность на любом языке.
Бернхард Баркер
1
@rootTraveller На самом деле этот вопрос будет дубликатом этого вопроса, потому что мой вопрос был опубликован первым.
Онорио Катеначчи

Ответы:

147
  • В связанном списке легче хранить данные разных размеров. Массив предполагает, что каждый элемент имеет одинаковый размер.
  • Как вы упомянули, для связного списка легче расти органически. Размер массива должен быть известен заранее или создан заново, когда он должен расти.
  • Перестановка связанного списка - это просто вопрос изменения того, что указывает на что. Перестановка массива более сложна и / или занимает больше памяти.
  • Пока все ваши итерации происходят в контексте «foreach», вы не теряете никакой производительности в итерации.
Райан
источник
19
Как по-разному относятся к предметам разных размеров? Связанный список либо использует фиксированную структуру со следующим полем (требуется фиксированный размер), либо сохраняет указатель на данные в автомобиле (переменный размер в порядке). Оба подхода так же просты с вектором. То же самое для перетасовки.
Брайан
32
Я бы сказал, что перетасовка массива менее сложна.
Хью Аллен
23
Этот ответ неверен и вводит в заблуждение. (за исключением необходимости знать размер массива при его объявлении)
Роберт Полсон
35
Не будет ли повторение связанного списка медленнее из-за локальности данных?
Фирас Ассаад
6
@Rick, векторы обычно перераспределяют пространство, которое им требуется, так что им не нужно выделять новое пространство каждый раз, когда размер увеличивается. В результате векторы обычно занимают меньше памяти, а не больше, чем связанные списки.
Уинстон Эверт
179

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

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

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

Алекс Миллер
источник
9
Алекс - это интересное соображение, которое никогда бы не пришло мне в голову. Очень хороший ответ Я бы проголосовал за тебя дважды, если бы мог. :-)
Онорио Катеначчи
5
Взгляните на списки пропусков (в частности ConcurrentSkipListMap в Java 6), чтобы получить хорошее представление о том, куда можно пойти с этим. CSLM - это отсортированная параллельная карта с отличной производительностью. Гораздо лучше, чем синхронизированный TreeMap. tech.puredanger.com/2007/10/03/skip-lists
Алекс Миллер
... за исключением того, что ConcurrentSkipListMapили ConcurrentSkipListMapне являются списками, даже если «Список» встречается где-то в их имени. Оба требуют ключи, которые будут отсортированы и уникальны. Если вам нужна List, то есть структура данных, которая позволяет дублировать элементы в произвольном порядке, это не подходит, и вам придется приложить большие усилия, чтобы сделать структуру данных похожей LinkedListна обновляемую вещь. Если вам нужна только параллельная очередь или очередь, ну да, есть даже существующие примеры, но параллельные List... Я не уверен, что это даже возможно.
Хольгер
128

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

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

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

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

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

Йонас Клемминг
источник
4
Это идеальный ответ. Кратко описывает преимущества и недостатки обоих.
Рик
спасибо)) очень просто, но я не видел его в вики)
Тимур Файзрахманов
58

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

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

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

Брайан
источник
4
Еще одно очень интересное соображение, которое я бы никогда не придумал. Спасибо.
Онорио Катеначчи
Как я могу сделать это в Python?
сверхобмена
29

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

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

Том Риттер
источник
2
Совершенно верно, что вставка и удаление происходят после поиска в большинстве случаев, поэтому необходимо учитывать сумму временных сложностей.
М. А. Хоссейн Тону
28

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

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

колокольчик-рапунцель
источник
2
Только если вы просто добавляете один список в другой. Если вы на самом деле объединяете два отсортированных списка, тогда потребуется больше, чем O (1).
Herms
3
@Herms, но вы можете объединить два отсортированных связанных списка, не выделяя лишней памяти, просто обходя оба списка и устанавливая указатели соответствующим образом. Слияние двух массивов обычно требует как минимум один дополнительный массив.
Пол Томблин
1
Да, объединение списков более эффективно использует память, но это не совсем то, что я комментировал. Сказать, что объединение связанных списков - это O (1), вводит в заблуждение без разъяснения дела.
Herms
Объединение списков @Herms не более эффективно для использования памяти, чем объединение массивов в любой разумной модели данных.
Алексей Аверченко
2
Алексей Аверченко: Объединение двух списков или даже сортировка слиянием двух отсортированных списков может быть осуществлена ​​на месте с помощью памяти O (1). Конкатенация двух массивов требует O (n) памяти обязательно, если только массивы уже не смежны в памяти. Я думаю, что цель, к которой вы стремитесь, это то, где список из n элементов и массив из n элементов занимают O (n) памяти, но коэффициент выше для связанных списков.
Рэмпион
17

Часто недооцениваемый аргумент для 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>
mhaller
источник
17

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

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

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

  1. доступ

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

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

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

    • Элементы могут быть вставлены и удалены в связанных списках на неопределенный срок.
    • Вставка / удаление значений в массивах очень дороги. Это требует перераспределения памяти.
Сульман
источник
У вас есть 2 номер 2 и 2 номер 3 :)
Hengameh
Мы можем объявить пустой массив и затем продолжать добавлять данные в соответствии с требованиями. Как это сделать еще фиксированный размер?
HebleV
11

Две вещи:

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

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

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

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

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

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

bradtgmurray
источник
Как я сказал кому-то выше, я просто пытался связать вопрос так, как он был задан мне. Во всяком случае, я бы никогда не использовал массив (или связанный список свёрток) в C ++ - я бы использовал STL-версии обоих.
Онорио Катеначчи
10

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

Rik
источник
2
По общему признанию хороший пост, но не связанный в связанном списке против обсуждения массива.
Роберт Полсон
2
Я бы предположил, что значительная часть статьи Эрика актуальна, поскольку в ней обсуждаются как недостатки массивов, так и преимущества списков, независимо от реализации списка.
Беван
8

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

Firas Assaad
источник
7

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

itsmatt
источник
7

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

Джеймс Керран
источник
4
Вы могли бы иметь очередь на основе массива без слишком большой работы, которая была бы все еще быстрой / эффективной. Вам просто нужно отслеживать, какой индекс был "головой", а какой - "хвостом". Это работает довольно хорошо, если вам нужна очередь фиксированного размера (например, буфер клавиатуры в ядре).
Herms
3
И называется «циклический буфер», если вы хотите посмотреть его в своем любимом алгоритме.
Стив Джессоп
7

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

Васил
источник
6
Векторы (= в основном массивы) тоже могут это делать, и амортизированная стоимость для них обычно меньше, чем для списков из-за проблем с местностью ссылок.
Конрад Рудольф
7

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

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

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

Джоэл Коухорн
источник
2
Er..umm .. std :: vector является массивом, а не связанным списком. Стандартный связанный список, ну, в общем, std :: list.
Джеймс Керран
1
да, но я думаю, что вектор ближе к тому, что требует опера - динамическая замена массива.
Джоэл Коухорн
@ Джоэл, я просто пытался связать вопрос с тем, что мне задал этот парень, который пытается изучать C ++. Я бы не стал кодировать свой собственный связанный список, но он так меня и спросил. :-)
Онорио Катеначчи
В средах с ограниченным объемом памяти (микроконтроллеры), для которых существуют пользовательские компиляторы, реализован не весь язык (например, контейнеры в C ++). Возможно, вам придется кодировать свой собственный связанный список. nongnu.org/avr-libc/user-manual/FAQ.html#faq_cplusplus
Minh Tran
6

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

Стив Бейкер
источник
6

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

tloach
источник
6

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

  1. Выделение памяти массива иногда происходит из-за фрагментации памяти.
  2. Кэширование лучше в массивах, поскольку все элементы выделяются непрерывным пространством памяти.
  3. Кодирование является более сложным, чем массивы.
  4. Нет ограничений по размеру в связанном списке, в отличие от массивов
  5. Вставка / удаление быстрее в связанном списке и доступ быстрее в массивах.
  6. Связанный список лучше с точки зрения многопоточности.
AKS
источник
-1: Все это нужно обосновать, а не просто перечислить.
Джон Сондерс
Каждый пункт уже был объяснен в ответах выше. Будучи опоздавшим, у меня не было другого выбора, кроме как перечислять. Кстати, что бы вы хотели объяснить?
AKS
Если они уже были объяснены, то почему вы отвечаете?
Джон Сондерс
2
Так что это даст вам обобщенный взгляд на обсуждение. И мне нравятся такие ответы, чтобы мне не приходилось читать одно и то же объяснение снова и снова. И я сделал это для тех людей, у которых такой же стиль мышления, как и у меня. У разных людей разные стили. Ничего нового.
AKS
3

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

debayan
источник
3

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

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

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

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

DenNukem
источник
Не могли бы вы уточнить это: «возможно создать структуру данных, которая дает массивоподобный обычный порядок доступа, где чтение и запись в худшем случае являются логарифмическими».
Hengameh
1
В Википедии есть кое-что в разделе «Динамический массив / врианты». Это не совсем то, что я имел в виду ... Представьте себе структуру типа b + tree со страницами, но без ключей, вместо этого каждая промежуточная страница запоминает, сколько элементов имеется на каждой из подстраниц, тогда как листовые страницы просто содержат элементы в небольшом массиве. При вставке элемента в листовую страницу вам нужно переместить ~ половину страницы, чтобы освободить место, затем подняться и обновить счетчик элементов на всех страницах предков. При поиске элемента #N просто добавьте количество элементов на подчиненной странице, пока не пересечете N, а затем
спускайтесь
3

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

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

pranjal
источник
3

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

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

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 ()

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

Фара Назифа
источник
3

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

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

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

iec2011007
источник
3

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

2 - размер связанного списка может увеличиваться или уменьшаться во время выполнения, поэтому нет потерь памяти. В случае с массивом происходит много потерь памяти, например, если мы объявляем массив размером 10 и храним в нем только 6 элементов, пространство из 4 элементов теряется. В связанном списке такой проблемы нет, так как память выделяется только при необходимости.

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

Айман Амджад
источник
2

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

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

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

user15453
источник
2
Указатели занимают много места? На самом деле, нет. Если вы храните связанный список логических значений, то, конечно же, процентное соотношение указателей занимает много места. Но если вы храните сложные объекты (как правило, так), то указатели, вероятно, будут незначительными.
Herms
забыл улыбнуться :) Но сказал "не может" не "есть".
user15453
1

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

ирам аршад
источник
1

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

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

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

SetSlapShot
источник
1

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

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

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

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

Хуан Карлос
источник
1

В то время как многие из вас касались основных нативов / массивов связанных списков и массивов, большинство сравнений показывают, насколько одно лучше / хуже другого. Например. Вы можете сделать произвольный доступ в массиве, но не возможно в связанном списке и других. Однако это предполагает, что списки ссылок и массив будут применены в аналогичном приложении. Однако правильным ответом должно быть то, каким образом список ссылок будет предпочтительнее массива и наоборот в конкретном развертывании приложения. Предположим, вы хотите реализовать приложение-словарь, что бы вы использовали? Массив: ммм, он позволил бы легко получить доступ через бинарный поиск и другой алгоритм поиска ... но давайте подумаем, как список ссылок может быть лучше ... Скажем, вы хотите искать "Blob" в словаре. Имеет ли смысл иметь список ссылок A-> B-> C-> D ---->

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

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

Викальп Вир
источник