与O(1)插入和删除的双链接列表的紧凑多阵列实现

Question

我对CLR中的练习（10.3-4）的解决方案感到困惑（算法3ED的Cormen介绍）。我的实施似乎能够在O（1）时间内执行删除 脱位分配，而我在网上发现的两个解决方案都需要这些操作的O（n）时间，我想知道谁是正确的。

这是练习的文字：

通常希望将双链接列表紧凑的所有元素保持在存储中，例如，例如多阵列表示中的第一个M索引位置。（在分页的虚拟内存计算环境中就是这种情况。）解释如何实现该过程分配对象和自由对象，以使表示形式紧凑。假设列表本身之外的链接列表的元素没有指针。（提示：使用堆栈的数组实现。）

通过"多阵列表示"，他们指的是使用Next，prev和key arrays 的链接列表的实现，索引充当数组中存储的指针，而不是带有对象成员指向下一个和上一条。在CLR的第10.3节的文本中讨论了该特定的实现，而这种特殊的练习似乎只是施加了使元素"紧凑"的添加条件，或者，据我所知，它被包装到阵列的开头，没有任何"无效"元素的空白或孔。

这里有一个先前的线程，但我无法从该线程中弄清楚我想知道什么。

我在网上找到的两个解决方案在这里是第一个，第二个解决方案在PDF的第6页。两种解决方案都说要在一个差距降低一个元素之后将所有元素移动以填补空白，以填补o（n）时间。相反，我自己的实现只是在数组中使用最后一个"有效"元素，然后使用它来填补创建的任何空白，仅在删除元素时才发生。这保持了"紧凑"属性。当然，适当的预序和下一个"指针"已更新，这是O（1）时间。此外，来自第二节的普通实施。10.3在不需要紧凑的书中，有一个名为"免费"的变量，该变量指向第二个链接列表的开始，该列表具有所有"非valid"元素，可以写入。对于我的实施，由于必须尽早完成任何插入，例如非valid阵列插槽，我只是让我的变量" 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 overflown");
        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）"换档 - 全能"解决方案也是正确的，因为它符合问题的规范，但是从运行时的角度来看，您的方法显然是可取的。