Python library data structures

Key 2: Using Python's standard library data structures.

• collections.deque: The collections module have a deque implementation. Deque is useful for the scenarios where item insertion and deletion occurs at both ends of structure as it has efficient inserts at the start of structure as well. Time-complexity is similar to copy O(n), insert—O(1), and delete—O(n). The following graph shows an insert at 0 position operation comparison between list and deque:

  >>> d = deque()
  >>> getsizeof(d)
  632
  >>> d = deque(range(100))
  >>> getsizeof(d)
  1160

  The following image is the graphical representation of the preceding code:

  
• PriorityQueue: A standard library queue module has implementations for multiproducer, and multiconsumer queues. We can simplify and reuse its PriorityQueue for simpler cases using the heapq module, as follows:

  from heapq import heappush, heappop
  from itertools import count
  
  class PriorityQueue(object...