Timing Difference: insert vs. append & reverse

[Tim Peters]

[Bryan Olson, on complicating the list object again, and 2.4's deque type]
> But it breaks (efficient) indexing.  Since we can have it all
> like Perl, why not?

As I said, the best Perl can do is O(1) amortized.  2.4's deque does
better than that, and that can be important in classes like Python's
Queue.Queue where threads typically block waiting for pops and pushes
(but has no use at all for random access).

If you follow the link you gave last time and read to the bottom
following the other links, you'll find that Perl lists had
quadratic-time behavior under the steady-state queue pattern for a
long time.  That was eventually fixed -- or so they say.  Small
details are both tricky and vital.  2.4's deque implementation is
obviously immune to "bad" patterns, steady-state queue or otherwise.

Most immediately damning, adding another member to the list struct (to
keep track of the "low bound") would increase the size of every list
object by 8 bytes, on 32-bit boxes.  Python lists are easy to spell,
use and access, and some Python apps use millions of small lists. 
They wouldn't appreciate the RAM hit for a mostly-useless feature. 
Most Perl programmers seem to be so confused by Perl lists that they
only use them when they have to, to shift function arguments in and
out <0.6 wink>.  That's a use case for lists Python doesn't have at
all.

You can pursue it if you want to, but with the 2.4 deque type I have
no interest in messing more with the list type.