如何用数组实现一个紧凑的链表

Question

这是我想解决的锻炼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)，我们可以使用普通数组来实现它。其次，我也没有使用堆栈的数组实现。那么问题在哪里呢?我该怎么开始呢?

Answer 1

您不必立即缩小列表。只需留下一个洞，并将该洞链接到您的空闲列表。一旦你分配了内存，它就是你的了。假设你的页面大小是1K。初始分配的列表大小将是1K，即使列表为空。现在您可以非常有效地添加和删除项。

然后将另一种方法引入pack您的列表，即删除所有孔。请记住，在调用pack-method之后，所有的"引用"都将失效。