operation complexities of lists and dictionaries

[Paul Rubin]

"xarnaudx at gmail.com" <xarnaudx at gmail.com> writes:
> what are the time complexities of inserting / removing / checking if an
> element is present in 1) a list and 2) a dictionary?
> does anybody know?

I assume in the list case, the element you want to operate on is in
the middle of the list.  In CPython, those are linear time operations.
If you just want to append to the end or remove from the end, those
are approximately constant time.  For dicts, all those operations are
approximately constant time in CPython.  Approximately means
occasionally something happens that makes it slower, but it's constant
time on average.

The Python docs don't specify this anywhere but it's so fundamental to
how people expect Python to work that it's not likely to be much worse
in any other implementation.