Структуры хранения — непрерывная и ссылочная

Несмотря на широкое разнообразие структур данных, имеется всего два альтернативных принципа их внутренней организации:

q непрерывная организация — размещение всех элементов структуры по порядку в одной непрерывной области памяти, в результате чего соседние элементы занимают соседние ячейки памяти (такой способ иногда называют векторной организацией, чтобы как-то отделить это понятие от понятия массива, хотя по сути это одно и то же);

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

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

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

Рис. 1.2. Элемент связной структуры

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

память под каждый элемент захватывается динамически, при этом ссылки на связанные элементы реализуются с помощью указателей;

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

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

Сравним различные структуры хранения.

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

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

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

Сравнение показывает, что ни одна из структур хранения не является идеальной, поэтому довольно часто используются структуры данных, в которых комбинируются различные структуры хранения. Например, в известной библиотеке шаблонов STL (Standard Template Library) для языка С++ некоторые типы реализованы как связные списки, элементами которых являются массивы (допустим, тип vector). Не менее часто используются массивы, элементами которых являются списки. Например, такой способ используется в одном из вариантов реализации хеш-таблиц, которые будут рассмотрены в главе 5.