Рубрики

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

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

Ключевые различия между массивом и связанным списком
1. Массив — это структура данных, которая содержит коллекцию элементов данных аналогичного типа, тогда как Связанный список рассматривается как не примитивная структура данных и содержит коллекцию неупорядоченных связанных элементов, известных как узлы.
2. В массиве элементы принадлежат индексам, т. Е. Если вы хотите попасть в четвертый элемент, вы должны написать имя переменной с ее индексом или местоположением в квадратных скобках.
3. В связанном списке, тем не менее, вы должны начать с головы и пройти весь путь до четвертого элемента.
4. Доступ к элементу в массиве быстрый, в то время как связанный список занимает линейное время, поэтому он немного медленнее.
5. Операции, такие как вставка и удаление в массивах, занимают много времени. С другой стороны, выполнение этих операций в связанных списках происходит быстро.
6. Массивы имеют фиксированный размер. В отличие от этого, связанные списки являются динамическими и гибкими и могут расширяться и сокращаться в своем размере.
7. В массиве память выделяется во время компиляции, в то время как в связанном списке она выделяется во время выполнения или выполнения.
9. Элементы хранятся последовательно в массивах, тогда как они случайным образом хранятся в связанных списках.
10. Потребность в памяти меньше из-за фактических данных, хранящихся в индексе в массиве. В отличие от этого, требуется больше памяти в связанных списках из-за хранения дополнительных элементов следующего и предыдущего ссылок.
11. Кроме того, использование памяти в массиве неэффективно. И наоборот, использование памяти эффективно в связанном списке.

Ниже приведены пункты в пользу связанных списков.

(1) Размер массивов фиксирован: поэтому мы должны знать верхний предел количества элементов заранее. Кроме того, как правило, выделенная память равна верхнему пределу независимо от использования, и при практическом использовании верхний предел редко достигается.

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

Например, предположим, что мы поддерживаем отсортированный список идентификаторов в массиве id [].

id [] = [1000, 1010, 1050, 2000, 2040,… ..].

И если мы хотим вставить новый идентификатор 1005, то для поддержания отсортированного порядка нам нужно переместить все элементы после 1000 (исключая 1000).

Удаление также дорого с массивами до тех пор, пока не будут использованы некоторые специальные методы. Например, чтобы удалить 1010 в id [], все после 1010 должно быть перемещено.

Таким образом, связанный список обеспечивает следующие два преимущества над массивами
1) динамический размер
2) Простота вставки / удаления

Связанные списки имеют следующие недостатки:
1) Произвольный доступ не допускается. Мы должны получить доступ к элементам последовательно, начиная с первого узла. Поэтому мы не можем выполнить бинарный поиск со связанными списками.
2) Требуется дополнительное место в памяти для указателя с каждым элементом списка.
3) Массивы имеют лучшую локальность кэша, что может существенно повлиять на производительность.

Ссылки:
http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

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

Рекомендуемые посты:

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

0.00 (0%) 0 votes