c++ - 如何用数组实现紧凑型链表？

Question

下面是习题CLRS 10.3-4 我正在尝试解决

It is often desirable to keep all elements of a doubly linked list compact in storage,using, for example, the first m index locations in the multiple-array representation.(This is the case in a paged, virtual-memory computing environment.) Explain how to implement the procedures ALLOCATE OBJECT and FREE OBJECT so that the representation is compact. Assume that there are no pointers to elements of the linked list outside the list itself. (Hint: Use the array implementation of a stack.)

这是我目前的解决方案

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 方法后，所有“引用”都会变得无效。