python insert vs append

Question

I have written basic python snippets to first insert values in a list and then reverse them. I found that there was a huge difference of speed of execution between insert and append methods.

Snippet 1:

L = []
for i in range(10**5):
 L.append(i)
L.reverse()

Time taken to execute this :

real    0m0.070s
user    0m0.064s
sys         0m0.008s

Snippet 2:

l = []
for i in range(10**5):
 l.insert(0,i)

Time taken to execute:

real    0m5.645s
user    0m5.516s
sys         0m0.020s

I expected the snippet 2 to perform much better than snippet1, since I am performing the reverse operation directly by inserting the numbers before. But the time taken says otherwise. I fail to understand why the latter method takes more time to execute, even though the method looks more elegant. Does any one have any explanation for this?

Answer 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.