Как реализовать компактный связанный список с массивом?

Вот вопрос упражнений CLRS 10.3-4 Я пытаюсь решить

Часто желательно, чтобы все элементы двусвязного списка были компактными в хранилище,
используя, например, первые m позиций индекса в представлении с несколькими массивами.
(Это имеет место в выгружаемой вычислительной среде виртуальной памяти.) Объясните, как реализовать процедуры ALLOCATE OBJECT и FREE OBJECT, чтобы представление было компактным. Предположим, что нет никаких указателей на элементы связанного списка за пределами самого списка. (Подсказка: используйте реализацию массива стека.)

Вот мой солн до сих пор

int free;
int allocate()
{
if(free == n+1)
return 0;
int tmp = free;
free = next[free];
return tmp;
}
int deallocate(int pos)
{

for(;pos[next]!=free;pos[next])
{
next[pos] = next[next[pos]];
prev[pos] = prev[next[pos]];
key[pos] = key[next[pos]];
}
int tmp = free;
free = pos;
next[free] = tmp;
}

Теперь проблема в том, что если это так, нам не нужен связанный список. Если удаление O (n), мы можем реализовать его, используя обычный массив. Во-вторых, я тоже не использовал массивную реализацию стека. Так в чем же подвох? Как мне начать?

1

Решение

Вам не нужно сокращать список сразу. Просто оставьте дыру и свяжите эту дыру с вашим бесплатным списком. Как только вы распределили память, она ваша. Допустим, размер вашей страницы составляет 1 КБ. Ваш начальный выделенный размер списка будет равен 1 КБ, даже если список пуст. Теперь вы можете добавлять и удалять элементы очень эффективно.

Затем введите другой метод pack ваш список, то есть удалить все дыры. Имейте в виду, что после вызова метода pack все ссылки становятся недействительными.

-1

Другие решения

Других решений пока нет …