python insert vs append

Solution 1:

Here is the complete answer from Duncan Booth:

A list is implemented by an array of pointers to the objects it contains.

Every time you call 'insert(0, indx)', all of the pointers already in the list have to be moved up once position before the new one can be inserted at the beginning.

When you call 'append(indx)' the pointers only have to be copied if there isn't enough space in the currently allocated block for the new element. If there is space then there is no need to copy the existing elements, just put the new element on the end and update the length field. Whenever a new block does have to be allocated that particular append will be no faster than an insert, but some extra space will be allocated just in case you do wish to extend the list further.

If you expected insert to be faster, perhaps you thought that Python used a linked-list implementation. It doesn't do this, because in practice (for most applications) a list based implementation gives better performance.

I actually have nothing else to add.

Solution 2:

Note that your results will depend on the precise Python implementation. cpython (and pypy) automatically resize your list and overprovision space for future appends and thereby speed up the append furthermore.

Internally, lists are just chunks of memory with a constant size (on the heap). Sometimes you're lucky and can just increase the size of the chunk, but in many cases, an object will already be there. For example, assume you allocated a chunk of size 4 for a list [a,b,c,d], and some other piece of code allocated a chunk of size 6 for a dictionary:

Memory  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
       |a b c d| | dictionary |

Assume your list has 4 elements, and another one is added. Now, you can simply resize the list to size 5:

Memory  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
       |a b c d e| dictionary |

However, what do you do if you need another element now?

Well, the only thing you can do is acquire a new space and copy the contents of the list.

Memory 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
                | dictionary |a  b  c  d  e  f |

Note that if you acquire space in bulk (the aforementioned overprovisioning), you'll only need to resize (and potentially copy) the list every now and then.

In contrast, when you insert at position 0, you always need to copy your list. Let's insert x:

Memory  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
orig   |a b c d| |dictionary|
after  |x a b c d|dictionary|

Although there was enough space to append x at the end, we had to move (not even copy, which may be less expensive in memory) all the other values.