list implementation of pop, __delitem__, __delslice__, __setslice__, insert, etc

Question

Is there anything special going on inside of the python methods that remove a value from, or insert into the middle of, a list? Is it just deleting/inserting and shifting everything over? Or is there something more creative that maintains random access without all the shifting around. I thought I had heard that inserting into the front of a list resulted in the rest of it being shifted, is the same idea true for deleting from the middle?

Answer 1

It's shifting everything. Python lists are implemented as dynamic arrays, which require O(n) time to insert or delete from the middle.

I tried to find a place in the docs that says this, or a proof that any clever way of allowing O(1) insertion and deletion from the middle could be extended to O(1) insertion and deletion everywhere, but I couldn't find anything. Instead, you get an excerpt from the Python source code, written in C.

In the Python 2.7.3 source code, in listobject.c, this is where the insertion method shifts everything to the right of where it's inserting:

items = self->ob_item;
for (i = n; --i >= where; )
    items[i+1] = items[i];

I couldn't find the corresponding code for deletion, unfortunately.