About the implementation of del in Python 3

[Jussi Piitulainen]

Dan Wissme writes:

> I thought that del L[i] would slide L[i+1:] one place to the left,
> filling the hole, but :
>
>>>> L
> [0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
>>>> id(L)
> 4321967496
>>>> id(L[5])    # address of 50 ?
> 4297625504
>>>> del L[2]
>>>> id(L[4])     # new address of 50 ?
> 4297625504
>>>> id(L)
> 4321967496
>
> So the element 50 is still at the same memory location.
> What del L[i] do exactly, and what is its complexity ? O(1) or O(n) ?

id identifies the object that is stored at that index, not the location.
Locations are not objects.

Consider [L[5], L[5]] where the same object is stored in two different
places. In the implementation level there is some kind of reference in
the internal representation of the list to the representation of the
object somewhere else in memory. In the language level, the object
simply is stored in two places, and that's nothing unusual. Storing or
fetching or passing or returning objects around does not make copies.

Incidentally, let no one point out that ids are not memory addresses.
It says in the interactive help that they are (Python 3.4.0):

Help on built-in function id in module builtins:

id(...)
    id(object) -> integer
    
    Return the identity of an object. This is guaranteed to be unique
    among simultaneously existing objects. (Hint: it's the object's
    memory address.)