Steve Howell wrote: > Is that really true in CPython? It seems like you could advance the > pointer instead of shifting all the elements. It would create some > nuances with respect to reclaiming the memory, but it seems like an > easy way to make lists perform better under a pretty reasonable use > case. > > Does anybody know off the top of their head if the "have-to-be-shifted- > by-one" warning is actually valid?
Why do you think the documentation has such obvious errors? CPython's list type uses an array of pointers to store its members. The type is optimized for the most common list operations in Python: iteration and appending. Python code rarely changes the head or middle of a list. The dequeue type is an optimized data structure for popping and inserting data at both ends. When you list.pop() or list.insert() the pointers in the internal array must be shifted. appending is much faster because the internal array is overallocated meaning it contains free slots at the tail of the data structure. A linked list of pointers requires more memory and iteration is slower since since it can't utilize the CPU's cache as good as an array. Christian -- http://mail.python.org/mailman/listinfo/python-list
