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

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

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

Ответы

Ответ 1

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

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

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

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

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

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

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

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

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

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

  • Добавление нового элемента в конце последовательности: Использование массива может привести к следующей проблеме: массивы обычно имеют фиксированный размер, поэтому если у нас есть ситуация, что наш массив уже полностью заполнен (см. //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 -+

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

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

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

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

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

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

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

Ответ 4

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

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

  • По мере того, как положение среднего элемента и других элементов также легко доступно, мы можем легко выполнить BINARY SEARCH в массиве.

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

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

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

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

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

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

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

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

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

Ответ 5

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

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

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

Ответ 6

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

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