Possibly -- nobody has given enough detail to say. I'd be inclined to continue doing what we do now when an append runs out of room, which is to ask for more room, overallocating by a small percentage of the current
size. If there's free room "at the left end", though, it may or may not be more efficient to memmove the guts left. Those are important details
On enhancing list object: queue vs. deque. My general impression is that queues, while less common than stacks, are used enough in enough different algorithms that adding one implementation field to list headers so that pop(0) is an O(1) pointer move might be an overall win for Python. The current O(n) move everything every time behavior is certainly a nuisance when queues are needed. Deques, on the other hand, seem to be more a theoretical construct. Algorithm books include them for completeness in describing possible list disciplines, but generally ignore them thereafter. I am hard put to remember an algorithm that actually needs them. They are certainly much rarer than queues. So I do not think trying to make prepends O(1) should be considered further. list that
haven't gotten beyond the hand-wavy stage.
My possibly naive thought is that before reallocating, look at the ratio of left free to total. If memmove would result in as much, or perhaps nearly as much, over-allocation as realloc, then just do that. Certainly if the ratio is small (like say .1), don't bother with memmove. The exact cutoff is a tuning matter. Separate issue: for best performance, one would like to be able trade space for time and preallocate a large enough block so that most append faults result in a memmove back to the left. Does the current builtin shrinkage discipline would allow this. Or does "q=[0]*1000; q[:]=[]" shrink the space for q back to nearly nothing? (One might also want to do same for stack. And yes, I remember: 'user tuning' is a 'bad idea'. But....) Terry J. Reedy