寻求支持高效随机访问与指定索引增删的索引型数据结构

存在这类数据结构，它们通过分层、分块或树状结构设计，能在指定索引位置完成优于线性时间的增删和访问操作，完全匹配你描述的需求（无需元素按顺序存储，仅需通过索引定位元素）。

常见实现方案 #

• 块状链表：将链表拆分为固定大小的块，每个块内部用数组存储元素。访问索引时先定位对应块（时间复杂度O(√n)），再在块内直接访问（O(1)）；增删元素时，若块满则拆分、块空则合并，整体增删操作的平均时间复杂度为O(√n)，远优于线性时间。
• 带大小计数的平衡二叉树：比如红黑树、替罪羊树，给每个节点维护其子树的节点总数。通过子树大小可以快速计算出指定索引对应的节点，增删和索引访问的时间复杂度均为O(log n)。
• 无序跳表：跳表的多层索引结构原本用于有序场景，但可以适配无序需求——给每个元素绑定索引映射，通过跳表的快速定位能力，实现*O(log n)*时间的索引访问、增删操作。

针对你需求的示例说明 #

以块状链表为例，对应你给出的元素5,2,8,1,3,3：

• 结构可划分为两个块：[5,2,8]、[1,3,3]
• 访问DataStructure[2]：定位到第一个块（覆盖索引0-2），直接返回块内第三个元素8
• 执行del DataStructure[2]：从第一个块移除8，块变为[5,2]，后续块的索引范围自动调整，操作仅需块内常数时间，整体开销可控

这类结构无需依赖外部库即可自行实现，也有部分语言的第三方工具包提供了类似封装。

内容的提问来源于stack exchange，提问作者Gursimar Singh Miglani