Cheat Sheets
Every Data Structure on 1 Page
Array
An Array is an ordered list of elements, where each lives at an index 0, 1, 2, and so on. Arrays are also called "lists" in Python.
Read/Write Time O(1).
Insert/Delete Time O(n).
Stack
A Stack is an Array, but where you only Insert/Delete the last element. This makes inserting and deleting fast.
Read/Write Time O(1).
Append/Pop Time O(1).
HashMap
A HashMap is a generalized type of Array, where you can look up data using "keys". Keys can be anything as long as they're immutable: strings, tuples, numbers, letters, etc.
HashMaps are called "dictionaries" or "dicts" in Python. We talk about how to implement a HashMap from scratch here.
Read/Write Time O(1).
Insert/Delete Time O(1).
Set
A Set is a HashMap, but where all the values are True. You can quickly check if an element is/isn't in a Set. In Python, sets are implemented as their own data structure, and not as HashMaps.
Read/Write Time O(1).
Insert/Delete Time O(1).
Linked List
A Linked List is a custom data structure that you implement yourself. The first node in the Linked List is called the "head". Each node has a value val, and points to the next node next.
We used HashMaps here instead of ListNodes, because HashMaps are perfectly equivalent to objects and don't require boilerplate code to use. If this is confusing to you, see the Classes and Objects cheat sheet.
Read/Write Time O(n).
Insert/Delete Time O(n).
Tree
A Tree is a custom data structure you implement yourself.
Typically when you say "Tree", you're really referring to the root node of a Binary Tree. In a Binary Tree, each node has a value val, a left child left, and a right child right.
Here's how you create the above binary tree:
We used HashMaps here instead of TreeNodes, because HashMaps are perfectly equivalent to objects and don't require boilerplate code to use. If this is confusing to you, see the Classes and Objects cheat sheet.
Trees generally have a height of O(n), but balanced trees are spread wider and have a height of O(log n), which makes reading/writing faster.
Read/Write Time Varies.
Insert/Delete Time Varies; O(log n) for balanced trees like Binary Search Trees and Heaps.
Graph
A graph is made of nodes that point to each other.
There are two ways you can store a graph, and both are common in coding interviews:
We used HashMaps here instead of GraphNodes, because HashMaps are perfectly equivalent to objects and don't require boilerplate code to use. If this is confusing to you, see the Classes and Objects cheat sheet.
Read/Write Time Varies.
Insert/Delete Time Varies.
Deque
A Double-Ended Queue (Deque) is a Linked List that has a next pointer next and a previous pointer prev. It's a built-in data structure, and the syntax is similar to an Array.
The main benefit of Deques is that reading and writing to the ends of a Deque takes O(1) time; however, the tradeoff is that reading and writing in general takes O(n) time. This is useful when you want to quickly read from both ends of a data structure (like in a Queue) instead of just one end (like an Array).
Read/Write Time O(n).
Insert/Delete Time O(n).
Append/Pop Time O(1).
AppendLeft/PopLeft Time O(1).
Queue
A Queue is not a new data structure - it's the name for an ordered data structure where you add elements from one side, and remove elements from the opposite side. Typically you add elements on the right side, and remove them from the left side.
You should implement a Queue using the Deque data structure, so that it's fast to add/remove from both sides of it. You should not use an Array because it's slow to add an element to the left side of it. Here's how you implement a Queue:
Read/Write Time O(1).
Append/Pop Time O(1).
Sorted Array
A Sorted Array is just an Array whose values are in increasing order. Sorted Arrays are useful because you can use Binary Search on them, which takes O(log n) time to search for an element.
Sorting an array takes O(n log n) time, except for special cases like when you have only integers and can use Counting Sort. We talk about the different sorting algorithms here.
Here are some built-in Python methods for sorting an Array, which take O(n log n) time:
To search a sorted Array, Python's bisect library contains Binary Search methods you can use. However, you should probably just get good at consistently writing a Binary Search instead of using bisect.
Search Time O(log n).
Insert/Delete Time O(n).
Sort Time O(n log n).
Binary Search Tree
A Binary Search Tree (BST) is just a Sorted Array but in tree form. This makes the insert/delete time faster than if you used a Sorted Array.
Stepping left in a BST gives you smaller values, and stepping right gives you larger values. A useful consequence of this that you might want to know, is that an inorder traversal visits values in a BST in increasing order.
Search Time O(log n).
Insert/Delete Time O(log n).
Create Time O(n log n).
Heap
A Heap is a balanced tree where the values increase as you step downwards. We introduced Heaps here.
The purpose of a Heap is to have immediate access to the smallest element, which is always at the top of the Heap. When you store Heaps, you usually store them as Arrays for convenience (there are no downsides to this - see here). Heaps are typically stored in the order of their BFS traversal.
Python only allows Min-Heaps (smallest values on top). If you want a Max-Heap, you can implement it with a Min-Heap by multiplying all your values by -1 when you push and pop.
Read Time O(1).
Push/Pop Time O(log n).
Create Time O(n).
String
Looking for built-in Data Structures like Strings? See the other Cheat Sheet, Everything You Need to Know About Python.