Efficient data structure for extractMin and extractMax

[laserlight]

I need to design or use an existing data structure which performs extractMin, extractMax and insert efficiently. What I mean by extractMin (resp. extractMax) is to retrieve the minimum (resp. maximum) element in the data structure. I know that if I use a red-black tree or avl tree or any other balanced binary tree, each of three operations will be O(logn). I am looking for something more efficient.

You can get constant time extractMin and extractMax at the cost of a slightly more expensive insert with a balanced binary tree simply by keeping track of those elements.

If your stated requirements are really all there is to it, then you can get constant time extractMin, extractMax and insert: use a singly linked list that keeps track of its tail, and also keep track of the minimum and maximum.