Построение и использование списков в динамической памяти.

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

GetMem(Size: Integer; out P: Pointer); - выделение памяти;

FreeMem(P: Pointer); - освобождение памяти

Часто при работе с динамической памятью используются цепочки, очереди и списки. Они обеспечивают гораздо большую гибкость чем массивы, так как у последених элементы связаны жесткой связью, упорядочены по номерам. Цепочка – это структура из звеньев, где звено – это структура содержащая поле для указания на объект и поля длz указания на другие звенья. Цепочки бывают однонаправленные и двухнаправленные. В однонаправленной цепочке каждый элемент указывает только на следующий за ним и движение по цепочке возможно только в одном направлении, в двунаправленной Цепочке – в звеньях храняться указатели на следующий и предыдущий элемент и движение возможнов обоих направлениях.

Общая структура звеньев может выглядит так:

Однонаправленный список:

Pchain = ^Tchain;

Tchain = record

Element: Telement;

Next: Pchain; End;

Двухнаправленный список:

Pchain = ^Tchain;

Tchain = record

Element: Telement;

Next: Pchain;

Prev: Pchain; End;

Здесь Pchain – указатель (ссылочный тип) на звено цепочки, а поле элемент является объектом, цепочка которых организуется. Для доступа к элементам цепочки необходимо иметь хотя бы указатель на первый элемент или на последний.

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

При этом цепочка, изображенная на первом рисунке с указателем на первый элемент называется стеком (LIFO – last input first output) – так как такая организация, реализует алгоритм, когда последний размещенный элемент, извелекается первым. Если использовать еще указатель на последний элемент, то можно организовать очередь, FIFO – first input first output, когда первый размещенный элемент будет первым извлечен. Алгоритм и организация полностью зависят от желаний программиста.

Часто возникает необходимость организовать доступ к произвольным элементам цепочки. При этом необходимо знание не только следующего звена, но и предыдущего для перемещения в двух направлениях. Такие цепочки называются списками. Их организация в памяти приведена на рисунке выше.

Основными функциями для работы являются помещение и извлечение из списка очередного элемента. Рассмотрим общий алгоритм этих функций напримере стека:

Если надо добавить элемент он добавляется впереди первого элемента, при этом указатель на первый элемент переключается на новый элемент, а указателю на следующий элемент у нового элемента присваивается значение старого первого элемента. При удалении – удаляется первый элемент, а указатель первого элемента переключается на указатель на следующий элемент удаленного элемента.

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

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