A Comprehensive Guide to Python’s Built-In Data Structures
Time complexities Of Python built-in data structures
Data structures are just specialized formats for organizing and storing data. They are a vital part of software development and choosing the right data structure is crucial.
“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” — Linus Torvalds, creator of Linux
One of the most important characters for picking the right one is its Big O notation.
What is a Big O notation? Big O notation (“O” stands for “order”) is the language to describe the performance of an algorithm and how it scales (not necessarily how fast it is).
I realize there are plenty of data structure articles out there. However, in this article, I will focus on Python implementation because:
- There is no single place with Python data structures time complexity (almost).
- I have somewhat different data structures.
- The time complexity can be surprising due to implementation.
List is an ordered mutable collection of elements.
Set is an unordered collection of distinct hashable objects.
Dict maps hashable values to arbitrary mutable objects.
4. Default dict
Default dict is a dictionary that is initialized with a default value when each key is encountered for the first time.
Deque is a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”).
Heapq is a binary search tree for which every parent node has a value less than or equal to any of its children.
Counter is a
dict subclass for counting hashable objects. It is an unordered collection where elements are stored as dictionary keys and their counts are stored as dictionary values.
The bisect module implements an algorithm for inserting elements into a list while maintaining the list in sorted order.
I hope you found it interesting and useful. I am open to any kind of constructive feedback.