what is the best data structure for moving nth element to the front? [closed]

Question

so I need to move n-th element from beginning and move it to the front (and shifting 0,..,n-1 items to the right). What would be best data structure to use and how should I go about it?

I already thinking about skiplist, but don't know how to get O(log n) for access via index. Are there any better things (trees or something) I should use?

Thanks in advance..

Language: C++

Disclaimer: Yes, this is homework.

Answer 1

You can use any balanced binary tree (e.g. a red-black tree) where in each node you cache the number of items stored in that subtree. The items themselves can be stored in the leaves. For indexed lookup, you compare the index with the size of the left subtree. If it's smaller, it's there. Otherwise it's in the right side, so subtract the size of the left subtree from the index to get the index relative to the right subtree. Then recurse. Since the tree is balanced, this gives you O(log n).

For the other operations you can use the existing algorithms for red-black trees. You just need some small modifications to keep track of the size. For example, to move an item to the front, you first find it using the algorithm described above, then delete it and reinsert it at the front. Each of these steps is O(log n), so the total runtime is also O(log n).

Answer 2

These questions always centre on a fundamental principle, you can think of it as the "no free lunch" of computer science: the tradeoff between time and space.

If you want to do something very fast, you need to consume more space, and vice versa.

For example, an array is the best-case for small space, but the moment you need to move something, it is horrendous. Hashtable is the best case for fast access, but consumes an excessive amount of wasted space.

So you have to decide what is more important, space economy or time economy.

In this case, if you are looking for O(log n) for indexed lokup, you can use a skip-list or indexed skip list. These data structures provide the benefits of linked list (easy to move the n-th element to the front, just change two pointers) with the benefits of an array (indexed lookup), at the cost of space (more pointers are stored to the "skipped" lists).