用于快速索引查找的列表数据结构

Question

我需要在类似列表的数据结构中存储大量元素。附加要求是，应随时快速确定每个元素的索引。元素未排序，无法排序。

如果使用简单数组，则每次查询元素的索引时，我们都必须使用线性搜索。这是可行的，但是它是一个非常低效的解决方案。这是伪代码中的数据结构：

class IndexList1 {
  Array elements

  getIndex(e) {
    for (i = 0; i < elements.length; i++) {
      if (elements[i] == e) {
        return i
      }
    }
    return -1;
  }

  insertAt(e, i) {
    elements.insertAt(e, i)
  }

  removeFrom(i) {
    elements.removeFrom(i)
  }

}

更好的方法是在内部映射中或作为元素中的字段将元素映射到索引。这样，无需搜索即可确定元素的索引。这里的问题是在列表中间插入或删除元素之后，必须更新插入点之后的所有索引。对于频繁的插入和删除以及大量元素，这不是很有效。

用伪代码改进的数据结构如下：

class IndexList2 {
  Array elements
  Map elementIndexMap

  getIndex(e) {
    return elementIndexMap.get(e)
  }

  insertAt(e, i) {
    elements.insertAt(e, i)
    updateIndicesFrom(i)
  }

  removeFrom(i) {
    elementsIndexMap.delete(elements[i])
    elements.removeFrom(i)
    updateIndicesFrom(i)
  }

  updateIndicesFrom(i) {
    for (; i < elements.length; i++) {
      elementsIndexMap[elements[i]] = i
    }
  }

}

是否有针对大量元素的聪明的类似列表的数据结构，即使有很多插入和删除操作，它也可以有效地跟踪每个元素的索引？有效是指getIndex()的O（1），比insert()和remove()的O（n）好。

我需要在类似列表的数据结构中存储大量元素。附加要求是，应随时快速确定每个元素的索引。元素不是...

Answer 1

解决此问题的常用方法是使用父指针将项目放在某种平衡树（红黑树，B +树，跳过列表等）中，并使用其子树的大小。