List insertion cost

Diez B. Roggisch deets at nospam.web.de
Wed Jul 22 13:55:29 CEST 2009


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) I'd say. You need to copy nearly the whole list, and sometimes
re-allocate it's storage (they are internally stored as arrays of object
references)

Diez



More information about the Python-list mailing list