具有O（1）插入和删除的双链表的紧凑多数组实现

Question

我对CLRS（Cormen Intro to Algorithms 3ed）练习（10.3-4）的解决方案感到困惑。我的实现似乎能够在O（1）时间内执行删除+解除分配，而我在网上找到的两个解决方案都需要O（n）时间进行这些操作，我想知道谁是正确的。

这是练习的内容：

通常希望使用例如多阵列表示中的前m个索引位置来保持双链表的所有元素在存储中紧凑。 （在分页的虚拟内存计算环境中就是这种情况。）解释如何实现ALLOCATE OBJECT和FREE OBJECT过程，以便表示紧凑。假设没有指向列表本身之外的链表的元素的指针。 （提示：使用堆栈的数组实现。）

通过“多数组表示”，它们指的是使用next，prev和key数组的链表的实现，其中索引充当存储在数组中的指针，而不是具有指向next和prev的成员的对象。在CLRS第10.3节的文本中讨论了这个特定的实现，而这个特定的练习似乎只是强加了元素是“紧凑”的附加条件，或者，据我所知，它被打包到数组的开头，没有任何间隙或孔与“非活动”元素。

有a previous thread on the same exercise here，但我无法弄清楚我想从那个线程中知道什么。

我在网上找到的两个解决方案是first one here和second one here, on page 6 of the pdf。两种解决方案都说，为了填补空缺，将间隙减少一个后的所有元素移位，花费O（n）时间。我自己的实现只是简单地获取数组中的最后一个“valid”元素，并使用它来填充创建的任何间隙，这只有在删除元素时才会发生。这保持了“紧凑”属性。当然，更新适当的prev和next“指针”，这是O（1）时间。另外，Sec的普通实现。书中的10.3（不需要紧凑性）有一个名为“free”的变量，它指向第二个链表的开头，它具有所有“无效”元素，可以写入。对于我的实现，因为任何插入必须尽早完成，例如，无效的数组插槽，我只是让我的变量“自由”更像是堆栈中的变量“top”。这似乎是显而易见的，我不确定为什么这两个解决方案都要求O（n）“在间隙之后移动一切”方法。那么是哪一个呢？

这是我的C实现。据我所知，一切正常，需要O（1）时间。

typedef struct {
    int *key, *prev, *next, head, free, size;
} List;

const int nil = -1;

List *new_list(size_t size){
    List *l = malloc(sizeof(List));
    l->key = malloc(size*sizeof(int));
    l->prev = malloc(size*sizeof(int));
    l->next = malloc(size*sizeof(int));
    l->head = nil;
    l->free = 0;
    l->size = size;
    return l;
}

void destroy_list(List *l){
    free(l->key);
    free(l->prev);
    free(l->next);
    free(l);
}

int allocate_object(List *l){
    if(l->free == l->size){
        printf("list overflow\n");
        exit(1);
    }
    int i = l->free;
    l->free++;
    return i;
}

void insert(List *l, int k){
    int i = allocate_object(l);
    l->key[i] = k;
    l->next[i] = l->head;
    if(l->head != nil){
        l->prev[l->head] = i;
    }
    l->prev[i] = nil;
    l->head = i;
}

void free_object(List *l, int i){
    if(i != l->free-1){
        l->next[i] = l->next[l->free-1];
        l->prev[i] = l->prev[l->free-1];
        l->key[i] = l->key[l->free-1];
        if(l->head == l->free-1){
            l->head = i;
        }else{
            l->next[l->prev[l->free-1]] = i;
        }
        if(l->next[l->free-1] != nil){
            l->prev[l->next[l->free-1]] = i;
        }
    }
    l->free--;
}

void delete(List *l, int i){
    if(l->prev[i] != nil){
        l->next[l->prev[i]] = l->next[i];
    }else{
        l->head = l->next[i];
    }
    if(l->next[i] != nil){
        l->prev[l->next[i]] = l->prev[i];
    }
    free_object(l, i);
}

Answer 1

你的方法是正确的。

O（n）“shift-everything-down”解决方案在满足问题规范的意义上也是正确的，但从运行时的角度来看，显然您的方法更为可取。