5 Python Data Structure Things I Wish I Knew Earlier
# Must-know prerequisite for leetcode-style interviews
1) If we want a stack, simply use a list
A stack is a last-in-first-out (LIFO) container.
To implement a stack, we can simply use a regular list.
Alternatively, we can simply use a list itself without having to implement an entirely new Stack class (we often do this to save time during interviews). Here, .append is the same as .push
2) If we want a queue, using a list is a bad idea
A queue is a first-in-first-out container.
Unlike a stack, it isn’t a good idea to use a regular Python list to implement it — we technically can, but it’s inefficient and your interviewer will probably question you for doing so.
Why is using a regular list as a queue inefficient?
When we enqueue (add something to the back of the queue), we use the list’s .append method, which runs in O(1) time.
However, when we dequeue (remove first element), we use the list’s .pop(0) method. Since a list is indexed, it needs to reindex every other existing element, which makes this operation run in O(n) time.
Use a deque instead (double-ended queue)
In a deque, popping from and appending to both left and right sides of the queue takes O(1) time. Always use a deque instead of a regular list to implement a queue.
3) A list can represent a binary tree
We often write our own classes to represent a binary tree as it is intuitive.
But did you know that we can actually represent a binary tree using a regular list?
value at index 0 is the root
values at indexes 1 & 2 are the left/right children of index 0
values at indexes 3 & 4 are the left/right children of index 1
values at indexes 5 & 6 are the left/right children of index 2
and so on and on
Quick Pause
Consider buying my ebook — 256 Python Things I Wish I Knew Earlier — a collection of hard-earned insights from writing 500,000+ lines of code over 10 years. Save yourself years of trial and error.
Link: https://payhip.com/b/xpRco
4) If we want priority queues, use the heapq library
Link: https://payhip.com/b/xpRco4) If we want priority queues, use the heapq library
If we need a priority queue, we can use a heap — it supports O(log n) enqueue and O(log n) dequeue. In Python, we can use the heapq library.
Note — for heapq, each element needs to be in a format (priority, element, ...)
If this is confusing, you could implement your own Heap class using heapq
But I usually use heapq directly as it saves more time.
5) heapq supports max heaps in Python 3.14+
Before Python 3.14, heapq only supported min-heaps — where the top element is always the smallest value.
However, since Python 3.14, max heaps are now supported in heapq, which makes things more convenient.
Note — technically, we can implement a max heap ourselves with old heapq by adding a negative sign in front on our heap key. But with this new change, we no longer need to deal with this annoyance.
Conclusion
Hopefully this was clear and easy to understand
If You Wish To Support Me As A Writer
Buy my Ebook — 256 Python Things I Wish I Knew Earlier at https://payhip.com/b/xpRco — a collection of hard-earned insights from writing 500,000+ lines of code over 10+ years. Save yourself from years of trial and error
Thank you — these actions go a long way, and I really appreciate it.