-3

I have a requirement in which elements in between need to be popped out. Which will be faster for this requirement? A set or a list in python?

anna
  • 405
  • 5
  • 13
  • If you are popping from the front of the list then a set does it in `O(1)` compared to a list which would be `O(N)`, if you are popping from the end then they both do it in `O(1)`. – yudhiesh Jul 04 '21 at 06:28
  • Somewhat related: https://stackoverflow.com/q/34642155/2988730 – Mad Physicist Jul 04 '21 at 06:28
  • You can just refer to [this](https://wiki.python.org/moin/TimeComplexity). – yudhiesh Jul 04 '21 at 06:29
  • 1
    What do you mean by "elements in between"? That doesn't make sense - in between *what*? And is "between" supposed to be by position or by value? (Sets don't have element positions, so if it's by position, sets definitely don't work.) – user2357112 Jul 04 '21 at 06:33

1 Answers1

2

When you pop an item from a list, all the filing elements most be shifted, so on average the operation is O(n). Popping the first element is the worst case since the entire list has to shift. Popping the last element is effectively O(1) because nothing needs to shift. As far as I know, python lists don't reallocate to a smaller buffer, so the entire list is only copied when the first element is popped.

Sets are implemented as hashables. Unless you get catastrophic had collision, popping an element is always O(1). If you're popping an arbitrary element, since sets are unordered, it may be O(1) even in the face of collisions, depending on how the buckets are implemented.

Mad Physicist
  • 107,652
  • 25
  • 181
  • 264
  • Yes, I was looking at the implementation details of set and list. Thank you – anna Jul 04 '21 at 06:52
  • This is an accurate description of the cost of removing one element, but "elements in between" complicates things, whatever it's supposed to mean. Removing a range of elements from a list can be done more efficiently than by just removing elements one by one. Also, depending on what kind of "between" we're talking about, the concept may not actually apply to sets. – user2357112 Jul 04 '21 at 06:57
  • @user2357112supportsMonica. This answer is a mess because it's late and I spewed it out without noticing the details in the question, but somehow it answers whatever OP was asking I guess. – Mad Physicist Jul 04 '21 at 07:01