Timing Difference: insert vs. append & reverse

[Duncan Booth]

bryanjugglercryptographer at yahoo.com (Bryan Olson) wrote in
news:1a517b5.0408031027.60554dfb at posting.google.com: 

>> 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 [array] based implementation gives
>> better performance. 
> 
> True, but an array implementation can easily support amortized 
> constant-time insert/delete at *either* end (without breaking 
> constant-time indexing).  The same trick of keeping extra space 
> at the tail end can work at the head; it requires keeping one 
> additional offset to show where the occupied cells start.
> 

If the OP had said he expected insert and append to be the same speed I 
might buy that, but he expected insert to be faster than append.