Data structure like struck

Question

I need to offer a data structure like struck, with these functions:

init() with a time complexity of O(1): initialization of an empty structure.
push(x) with a time complexity of O(1): insert a new element with key x to the structure.
pop() with a time complexity of O(1): remove the element that was last inserted into the structure.
getMiddle() with a time complexity of O(1): return the key of the middle (n/2) element (in insertion order).
getAt(k) with a time complexity of O(log k): return the key of the k^th element (in insertion order).

Space complexity is O(n), when n is the nunmber of the elements in the structure.

I am allowed to use the following structures: ADT, Queue, Stack, Array, Linked List, Binary Tree and Binary Search Tree.

I thought about using a linked list, because the initialization of a list is O(1). To insert an element and to remove an element is also O(1). In the functions of push and pop, I thought to use a pointer that points to the middle, and at every insert or delete, the pointer would move. So, in the middle function, return the key at this pointer.

My problem is the last program. I thought about performing a binary search, but the time complexity is O(log(n)) and I need O(log(k)). I thought to split the list in the k^th element, but I don't know how.

Do you have any suggestion to solve this problem?

Just use array with inserting/deleting elements at the last location i..getAt(k) will be o(1) — aravind, May 07 '20 at 12:53
but, we need to know the amount of the elements when we create array. — lirongr1996, May 07 '20 at 13:21
You should look at arraylist in java...where we create array with some capacity and dynamically increase the size and copy them to new array..copying them to new array happens very rare..so we can ignore its time complexity.. — aravind, May 07 '20 at 13:25
Are you interested in worst-case or amortized time complexity? — Roman Svistunov, May 07 '20 at 13:55
You don't need to use ArrayList , You need to implement similar Idea.. — aravind, May 07 '20 at 14:37
Since this is an ADT, you could in theory just use a stack and the underlying implementation uses a doubling array, and you augment the size as another parameter. You then get amortized analysis of O(1) for all of your proposed methods. — MathBunny, May 07 '20 at 14:44

score 1 · Answer 1 · answered May 07 '20 at 18:00

Interesting problem!

If you need to meet all of these time bounds in an amortized sense, a dynamic array supports random access in time O(1) and supports appending elements and removing from the end of the list in amortized time O(1). That would meet all of your requirements. This is probably the easiest option.

If you need to meet all of these requirements in a worst case sense, the only data option I can think of that meets the bounds is the extendible array data structure, which is essentially a de-amortized version of the dynamic array. This can be built out of two arrays, but assumes you can allocate a block of memory of size n in time O(1).

I've been thinking over other options to see if there's something simpler, but nothing I've tried works out. For example, a skiplist lets you get (expected-case) O(log k) lookup of the kth element. To do so, start at the bottom layer and move upward until you reach an element that's past the kth position, then do the regular skiplist lookup start at or below that level. The idea is that, on average, the first time you overshoot position k, you'll be at position roughly 2k, and the search in that sub-skiplist will take time O(log 2k) = O(log k) to find what you're looking for.

There are two problems with that approach. The first is that skiplists are randomized, though that can be overcome by using a deterministic version of a skiplist (these exist, though they're not as well-known). The second is that the cost of inserting into a skiplist is not O(1) due to the cost of wiring the appropriate pointers. You can show that the amortized cost of inserting into such a skiplist would be O(1) if you use a deterministic scheme, but if you're going for amortized efficiency you should just use a dynamic array.

Another option I considered was something like a VList - a linked list of blocks of elements whose sizes grow exponentially in size as you move forward. Finding the kth element could then be done in time O(log k) by simply walking forward in the linked list until you find the appropriately-sized block, then looking within that block. The number of blocks you'd visit this way is O(log k) because, after visiting i blocks, you'll have passed over 2ⁱ⁺¹ - 1 elements. The problem here is that this assumes you can allocate a block of memory in time O(1), and if that's the case you might as well just use the extendible array mentioned earlier.

If I think of anything else, I'll be sure to update this answer. I'm wondering if there's some simpler strategy that I'm missing?

Thank you for the answer, I understand all the option. But, I can use only the regular array or smart array, simple linked list or doubly linked list. Sory if that wasn't understandable — lirongr1996, May 08 '20 at 08:51
you said that the inserting to skiplist is not O(1), if I insert to the end of the list, it would be O(1) ? — lirongr1996, May 08 '20 at 08:57
Unfortunately no, since you may need to wire multiple pointers into that node. — templatetypedef, May 08 '20 at 15:16

Data structure like struck

1 Answers1