arrays - 具有 O(1) 插入和删除的双向链表的紧凑多数组实现

Question

我对 CLRS(Cormen 算法介绍 3 版)中练习 (10.3-4) 的解决方案感到困惑。我的实现似乎能够在 O(1) 时间内执行删除 + 取消分配，而我在网上找到的两个解决方案都需要 O(n) 时间来执行这些操作，我想知道谁是正确的。

这是练习的文本:

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

通过“多数组表示”，他们指的是使用下一个、上一个和键数组的链表的实现，索引充当存储在数组中的指针而不是对象指向下一个和上一个的成员。该特定实现在 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) 时间。我自己的实现只是简单地获取数组中的最后一个“有效”元素并使用它来填充创建的任何间隙，这仅在删除元素时发生。这保持了“紧凑性”属性。当然，相应的 prev 和 next “指针”也会更新，这是 O(1) 时间。此外，来自 Sec 的普通实现。本书中的 10.3 不需要紧凑性，它有一个名为“free”的变量，它指向第二个链表的开头，该链表具有所有“无效”元素，可以被覆盖。对于我的实现，因为任何插入都必须尽早完成，例如无效的数组槽，我只是让我的变量“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) 的“向下移动”解决方案在满足问题规范的意义上也是正确的，但显然从运行时的角度来看，您的方法更可取。