CODEWITHSUNDEEP
linked-listruntimetime-complexitydoubly-linked-list
Genadi
Genadi

Reputation: 249

Improving data structure

If I have a data structure that acting like a stack, which I implemented using Doubly Linked list, I also added a pointer which always keeps the middle element.

I want to modify it by adding a method peekAt(k) which will return the Kth inserted element, in O(log(k)).

linked list

Any ideas how can I do this? Thanks.

Upvotes: 0

Views: 39

Answers (1)

pkacprzak
pkacprzak

Reputation: 5617

If you implemented it as a double linked list, you cannot return k-th elementh in O(log(k)) time, because linked list doesn't have a random access to elements. I suggest implementing your stack as an (dynamic) array instead where you can achieve O(1) access.

EDIT:

If you want also fast insertion / deletion in any place, then I suggest using a balanced binary tree.

Upvotes: 1

Related Questions