Стек свободного пространства

До сих пор мы не заботились о том, куда деваются освобождаемые узлы списков, перекладывая это на алгоритмы работы с "кучей". Это было возможно, потому, что наши списки располагались в оперативной памяти и в нашем распоряжении имелись операторы new и delete. Существуют ситуации, когда программа сама должна заботиться об "утилизации" осво­бож­даемых узлов списков. Такая ситуация возникнет, если отказаться от кучи как поставщика узлов или список находится на внешнем носителе. Просто бросать освободившиеся узлы было бы слишком расточительно. Мы будем помещать их в стек свободного пространства, организованный как линейный односвязный

Рис 20. Вставка узла в список.

Текст функции приведен ниже.

NODE *InsertNode(NODE *p, NODE *s){

// Вставка узла вслед за p

// s – указатель на вершину стека свободного пространства

// возвращает указатель на новый узел

NODE *X;

X=s;

s=s->Next;

X->Next=p->Next;

p->Next=X;