如何用数组实现紧凑的链表? [英] How to implement a compact linked list with array?

问题描述

这是锻炼问题 CLRS 10.3-4我正在尝试解决

Here is the question of exercise CLRS 10.3-4 I am trying to solve

通常希望将双向链表的所有元素紧凑地存储在存储区中， 例如，使用多数组表示形式中的前m个索引位置. (在分页的虚拟内存计算环境中就是这种情况.)说明如何实现过程ALLOCATE OBJECT和FREE OBJECT，以便表示形式紧凑.假定在列表本身之外没有指向链接列表元素的指针. (提示:使用堆栈的数组实现.)

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.)

到目前为止，这是我的烦恼

Here is my soln so far

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)，我们可以使用普通数组来实现.其次，我也没有使用堆栈的数组实现.那么渔获量在哪里?我应该如何开始?

Now , The problem is , If this is the case , We don't need linked list. If deletion is O(n) we can implement it using normal array. Secondly I have not used the array implementation of stack too . So where is the catch? How should I start?

推荐答案

您不必立即缩小列表.只需留下一个漏洞并将该漏洞链接到您的免费​​列表即可.分配内存后，它就归您所有.假设您的页面大小为1K.即使列表为空，您最初分配的列表大小也将为1K.现在，您可以非常有效地添加和删除项目.

You don't have to shrink the list right away. Simply leave a hole and link that hole to your free list. Once you've allocated the memory, it's yours. So let's say your page size is 1K. Your initial allocated list size would then be 1K, even if the list is empty. Now you can add and remove items very effectively.

然后为pack您的列表引入另一种方法，即删除所有孔.请记住，调用打包方法后，所有引用"都将变为无效.

Then introduce another method to pack your list, i.e. remove all holes. Keep in mind that after calling the pack-method, all 'references' become invalid.

这篇关于如何用数组实现紧凑的链表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！