是否有任何数据结构或算法可以有效地将元素插入数组的任意位置,如O(1)或O(log(n))复杂性?在C++中有一个链表数据结构,它可以以O(1)复杂度在iterator位置有效地插入一个元素,但是要使iterator达到这个位置,则需要O(n),这是非常昂贵的。那么,是否有任何数据结构可以支持这个函数void insert(int pos, int val),该函数在位置pos之前插入一个元素val,并且该函数的复杂性很小?
在这个问题中,静态链表的定义如下:(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实现的,该字段指向下一个
我经常被告知,使用OCaml中的Lazy模块,可以在诸如Haskell这样的惰性语言中做任何你能做的事情。为了测试这个声明,我正在尝试编写一个函数,将常规列表转换为ocaml中的静态双向链表。
type 'a dlist = Dnil | Dnode of 'a dlist * 'a * 'a dlist
对于这种类型,我可以手动创建几个静态双向链表:
let rec l1 = Dnode (Dnil,1,l2)
and l2 = Dnode (l1,2,l3)
and l3 = Dnode (l2,3,Dnil)
但是我想写一个'