Is it possible to implement a dictionary with efficient access according to insertion order?

Question

I am trying to build a generic data structure that needs to hold keys and values and in the same time keep track on the indices in which keys and values were put in, like arraylists do but in a complexity of $O(\log n)$ or less.

I tried to work around a solution to this problem and created various TreeMaps that has Integer indices and values and vice-versa, and the same with keys.

Just to make it more clear, the indices symbolize the insertion order from the user. So if I had 3 elements then their index values are 0, 1, 2 and if element 0 was deleted then I need to push 1 to 0 and 2 to 1 and a new element would be added with index 2.

My problem is when I remove a key and its value, if I want to insert the next key and value in the right index I have to make sure all the old ones were set back by 1. I don't know how to do it and not to fall into $O(n)$ complexity.

My goal is to use existing data structures and mix them to get this result, please take a look at the methods I implemented as I need those.

What I am asking is how can I create a data structure for keys and values that has the put, remove, get, getValueByIndex, getKeyByIndex, getIndexByKey methods in it while each method takes $O(\log n)$ or less and the indices change at each deletion.

Is it possible? And if so what is the mixture of Data-structures to create this?

Answer 1

To summarize, this is what you require:

• a dictionary that
• offers find, add and delete in $O(\log n)$ time and also
• GetByIndex, KeyByIndex and IndexByKey in $O(\log n)$ time, where the index is determined by insertion order.

The first part is easy: use any balanced search tree. Say we use AVL trees.

For the second, we can use a second tree but use an increasing counter as key. With a small change to the data structure, we can find the $i$th element in $O(\log n)$ time (rank selection). Thus, we don't have to change any indices; the tree structure maintains the order for us.

We can further link the two AVL trees back and forth.

Assuming we have an implementation AVL which provides efficient select and rank (zero-based) and has a field for crosslinks, this would be rough pseudocode:

class IndexedDictionary {
  dataTree  = new AVL()
  indexTree = new AVL()
  nextId = 0

  add(key, data) {
    dataNode  = dataTree.add(key, data)
    indexNode = indexTree.add(nextId, data)
    dataNode.crosslink = indexNode
    indexNode.crosslink = dataNode
    nextId += 1
  }

  delete(key) {
    i = index(key)
    dataTree.delete(key)
    indexTree.delete(indexTree.select(i).key)
  }

  find(key) {
    return dataTree.find(key).value
  }

  get(index) {
    return indexTree.select(index).value
  }

  key(index) {
    return indexTree.select(index).crosslink.key
  }

  index(key) {
    return indexTree.rank(dataNode.find(key).crosslink.key)
  }
}

Of course, delete(index) can be implemented similarly to delete(key). Delete can be implemented faster if you add an operation delete-ith to AVL, and have AVL-delete return the removed node.