Ram Rachum writes:
Okay, now that I've posted on python-list, and among the 80% of joke posts in my thread, there was a 20% of posts that assured me that Python's list has no such behavior and that I should use deque,
For complexity of collections the best reference I know is https://wiki.python.org/moin/TimeComplexity
Is there a good reason why `list.insert(whatever, 0)` doesn't opportunistically try to allocate more space at the left side of the list, so as to save the expensive operation of moving all the items? I'm not saying it should reserve space there, just check if that space is available, and if so use it.
The problem is that it would have to have unholy carnal knowledge of OS internals (eg, of malloc). First off, availability itself is non-portable, depending on a lot of things (eg, placement of malloc metadata and Python object metadata). I would imagine those things are placed at the beginning of a data structure, but your OS may vary. Even if somehow they were placed at the end of the allocation block, you'd have to ask malloc if there is an empty block before it, and then futz with the malloc metadata if you were to try to snarf that block. Sounds like a great way to crash Python to me. I'll take collections.deque, thankyouverymuch. A general note: implementations of Python builtins are generally quite well-tuned, but not at the expense of excessive complexity. Python's threshold for "excessive" is pretty low, but nonetheless most builtins are very efficient by now. P.S. ISTR posting via Googlegroups is deprecated.