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).