Несколько дней назад я писал об односвязных списках и не мог перестать спрашивать себя… зачем они нужны? Почему мы беспокоимся об использовании связанных списков, когда мы могли бы легко использовать массив? Что ж, сегодня тот день, когда мы собираемся сесть, выпить чашечку кофе и поговорить о массивах и связных списках.
Массивы всемогущи, давайте придерживаться их.
Когда я думаю о хранении данных, я думаю о массивах. "Эй, приятель, что я хранил в позиции "x"?" И в мгновение ока приходит массив с ответом. Это лучшая мысль о массивах. К любому элементу массива можно получить доступ за постоянное время, и нет ничего более удивительного, когда нам нужно часто обращаться к определенным элементам.
Я бы сказал, что если бы у нас был список с постоянным количеством элементов, массив был бы отличным местом для хранения ваших данных. Когда мы имеем дело с массивами, очень важно помнить, что они индексируются. Если на то пошло, если мы хотим получить доступ к определенному элементу, по крайней мере, нам нужно знать его индекс, чтобы иметь возможность найти его в постоянное время.
Большим недостатком массивов является то, что для хранения всех данных им требуется один блок памяти. Представьте, что вы пошли в магазин за продуктами и вам нужно хранить все это в холодильнике. Вы не ждете, пока ваш холодильник опустеет, чтобы купить больше еды, поэтому мы знаем, что он уже забит некоторыми продуктами. Теперь представьте, что вам нужно хранить все ваши новые продукты в одном месте холодильника. Вероятно, вы не можете, хотя у вас может быть больше свободного места. Вот что происходит с массивами. У них неправильное использование пространства (памяти!).
Еще одна вещь, которая может вызвать много головной боли, это то, что если мы хотим добавить новый элемент в массив в определенной позиции, нам нужно будет сдвинуть все следующие элементы вправо (включая тот, который уже был в этой позиции) . Кроме того, если у нас недостаточно свободного места, нам нужно будет переместить все наши элементы в массив большего размера. Да, я только что сказал тебе, головные боли повсюду.
Хорошо, массивы не так уж хороши, тогда давайте использовать связанные списки.
Вам следует знать, что связанные списки были созданы как ответ на проблемы с массивами. Они пытаются справиться с теми операциями, где массив, возможно, не так эффективен. Структура связанных списков напоминает поезд с вагонами. Каждый вагон знает только, какой вагон следующий, а в случае двусвязных списков он также знает предыдущий. Эти вагоны называются узлами, и каждый из них может хранить некоторые данные.
Самым большим преимуществом связанных списков является гибкость, которую можно обеспечить. В то время как в массивах у вас есть фиксированный размер, связанные списки более динамичны. Они могут легко увеличиваться или уменьшаться. На самом деле существует множество алгоритмов, которые могут обеспечить постоянное время добавления или удаления элементов связанных списков. Такая гибкость хороша, например, когда у вас есть список учетных записей пользователей. Использование этой структуры данных может помочь вам легко удалять и создавать новые учетные записи.
Но не все персики и крем. Хотя такой список может обеспечить большую динамику, если мы хотим найти определенный элемент в списке, это может быть не так просто. Массивы могут обращаться к элементам за постоянное время, но связанные списки должны использовать некоторую итерацию. Кроме того, они, как правило, немного сложны в использовании, в отличие от массивов.
Если вы хотите лучше использовать пространство памяти, вам следует использовать связанные списки. Пространство памяти резервируется при необходимости и не обязательно должно находиться в одном блоке памяти. Возвращаясь к примеру с холодильником, связанные списки могут быть разбросаны по пространству, потому что каждый отдельный узел знает, где находится следующий.
Теперь я запутался, какой из них мне использовать?
Нет простого ответа. Теперь, когда вы знаете преимущества и недостатки, вы сможете определить, какой из них вам нужен. Не воспринимайте их как соперников. Что я рекомендую, так это то, что, когда вы испытываете стресс из-за ограничений массивов, используйте связанные списки. Но всегда рассматривайте массивы как первый вариант, потому что их гораздо проще использовать.
Дайте мне знать в комментариях, если это было полезно для вас. Знаете ли вы о каких-либо других преимуществах или недостатках? Когда бы вы их использовали? Ну вот и все на сегодня. Читать вас позже! :)
