My own ideal solution would be a subtle hack to the list implementation to make pop(0) and insert(0, x) go a lot faster -- this can be done by adding one or two extra fields to the list head and allowing empty space at the front of the list as well as at the end.
I'm sure you know this, but just for sake of argument, how many extra fields?
You misunderstood -- the *fields* I was talking about are counters or pointers that keep track of the overallocation, and 1 or at most 2 is enough.
A couple? A few? 20? 30? I'm not sure there really is a good hard and fast number.
You're talking about the amount of overallocation. I would propose to overallocate exactly as much as the list implementation currently does, which is a very subtle scheme that overallocates more when the list grows larger to maintain logarithmic behavior.
I think it makes as much sense to preallocate the same number of entries to the front of a list, as to what is currently allocated to the back. At that point, you can guarantee O(1) {pop(0), pop(), append() and insert(0)} behavior, at the cost of slightly more memory. Then it really wouldn't matter how people implement their stacks or queues (front, back, double-list), it would still be fast.
Right. --Guido van Rossum (home page: http://www.python.org/~guido/)