About the implementation of del in Python 3

[Steve D'Aprano]

On Thu, 6 Jul 2017 06:51 pm, Dan Wissme wrote:

> So what 'del L[i]' do exactly in memory ? Same as L.pop(i) ? with
> complexity O(n-i) ?

It depends on what L is and what the value of i is. If L is a list, and i is the
last index of the list, then deleting it is quick. If i is 0, then Python has
to copy the entire list over by one slot, which will probably be O(n) slow.

If you care about the performance of this, then you probably shouldn't use a
list. Consider using collections.deque, which is optimized to be fast to insert
or delete items at both ends. (But it is slower to do so in the middle.)

By the way, the big O algorithmic complexity is not a language promise, so it is
possible that it could change in the future, or in some other implementation. I
think the only *guarantee* is that:

- appending to a list is amortised O(1);
- item retrieval from a list is O(1).

Anything else is implementation dependent and could (but probably won't) change.



-- 
Steve
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.