data-structures - 使用静态链表的数据结构有什么好处

Question

在本题中，静态链表定义如下：（c++代码）

template<typename T> struct Node{
    T elem;
    int next;//yes, int, which points to the index of the next element in the array.
};
Node static_linked_list [SOME_SIZE];
//some initialization code omitted.

所以在这种链表中，它是静态的，因为它的大小是在数组初始化期间分配的。链接是通过字段 实现的int next，它指向下一个元素的索引。

与基于指针（或引用）的链表相比，这种数据结构有什么优势？它的应用是什么？据我所知，静态的有范围生命周期，并且可以在实现malloc. 但它的int next内存消耗似乎并不比指针少。

标签： data-structureslinked-list

Answer 1

我不确定这个特定结构的用途，但这种不寻常的技术确实提供了在使用一个上限和固定的预分配内存块时表现得像一个链表的能力，除了更新之外不需要管理它根据需要在元素中索引。（请注意，当然索引字段不必“指向”下一个数字索引，它可以指向任何索引，因此“列表”不需要按语义顺序存储。）

“删除”一个项目比一个简单的数组更快（这需要移动后面的元素）。添加项目比较棘手，显然受整个元素数组大小的限制，但可以通过一些旁观的簿记来加快速度。我不确定在什么情况下您会决定在不同类型的列表上需要这种特定的数据结构。我的猜测是，在可预测性为王的情况下，您会受到相当谨慎的内存限制：想想游戏机、嵌入式设备、驱动程序/操作系统层等。