3

l = [1,2,3,4]

popping the last element would be an O(1) operation since:

  1. It returns the last element
  2. Changes a few fixed attributes like len of the list

Why can't we do the same with pop(0)?

  1. Return the first element
  2. Change the pointer of the first element (index 0) to that of the second element (index 1) and change a few fixed attributes?
figs_and_nuts
  • 4,870
  • 2
  • 31
  • 56
  • Why do you think it isn't *O(1)*? – user207421 Aug 21 '23 at 02:18
  • All online sources say it.. like https://stackoverflow.com/questions/34633178/why-is-the-big-o-of-pop-different-from-pop0-in-python – figs_and_nuts Aug 21 '23 at 02:21
  • What do you do with that extra unused memory? Memory is typically allocated in globs of a convenient size. If you change the starting pointer, now you have wasted memory, unless you reallocate and copy. – Tim Roberts Aug 21 '23 at 02:22
  • Isn't that the exact hit we are also taking in the case of pop(-1)? – figs_and_nuts Aug 21 '23 at 02:28
  • @TimRoberts you can ignore it (*mostly* it's no worse than unused space at the end of the allocation, which you commonly have for efficiency); you can force a copy-down if the offset gets beyond a certain size (which lowers the amortized cost of copying, while capping wasted space); or you can force a copy-down if the user is trying to add an element on the right, and there's no free space there but there is free space on the left (which is what Perl does, to prevent endless growth if the user repeatedly pushes on the right and pops on the left). – hobbs Aug 22 '23 at 13:25
  • Right, and one has to decide whether the benefit is worth the cost. Most usages of list don't do that, and for those that do, you have `deque`. A container cannot be all things to all people. The C++ STL library has done an excellent job of itemizing this, where each type of container has the performance behavior specified explicitly. You don't wish that `std::vector` does what you want; instead, you choose another container. Python lists happen to be like `std::vector`. – Tim Roberts Aug 22 '23 at 18:52

1 Answers1

4

Lists could have been implemented to do what you suggest, but it would add complexity and overhead, for an operation better handled by collections.deque. All lists everywhere would need extra metadata to track how much empty space is at the front (important for handling the resize policy, and calling free on the right pointer when the list dies or gets resized), and the logic for when and how to resize would also become more complicated.

The tradeoff was not deemed worthwhile.

user2357112
  • 260,549
  • 28
  • 431
  • 505
  • 1
    Why would we need to store how much empty space is at the front? As I see it we just change the pointer of the 0th element to the 1st element and the rest of the modifications are exactly the same as in the case of pop(-1). The offset arithmetic would work just fine and now it is as good a list as any? – figs_and_nuts Aug 21 '23 at 02:24
  • 1
    @figs_and_nuts then who owns that memory and how does it get freed? – hobbs Aug 21 '23 at 02:28
  • @figs_and_nuts: How are you going to free the right pointer when the list is reclaimed? You need two pieces of info to track both the start of the buffer and the start of the list's data. That can be two pointers or a pointer and a count, but either way, you need more metadata than without this feature. – user2357112 Aug 21 '23 at 02:28
  • To understand you correctly, I think what you are saying is: the list, in memory, actually is: {metadata} {data in the list}. Both are contiguous. Now if I change just the pointer of the first element, there's that unnecessary void between the metadata and the list data that can't be used? This obviously isn't the case with pop(-1). Am I correct in understanding you? If this is the case, I didn't know this and my question has been answered. My understanding was that for a list the contiguity is needed only for the list data and the metadata could be stored anywhere else – figs_and_nuts Aug 21 '23 at 02:32
  • @figs_and_nuts: No. The metadata and the list's buffer are allocated separately. But if you don't track where the list's buffer starts, you can't free the buffer. – user2357112 Aug 21 '23 at 02:35
  • 1
    Lists, as currently implemented, only need a single pointer to track the start of the buffer and the start of the list's data, because these are the same thing. Your proposal would make these different things, which would need extra metadata to track separately. – user2357112 Aug 21 '23 at 02:39
  • 2
    FWIW Perl does it exactly the way that Python doesn't, so it is an option. The two pointers are `AvARRAY` (points to the element you get if you access `[0]`) and `AvALLOC` (points to the beginning of the underlying allocation). It definitely takes a bunch of code to manage them both correctly, plus some extra to make sure that an array used like a queue (pushed at the end, popped at the beginning) doesn't slide that pointer forward forever and leak memory like a sieve. – hobbs Aug 21 '23 at 02:49
  • I see. Personally, it would have made more sense to have the dynamic nature of the array implemented at both ends rather than just at the tail. Would allow dequeue-like capabilities in the list and also, O(n) amortized prepends. Bit more complex, bit more size of the memory buffer to be allocated but the benefits would outweigh the costs. But, I see the challenges as well. Thank you for helping me guys :) – figs_and_nuts Aug 21 '23 at 04:31