Динамические структуры данных: списки Введение
    В предыдущих обзорах мы рассматривали программирование, связанное с обработкой только статических данных. Статическими величинами называются такие, память под которые выделяется во время компиляции и сохраняется в течение всей работы программы.
    В языках программирования (Pascal, C, др.) существует и другой способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины будем называть динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью).
    Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера.
    Работа с динамическими величинами связана с использованием еще одного типа данных - ссылочного типа. Величины, имеющие ссылочный тип, называют указателями.
    Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти.
    Адрес величины - это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом.
    Далее будем более подробно обсуждать указатели и действия с ними в языке Pascal, примеры будем приводить на Pascal и C.
    Величина ссылочного типа (указатель) описывается в разделе описания переменных следующим образом:
     Var : ^;
    Вот примеры описания указателей:
     Type Mas1 = Array[1..100] Of Integer;
     Var P1 : ^Integer;
     P2 : ^String;
     Pm : ^Mas1;
    Здесь P1 - указатель на динамическую величину целого типа; P2 - указатель на динамическую величину строкового типа; Pm - указатель на динамический массив, тип которого задан в разделе Type.
    Сами динамические величины не требуют описания в программе, поскольку во время компиляции память под них не выделяется. Во время компиляции память выделяется только под статические величины. Указатели - это статические величины, поэтому они требуют описания.
    Каким же образом происходит выделение памяти под динамическую величину? Память под динамическую величину, связанную с указателем, выделяется в результате выполнения стандартной процедуры NEW. Формат обращения к этой процедуре:
     NEW();
    Считается, что после выполнения этого оператора создана динамическая величина, имя которой имеет следующий вид:
     := ^
    Пусть в программе, в которой имеется приведенное выше описание, присутствуют следующие операторы:
     NEW(P1); NEW(P2); NEW(Pm);
    После их выполнения в динамической памяти оказывается выделенным место под три величины (две скалярные и один массив), которые имеют идентификаторы:
     P1^, P2^, Pm^
    Например, обозначение P1^ можно расшифровать так: динамическая переменная, на которую ссылается указатель P1.
    Дальнейшая работа с динамическими переменными происходит точно так же, как со статическими переменными соответствующих типов. ............