In this section, we learned about Graphs, applications, properties, and how we can create them. We mention that you can represent a graph as a matrix or as a list of adjacencies. We went for implementing the latter since it’s more space-efficient. We cover the basic graph operations like adding and removing nodes and edges. In the algorithms section, we are going to cover searching values in the graph.
Data Structure | Searching By | Insert | Delete | Space Complexity | |
Index/Key | Value | ||||
- | O(n) | O(n) | O(n) | O(n) | |
- | O(log n) | O(log n) | O(log n) | O(n) | |
Hash Map (naïve) | O(n) | O(n) | O(n) | O(n) | O(n) |
HashMap (optimized) | O(1) | O(n) | O(1)* | O(1) | O(n) |
TreeMap (Red-Black Tree) | O(log n) | O(n) | O(log n) | O(log n) | O(n) |
O(1) | - | O(1)* | O(1) | O(n) | |
O(log n) | - | O(log n) | O(log n) | O(n) | |
* = Amortized run time. E.g. rehashing might affect run time to O(n).
