小编Ary*_*ana的帖子

我正在寻找一个存储元素数组并支持这些操作的数据结构:

1. 访问给定索引处的元素
2. 在给定索引处添加或删除元素(从而转移以下元素)

数组在O(1)中执行第一个操作,但第二个操作采用O(n),而链接列表执行相反的操作.是否存在中间数据结构？比方说,可以在O(lg n)或O(n ^ epsilon)"最坏情况"时间内进行两种操作？

请注意,我不是要求平衡的二叉搜索树.每次添加/删除新元素时,键(索引)都会被更改和移位.例如,删除最小元素会将所有其他元素的索引减少1.