A library that contains basic data structures and algorithm implementations in Java for the purposes of the Data Structure + Algorithms course @ FMI, SU.
The following table summarizes what we already know about the algorithmic complexity of the basic operations on several data structures.
| Data structure | Get | Append | Insert | RemoveAt | Search | Random Access? |
|---|---|---|---|---|---|---|
| Sequential List (Dynamic Array) | O(1) |
O(1)A |
O(n) |
O(n) |
O(n) |
True |
| Linked List | O(n) |
O(1) |
O(1) |
O(1) |
O(n) |
True |
| Stack | O(1) |
O(1) |
- |
O(1) |
- |
False |
| Queue | O(1) |
O(1) |
- |
O(1) |
- |
False |
| HashMap | O(1) |
O(1)A |
O(1)A |
O(1) |
O(1) |
False |
- Subscript A means that the complexity is amortized.
The following table summarizes the standard implementations (if any) of several data structures data structures in the most popular programming languages' standard libraries.