A friend of mine was asked a question during a CS exam about finding and maintaining the minimal element in a linked list in constant time, as elements are randomly added to and deleted from the list. He could not answer it, and after he related this to me, neither could I.
Sure, when elements are being added, you can figure out which one is the minimal by keeping it in an outside variable, but if they are deleted, how do you find the next smallest if the minimal one is gone? Is there a particular weird data structure to be used?
(No, it's not a homework question. :) Just a pointer would be sufficient to satisfy our curiousity.