Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does Python take O(n) time to remove the first element from a list?

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.

like image 540
Elias Zamaria Avatar asked Mar 12 '23 03:03

Elias Zamaria


1 Answers

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.

like image 129
glglgl Avatar answered Apr 28 '23 04:04

glglgl