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