В чем преимущество связанного списка над массивом и наоборот?

Question

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

С уважением, Shoaib

Answer 1

Оба хранят последовательность элементов, но используют разные методы.

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

--------------------------------------------------------------------------------------
|  item 1  |  item 2  |  item 3  |  ...  ...  |  item x  | //here comes other stuff
--------------------------------------------------------------------------------------

Это означает, что элементы один за другим последовательно в памяти.

A ((вдвойне) связанный) list , с другой стороны, сохраняет элементы следующим образом: создает собственный «элемент списка» для каждого элемента; этот «элемент списка» содержит фактический элемент и указатель / ссылку / подсказку / и т. д. на следующий «элемент списка». Если он дважды связан, он также содержит указатель / ссылку / подсказку / и т. Д. На предыдущий «элемент списка»:

                                  ------------
------------        ----------    |  item 4  |
|  item 1  |        | item 2 |    |  next ---+----...
|  next ---+------->| next   |    ------------
------------        ---+------      ^
                       |            |
                       |            |
                       v            |
                       ----------   |
                       | item 3 |   |
                       | next --+---+
                       ----------

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

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

• Доступ к элементу по определенному индексу: Используя массив , мы просто вычисляем смещение для этого индекса и имеем элемент в индекс.

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

• Добавление нового элемента в конце последовательности: Использование массива это может привести к следующей проблеме: Массивы обычно имеют фиксированный размер, поэтому, если мы в ситуации, когда наш массив уже полностью заполнен (см. //here comes other stuff), мы, вероятно, не можем поместить новый элемент туда, потому что может уже быть что-то еще. Так что, возможно, нам нужно скопировать весь массив. Однако, если массив не заполнен, мы можем просто поместить туда элемент.

  Используя список , мы должны сгенерировать новый «элемент списка», поместить в него элемент и установить указатель next последнего в данный момент элемента на этот новый элемент списка. Обычно мы храним ссылку на последний элемент в данный момент, так что нам не нужно искать весь список, чтобы найти его. Таким образом, вставка нового элемента не представляет реальной проблемы со списками.

• Добавление нового элемента где-то посередине: Давайте сначала рассмотрим массивы : здесь мы можем попасть в следующую ситуацию: У нас есть массив с элементами от 1 до 1000

  1 | 2 | 3 | 4 | 5 | 6 | ... | 999 | 1000 | free | free

  Теперь мы хотим вставить 4.5 между 4 и 5: это означает, что мы должны переместить все элементов с 5 на 1000 на одну позицию вправо, чтобы освободить место для 4.5:

   1 | 2 | 3 | 4 | free | 5 | 6 | ... | 999 | 1000 | free
  
                    ||
                    vv
  
   1 | 2 | 3 | 4 | 4.5  | 5 | 6 | ... | 999 | 1000 | free
  

  Перемещение всех этих элементов - очень дорогая операция. Так что лучше не делай этого слишком часто.

  Теперь мы рассмотрим, как список может выполнить эту задачу: допустим, у нас есть следующий список:

   1 -> 2 -> 3 -> 4 -> 5 -> ... -> 999 -> 1000
  

  Опять же, мы хотим вставить 4.5 между 4 и 5. Это можно сделать очень легко: мы генерируем новый элемент списка и обновляем указатели / ссылки:

   1 -> 2 -> 3 -> 4        5 -> ... -> 999 -> 1000
                  |        ^
                  +-> 4.5 -+
  

  Мы просто создали новый элемент списка и сгенерировали своего рода «обход» для его вставки - очень дешево (если у нас есть указатель / ссылка на элемент списка, после которого будет добавлен новый элемент).

  * * 1087

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

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

Известные вещи:

• Решение проблемы фиксированного размера для массивов. Как упоминалось ранее, (необработанные) массивы обычно имеют фиксированный размер.Однако, в настоящее время эта проблема больше не имеет смысла, так как почти все языки программирования предоставляют механизмы для генерации массивов, которые растут (и, возможно, сокращаются) динамически - по мере необходимости.Это увеличение и сжатие может быть реализовано так, что у нас есть амортизируемая среда выполнения O (1) для вставки и удаления элементов (в конце массива) и такая, что программист не должен вызывать grow и shrink явно.

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

Answer 2

Массивы имеют фиксированный размер, но к ним более быстрый доступ: они расположены в одном месте, и местоположение каждого элемента известно (вы можете перейти к нужному элементу).

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

Это очень краткое объяснение: я бы посоветовал вам взять книгу о структурах данных и прочитать ее.Это основные понятия, которые вам необходимо полностью понять.

Answer 3

Поскольку вы пометили вопрос "структурами данных", я отвечу на это в этом контексте.

Массив имеет фиксированный размер, когда вы объявляете / создаете его, то есть вы не можете добавить к нему больше элементов.Таким образом, если у меня есть массив, скажем, из 5 элементов, вы можете делать с ним все, что захотите, но не можете добавлять к нему больше элементов.

Связанный список - это в основном способ представлениясписок, где вы можете иметь столько «предметов», сколько захотите.Он состоит из головы (первый элемент), хвоста (последний элемент) и элементов (называемых узлами) между списком.

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

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

Очевидно, это очень обобщенный ответ.Это должно дать вам представление о вашем классе.

Answer 4

Преимущества массива над связанным списком

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

2. Поскольку мы знаем, что положение среднего элемента и других элементов также легко доступны, мы можем легко выполнить БИНАРНЫЙ ПОИСК в массиве.

Недостатки массива по сравнению со связанным списком

1. Необходимо указать общее количество элементов или выделение памяти во время создания массива

2. Размер упомянутого массива нельзя увеличить в программе. Если количество введенных элементов превышает размер массива, происходит ARRAY OVERFLOW EXCEPTION.

Преимущества связанного списка над массивом

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

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

Недостатки связанного списка над массивом

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

2. Поскольку все узлы не имеют своего конкретного адреса, БИНАРНЫЙ ПОИСК не может быть выполнен.

Answer 5

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

Короче говоря, если производительность имеет значение даже в малейшей степени в вашей программе, вы никогда не должны использовать связанный список. Когда-либо. Этому нет оправдания. Они далеко за пределами "медленных", они катастрофически медленные, и ничто в них не может восполнить этот факт. Их использование похоже на преднамеренный саботаж вашей производительности, подобно вставке функции «wait ()» в ваш код без всякой причины.

Answer 6

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

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

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