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 later 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(1)* |
TreeMap (Red-Black Tree) |
O(log n) |
O(n) |
O(log 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) |
|
* = Amortized run time. E.g. rehashing might affect run time to O(n).