[Python-Dev] collections module

[Tim Peters]

[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.