A Simple implementation of DataStructures using scala.
I'm broadly focusing on simple data structures (their concepts) and implementing them in Scala. The intent is not to implement a complete collections API as this is completely reinventing the wheel. Rather the intent is to learn the foundational data structures, their strengths and weaknesses, their asymptotic analysis and of course using functional programming in scala. :-)
- Arrays
- ArrayLists
- Linked Lists
- Stacks
- Queues
- Dictionaries (HashTables)
- Binary Search Trees (Vanilla)
- Heaps (Priority Queues)
- Red-Black Trees
- B-Trees
- Graphs
- Quick Sort
| DATA STRUCTURE | SEARCH | INSERT | DELETE | NOTES |
|---|---|---|---|---|
| Arrays | O(n) | O(n) | O(n) | |
| ArrayLists | O(n) | O(n) | O(n) | |
| LinkedLists | O(n) | O(1) | O(1) | |
| Queues | O(n) | O(1) | O(1) | |
| Stacks | O(n) | O(1) | O(1) | |
| BST (Vanilla) | O(n) | O(n) | O(n) | No balancing techniques employed as such. |