| Operation | Example | Class | Notes |
|---|---|---|---|
| Index | l[i] | O(1) | |
| Store | l[i] = 0 | O(1) | |
| Length | len(l) | O(1) | |
| Append | l.append(5) | O(1) | mostly: ICS-46 covers details |
| Pop | l.pop() | O(1) | same as l.pop(-1), popping at end |
| Clear | l.clear() | O(1) | similar to l = [] |
| Slice | l[a:b] | O(b-a) | l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N) |
| Extend | l.extend(...) | O(len(...)) | depends only on len of extension |
| Construction | list(...) | O(len(...)) | depends on length of ... iterable |
| check ==, != | l1 == l2 | O(N) | it should be multiplied buy comparison complexity, e.g. if elements are strings of length t, the complexity would be O(N*t) (worst case) |
| Insert | l[a:b] = ... | O(N) | |
| Delete | del l[i] | O(N) | depends on i; O(N) in worst case |
| Containment | x in/not in l | O(N) | linearly searches list |
| Copy | l.copy() | O(N) | Same as l[:] which is O(N) |
| Remove | l.remove(...) | O(N) | |
| Pop | l.pop(i) | O(N) | O(N-i): l.pop(0):O(N) (see above) |
| Extreme value | min(l)/max(l) | O(N) | linearly searches list for value |
| Reverse | l.reverse() | O(N) | |
| Iteration | for v in l: | O(N) | Worst: no return/break in loop |
| Sort | l.sort() | O(N Log N) | key/reverse mostly doesn't change |
| Multiply | k*l | O(k N) | 5*l is O(N): len(l)*l is O(N**2 |
| Get Length | len((...) | O(1) |
Same as lists but immutable
Sets have many more operations that are O(1) compared with lists and tuples. Not needing to keep values in a specific order in a set (while lists/tuples require an order) allows for faster implementations of some set operations.
| Operation | Example | Class | Notes |
|---|---|---|---|
| Length | len(s) | O(1) | |
| Add | s.add(5) | O(1) | |
| Containment | x in/not in s | O(1) | compare to list/tuple - O(N) |
| Remove | s.remove(..) | O(1) | compare to list/tuple - O(N) |
| Discard | s.discard(..) | O(1) | |
| Pop | s.pop() | O(1) | popped value "randomly" selected |
| Clear | s.clear() | O(1) | similar to s = set() |
| Construction | set(...) | O(len(...)) | depends on length of ... iterable |
| check ==, != | s != t | O(len(s)) | same as len(t); False in O(1) if the lengths are different |
| <=/< | s <= t | O(len(s)) | issubset |
=/> | s >= t | O(len(t)) | issuperset s <= t == t >= s Union | s | t | O(len(s)+len(t))| Intersection | s & t | O(len(s)+len(t)) Difference | s - t | O(len(s)+len(t))| Symmetric Diff| s ^ t | O(len(s)+len(t)) Iteration | for v in s: | O(N) | Worst: no return/break in loop Copy | s.copy() | O(N) |
Same as sets but immutable
| Operation | Example | Class | Notes |
|---|---|---|---|
| Index | d[k] | O(1) | |
| Store | d[k] = v | O(1) | |
| Length | len(d) | O(1) | |
| Delete | del d[k] | O(1) | |
| get/setdefault | d.get(k) | O(1) | |
| Pop | d.pop(k) | O(1) | |
| Pop item | d.popitem() | O(1) | popped item "randomly" selected |
| Clear | d.clear() | O(1) | similar to s = {} or = dict() |
| View | d.keys() | O(1) | same for d.values() |
| Construction | dict(...) | O(len(...)) | depends # (key,value) 2-tuples |
| Iteration | for k in d: | O(N) | all forms: keys, values, items - Worst: no return/break in loop |
Dict with a default constructor which lets the programmer to use a new key without constructing it Time Complexity is same as Dict
A deque (double-ended queue) is represented internally as a doubly linked list. (Well, a list of arrays rather than objects, for greater efficiency.) Both ends are accessible, but even looking at the middle is slow, and adding to or removing from the middle is slower still.
| Operation | Average Case |
|---|---|
| copy | O(n) |
| append | O(1) |
| appendleft | O(1) |
| pop | O(1) |
| popleft | O(1) |
| extend | O(k) |
| extendleft | O(k) |
| rotate | O(k) |
| remove | O(n) |
Most commonly refers to singly linked list. Data stored in nodes where each node has a reference to the next node. There are doubly linked list and circular linked list as well. Stack and queue are often implemented with linked list because linked list are most performant for insertion/deletion, which are the most frequently used operations for stacks/queues.
| Operation | Average Case |
|---|---|
| indexing | O(n) |
| searching | O(n) |
| insertation | O(1) |
| deletion | O(1) |
A binary tree with extra condition that each node is greater than or equal to all nodes in left sub-tree, and smaller than or equal to all nodes in right sub-tree.
| Operation | Average Case |
|---|---|
| indexing | O(1) |
| searching | O(log n) |
| insertation | O(log n) |
| deletion | O(log n) |
A binary tree with the condition that parent node’s value is bigger/smaller than its children. So root is the maximum in a max heap and minimum in min heap. Priority queue is also referred to as heap because it’s usually implemented by a heap.
| Operation | Average Case |
|---|---|
| min/max | O(1) |
| insertation | O(log n) |
| deletion | O(log n) |
Same memory usage as simple list
| Operation | Average Case |
|---|---|
| Compute the sum of the first i-th elements | O(log n) |
| Update (add a positive or negative number) | O(log n) |
!https://www.geeksforgeeks.org/wp-content/uploads/BITSum.png
- Leaf Nodes are the elements of the input array.
- Each internal node represents some merging (e.g. sum) of the leaf nodes.
| Operation | Average Case |
|---|---|
| Compute the sum (or pther func) of the first i-th elements | O(log n) |
| Update (add a positive or negative number) | O(log n) |
!https://media.geeksforgeeks.org/wp-content/cdn-uploads/segment-tree1.png
| Struct | Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | Space Complexity |
|---|---|---|---|---|---|---|---|---|---|
| Array | Θ(1) | Θ(n) | Θ(n) | Θ(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stack | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Singly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Skip List | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n log(n)) |
| Hash Table | N/A | Θ(1) | Θ(1) | Θ(1) | N/A | O(n) | O(n) | O(n) | O(n) |
| Binary Search Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Cartesian Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(n) | O(n) | O(n) | O(n) |
| B-Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Red-Black Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Splay Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| AVL Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| KD Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |