List insertion cost

Robert Kern robert.kern at
Tue Jul 21 15:43:41 EDT 2009

On 2009-07-21 14:21, Lucas P Melo wrote:
> Hello,
> I would like to know how much it costs to insert an element into a list
> using this operation:
> a[2:2] = [ 1 ]
> i. e, what is the complexity of the operation above (given that len(a) =
> n)?

O(n). Python lists are contiguous arrays in memory, and everything after the 
insertion point needs to be moved. Raymond Hettinger has a good talk about the 
implementation of Python lists and other container objects.

Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco

More information about the Python-list mailing list