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.
| Language | SequentialList | LinkedList | Stack | Queue | HashMap | Set |
|---|---|---|---|---|---|---|
| C++ | vector |
list |
stack |
queue |
unordered_map |
unordered_set |
| Java | ArrayList |
LinkedList |
Stack |
Queue |
HashMap |
HashSet |
| C# | List |
LinkedList |
Stack |
Queue |
Dictionary |
HashSet |
| Python | list |
- |
- |
- |
dict |
set |
| JavaScript | Array |
- |
Array |
Array |
Object |
- |