The Python wiki page on time complexity says that deleting an item takes O(n) time. The description of the deque class in the documentation of the collections module says that "list
objects [...] incur O(n) memory movement costs for pop(0)
and insert(0, v)
operations which change both the size and position of the underlying data representation".
Why do lists need O(n) time? Isn't a list just a bunch of elements, or pointers to elements, physically next to each other in memory, along with a pointer to where the list starts? If so, why can't the list
type have a popleft
method, similar to the one in collections.deque
, that removes the first element in O(1) time by appropriately incrementing the start pointer of the list?
I am not trying to solve any specific problem. I just want to satisfy my curiosity as to why it is designed that way.
EDIT: Here is a diagram of how my popleft
method would work:
Before calling popleft
:
-------------------------------------------------------------------
| The | quick | brown | fox | jumps | over |
-------------------------------------------------------------------
^
pointer to list
After calling popleft
:
-------------------------------------------------------------------
| The | quick | brown | fox | jumps | over |
-------------------------------------------------------------------
^
pointer to list
Before the call to popleft
, the first element of the list is The
, the 2nd is quick
, etc. After the call, the place where the first element was is now unused memory (which may be left empty or claimed by the garbage collector), the new first element is quick
, the new 2nd element is brown
, etc. No large amount of data needs to be moved, and nothing needs to happen that takes O(n) time.
The pointer to where the list really starts must be retained for the purpose of freeing the memory appropriately.
Indeed, remove(0)
could be made faster by having a second pointer which is increased in this case. And if an .add(0, x)
happens afterwards, this could be made faster by decrementing this "data start timer" as long as it is bigger than the "memory start timer".
But all other operations, i. e. insertions and deletions to other indexes, would still be O(n)
, so that wouldn't change much.
Just know what your operations will be and thus which data structure to pick.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With