[Guido]
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.
[Josiah Carlson]
I'm sure you know this, but just for sake of argument, how many extra fields? A couple? A few? 20? 30?
As Guido said, "one or two" would be enough. I think you're talking about different things, though: Guido is talking about the number of new named struct members that would have to be added to Python's list object header. I think you're talking about how many array slots to leave unused on both ends. Just as now, on a reallocation the number of free slots asked for has to be proportional to the total number of slots, so that growth via a huge number of one-at-a-time appends takes (amortized) constant-time per append. Picking any fixed number of free slots leads to overall quadratic-time (in the number of appends) behavior.