Функциональные и свободные списки
Достоинства и недостатки связных списков
Перечислим преимущества связных списков.
1) Важным преимуществом связных список является независимость быстродействия операций включения и удаления от количества элементов. В подразделе 6.5, где обсуждаются особенности операций вставки и удаления в массиве, показано, что эти операции требуют выполнения сдвига, т. е. физического перемещения в памяти группы элементов. Аналогичные операции в связных списках вызывают простое изменение значений адресов, хранящихся в самих элементах.
2) На основе концепции связности элементов можно создавать бесконечное множество различных структур данных, что позволяет формировать в памяти ЭВМ разнообразные информационные модели для различных предметных областей.
3) Благодаря использованию динамических связных списков экономится оперативная память ЭВМ. В связном списке в любой текущий момент времени существует ровно столько элементов, сколько требуется для решаемой задачи.
4) Динамические связные структуры создаются, хранятся и обрабатываются в самой большой по объему области оперативной памяти - куче (heap). Это дает возможность с помощью таких структур решать серьезные задачи, требующие много памяти.
Основным недостатком связных списков является то, что затраты времени на получение доступа к их элементам зависят от количества элементов. Для получения доступа к некоторому i-ому элементу необходимо выполнить переходы по ссылкам вплоть до искомого элемента. Чем больше элементов в списке, тем больше переходов придется совершить.
Второй недостаток связан с произвольным физическим размещением элементов списка в куче. Поскольку в общем случае вставки и удаления элементов выполняются в непредсказуемом порядке, узлы списка будут разбросаны по различным страницам виртуальной памяти. Это влияет на эффективность выполнения операций.
Наконец, в элементах связных списков приходится размещать структурные ссылки, число которых зависит от степени связности К. Для К‑связной структуры затраты памяти на ссылки составляют К*SizeOf(Poiner) байт на каждый элемент.
6.7.1 Общая характеристика функционального и свободного списка
Важнейшие операции над связными списками - включение и исключение элементов. Список, уже сформированный к текущему моменту времени и хранящий в содержательных полях своих элементов полезную информацию, называют функциональным списком. Свободным списком называют такой дополнительный список элементов (или один элемент), который служит источником памяти при формировании функциональных списков. Каждый элемент свободного списка имеет такой же формат полей, как и элемент функционального списка, но содержимое информационной его части не определено.
Свободный список формируется из элементов, исключаемых из функционального списка. Операцию исключения можно изобразить с помощью рисунка 6.14, на котором показана операция исключения третьего узла. Если на удаляемом элементе не сохранить указатель (как на рисунке 6.14 6), то его слот перестанет быть адресуемым, то есть в куче появится неадресуемое пространство - «дыра». С целью экономии памяти исключенный элемент следует включить в список, сформированный из других исключенных элементов одинакового формата, то есть в свободный список. В дальнейшем прежде чем добавить в функциональный список новый элемент, следует проверить соответствующий свободный список, и, если в свободном списке есть элементы, то взять элемент из него, а не создавать в памяти новый элемент.
Рисунок 6.14 - Исключение в связном списке
В Delphi распределением и освобождением памяти занимается очень сложный диспетчер кучи. Диспетчер кучи содержит код, который позволяет манипулировать кусками памяти. Диспетчер кучи Delphi использует свободный список освобожденных блоков памяти различного размера. Некоторые массивы в Delphi используют цепочку удаленных элементов, которая является ни чем иным, как другим названием свободного списка. Многие базы данных поддерживают скрытый свободный список удаленных записей, которые можно использовать повторно.
6.7.2 Методы формирования свободного списка
Каждый элемент многосвязной структуры может входить в несколько односвязных списков. Исключение элемента из одного такого списка еще не означает, что его можно поместить в свободный список элементов. Проблема возврата элементов многосвязной списковой структуры в свободный список может реализоваться разными методами.
Метод счетчиков сводится к тому, что после операции исключения элемента из того или иного списка делается проверка, остался ли этот элемент хотя бы в каком-либо одном функциональном списке, и в случае отрицательного ответа элемент присоединяется к свободному списку (т. е. удаляется из связного функционального списка). Метод предполагает наличие в каждом элементе многосвязной структуры специального поля счетчика. Содержимое этого поля увеличивается на единицу при установлении каждой новой ссылки, направленной к элементу, и уменьшается на единицу при исчезновении такой ссылки. Как только счетчик станет равен нулю, элемент помещается в свободный список.
В методе сборки мусора (garbage collection) не требуется при разрыве каждой связки делать проверку элемента и возвращать освободившийся элемент в свободный список. Освободившийся элемент как бы «повисает» до тех пор, пока не будет исчерпан свободный список. И только после этого запускается процедура «сборки мусора», которая отыскивает все освободившиеся к тому времени элементы и включает их в свободный список. Для реализации метода сборки мусора в каждом элементе многосвязной структуры резервируется минимально возможное поле памяти для маркера, который используется на этапе поиска освободившегося элемента. С этой целью процедура маркирует все доступные элементы многосвязной структуры, т. е. такие элементы, к которым направлен хотя бы один указатель. Затем просматривается вся область памяти, отведенная для элементов, и в свободный список включаются все элементы, в которых отсутствует маркер.
Диспетчер кучи Delphi создает список свободных областей (free space list) по мере выполнения процедур «уничтожения» динамических переменных, таких, например, как Dispose.