Shouldn't you malloc() in the case of prepending, and do the copying yourself? realloc can only avoid copying if it can append a free block. For the list, we know a) realloc is unlikely to find a new block, anyway, as it is pymalloc, which never extends a small block.
Not for large lists. pymalloc passes large objects off to real malloc.
b) even if realloc would be able to extend the block, we still would have to copy the data.
For really large lists, you'd risk running out of memory due to the malloc(1GB), while realloc(1GB) very likely just extends (since such a large block effectively becomes in a memory segment of its own).
I don't know whether the overallocation would make similar-sized room at both ends, or whether it would take the current operation into account. For the specific case of queues, we may find that doing *just* the copying might be sufficient, with no need to go to the allocator.
Hm. An idea: don't bother overallocating when inserting in the front, but do keep the free space in the front if possible. Then recommend that queus are implemented using append(x) and pop(0), rather than using insert(0, x) and pop(). --Guido van Rossum (home page: http://www.python.org/~guido/)