Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I need to take an kth index element from array like data structure and delete it (k is any possible index). Array have O(n) for deleting elements, and List have O(n) for searching element. I would like to do both operations in O(logn) time.
Which data structure should I use to meet this requirement?
Clarification:
Deleting element on index(5) will move element from index(6) to index(5)
the element at index 6 change indexes so that it now has index 5 and 7th element changes to 6th so on ..
Take any self-balancing binary tree (e.g. AVL) and replace every node's key with the number of left descendants it has. This is easy to keep up-to-date for tree insertions/deletions (in $O(log n)$ time), and rotations (in $O(1)$ time).
Then to find the node with index $i$ you start at the root and repeatedly compare $i$ with the value of the current node $v$. If $i < v$ you go to the left child, $i = v$ you found the correct node and $i > v$ you subtract $i := i - v$ and go to the right child.
You can also use a skip list to do this: https://en.wikipedia.org/wiki/Skip_list#Indexable_skiplist
As described above, a skip list is capable of fast O(log(n)) insertion and removal of values from a sorted sequence, but it has only slow O(n) lookups of values at a given position in the sequence (i.e. return the 500th value); however, with a minor modification the speed of random access indexed lookups can be improved to O(log(n)). For every link, also store the width of the link. The width is defined as the number of bottom layer links being traversed by each of the higher layer "express lane" links.
