Engineering question

Assume we have direct access to both front and rear ends of a linear list L.

Consider the following five operations on such a list:
- PushFront(x, L): insert item x on the front end of list L.
- PopFront(L): remove the front item from list L and return it.
- PushRear(x, L): insert item x on the rear end of list L.
- PopRear(L): remove the rear item from list L and return it.
- FindMin(L): return the smallest item on list L.

How to support these operations in O(1) amortized time? and how to support these operations in O(1) worst-case time?

thanks

Findmin() would need to run in T(L) time...

plus there's actually a similar thread open at

http://http://forums.devshed.com/t155141/s.html

(a few threads down)

-MBirchmeier

I think the first 4 methods can be done at O(1) with no problem, because these 4 methods doesn't have to search for anything before they perform pop/push, they are just simply insert and delete front/back.

For findmin(), it's hard to get O(1) in real time, usually we have to set a pointer point to the min value in the current linear list when we do insert, then we can compare the current min value in the list to the new input value. However, if we pop the min value, then we have to go through the list once again to find the current. That where I get confuse.