linked list, implement peekAt(k) method in log(k)

user_13515835 0
Viewed 70

I have been asked to design a data structure which will act like a stack, not limited in size, which will support the following methods, with given run-time restrictions.

push(s) - push s to the data structure - O(1) pop() - remove and return the last element inserted O(1) middle() - return the element (without removing) with index n/2 by insertion order where n is the current amount of elements in the data structure. - O(1) peekAt(k) - return the kth element by insertion order (the bottom of the stack is k=1) - O(log(k))

the 3 methods will use a linked list, but how i should implement the method peekAt(k).

thank you.

data-structures time-complexity linked-list
1 Answers

What you are looking for is a variant of Skip List, which is ordered by insertion order.

The only modification you actually need, in order to support O(logk) instead of O(logn), is to from from down up before you initiate your search, something like:

// Assume head points to the first element in the lower tier list.
current = head
while (current->next->index < k) current = current->up

At this point, the element you are looking for is somewhere between current and current->next. You can look it up using a regular skip list search for the value k, starting from current instead of the top tier.

Note that finding current is done in O(logk), because, you basically check iteratively:

1 < k ?
2 < k ?
4 < k ?
8 < k ?
...
2^ceil(logk) < k ?

Which is, O(log(k)) checks.

user_5726700
Related