Разница между массивами и связанными списками

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

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

На рисунке 1 показан фрагмент кода, который обычно используется для объявления и присвоения значений массиву. На рисунке 2 показано, как массив будет выглядеть в памяти.

Вышеприведенный код определяет массив, который может хранить 5 целых чисел, и к ним обращаются с помощью индексов от 0 до 4. Одним из важных свойств массива является то, что весь массив выделяется как один блок памяти, и каждый элемент получает свое собственное пространство в массиве. Как только массив определен, его размер фиксирован. Поэтому, если вы не уверены в размере массива во время компиляции, вам придется определить достаточно большой массив, чтобы быть в безопасности. Но в большинстве случаев мы собираемся использовать меньшее количество элементов, чем выделено. Таким образом, значительный объем памяти фактически теряется. С другой стороны, если «достаточно большой массив» на самом деле недостаточно велик, программа завершится сбоем.

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

Рисунок 3: Элемент связанного списка

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

Хотя массивы и связанные списки похожи в том смысле, что оба они используются для хранения коллекции элементов, они имеют различия из-за стратегий, которые они используют для выделения памяти его элементам. Массивы выделяют память всем его элементам как один блок, и размер массива должен быть определен во время выполнения. Это сделает массивы неэффективными в ситуациях, когда вы не знаете размер массива во время компиляции. Поскольку связанный список выделяет память своим элементам отдельно, он будет гораздо эффективнее в ситуациях, когда вы не знаете размер списка во время компиляции. Объявление и доступ к элементам в связанном списке не будет простым по сравнению с прямым доступом к элементам в массиве с использованием его индексов..