This repository contains an implementation of common data structures and algorithms in Java. This code is primarily intended for understanding and learning data structures, and for finding their complexity. It is designed for students and self-learners.
Great request, if you see an error or inaccuracy, please make a correction. Any help is welcome.
The following keys are used to indicate the level of difficulty and time/space complexity of each algorithm:
🍏
: easy;🍊
: medium;🍎
: hard;⭕️(1)
,⭕️log(N)
,⭕️(N^2)
, etc: time and space complexity;- [
✍🏻
]: in progress; - [
🙇🏻♂️
]: hard to solve; - [
❓
]: the solution is not optimal; - [
🆗
]: Test passed Ok;
The following data structures are implemented in this repository:
The Arrays
class provides the following algorithms:
Algorithm (operation) | Level | Done | Time Complexity | Space Complexity | Tests passed: |
---|---|---|---|---|---|
findMin | 🍏 |
✔️ |
⭕️(N) |
⭕️(1) |
[🆗 ] Open |
mergeSortedArrays | 🍊 |
✔️ |
⭕️(N) |
⭕️(N) |
[🆗 ] Open |
mergeUnsortedArrays | 🍊 |
✔️ |
⭕️(N^2) |
⭕️(N) |
[🆗 ] Open |
pop | 🍏 |
✔️ |
⭕️(N) |
⭕️(N) |
[🆗 ] Open |
push | 🍏 |
✔️ |
⭕️(N) |
⭕️(N) |
[🆗 ] Open |
remove(position) | 🍏 |
✔️ |
⭕️(N) |
⭕️(N) |
[🆗 ] Open |
reverse | 🍊 |
✔️ |
⭕️(N) |
⭕️(1) |
[🆗 ] Open |
reverse(start,end) | 🍊 |
✔️ |
⭕️(N) |
⭕️(1) |
[🆗 ] Open |
size | 🍏 |
✔️ |
⭕️(N) |
⭕️(1) |
[🆗 ] Open |
sort | 🍊 |
✔️ |
⭕️(N^2) |
⭕️(1) |
[🆗 ] Open |
genericArray <T> | 🍎 |
✔️ |
[🆗 ] Open |
The Sort
classes provide the following algorithms:
Algorithm (operation) | Level | Done | Time Complexity | Space Complexity | Tests passed: |
---|---|---|---|---|---|
Buble Sort <T> | 🍏 |
✔️ |
⭕️(N^2) |
⭕️(1) |
[🆗 ] Open |
Quick Sort | 🍊 |
✔️ |
⭕️(N log(N)) |
⭕️(log(N)) |
[🆗 ] Open |
MergeSort | 🍏 |
✔️ |
⭕️(N log(N)) |
⭕️(N) |
[🆗 ] Open |
Insertion Sort | 🍏 |
✔️ |
⭕️(N^2) |
⭕️(1) |
[🆗 ] Open |
The Matrix
class provides the following algorithms:
Algorithm (operation) | Level | Done | Time Complexity | Space Complexity | Tests passed: |
---|---|---|---|---|---|
rotate | 🍊 |
✔️ |
⭕️(N^2) |
⭕️(1) |
[🆗 ] Open |
transpose | 🍊 |
✔️ |
⭕️(N^2) |
⭕️(1) |
[🆗 ] Open |
reflect | 🍊 |
✔️ |
⭕️(N^2) |
⭕️(1) |
[🆗 ] Open |
The SinglyLinkedList
class provides the following algorithms:
Algorithm (operation) | Level | Done | Time Complexity | Space Complexity | Tests passed: |
---|---|---|---|---|---|
append(data) | 🍏 |
✔️ |
⭕️(1) |
⭕️(1) |
[🆗 ] Open |
preppend(data) | 🍏 |
✔️ |
⭕️(N) |
⭕️(1) |
[🆗 ] Open |
find(data) | 🍏 |
✔️ |
⭕️(N) |
⭕️(1) |
[🆗 ] Open |
deleteFirst() | 🍏 |
✔️ |
⭕️(N) |
⭕️(1) |
[🆗 ] Open |
deleteLast() | 🍏 |
✔️ |
⭕️(N) |
⭕️(1) |
[🆗 ] Open |
deletePos(position) | 🍏 |
✔️ |
⭕️(N) |
⭕️(1) |
[🆗 ] Open |
length() | 🍏 |
✔️ |
⭕️(N) |
⭕️(1) |
[🆗 ] Open |
reverse() | 🍏 |
✔️ |
⭕️(N^2) |
⭕️(N) |
[🆗 ] Open |
getMid(LinkedList) | 🍏 |
✔️ |
⭕️(N) |
⭕️(1) |
[🆗 ] Open |
merge(LinkedList, LinkedList) | 🍊 |
✔️ |
⭕️(N+M) |
⭕️(1) |
[🆗 ] Open |
sort() | 🍊 |
✔️ |
⭕️(N log(N)) |
⭕️(log(N)) |
[🆗 ] Open |
The DoublyLinkedList
class provides the following algorithms:
Algorithm (operation) | Level | Done | Time Complexity | Space Complexity | Tests passed: |
---|---|---|---|---|---|
append(data) | 🍏 |
✔️ |
⭕️(1) |
⭕️(1) |
[🆗 ] Open |
preppend(data) | 🍏 |
✔️ |
⭕️(1) |
⭕️(1) |
[🆗 ] Open |
deleteFirst() | 🍏 |
✔️ |
⭕️(1) |
⭕️(1) |
[🆗 ] Open |
deleteLast() | 🍏 |
✔️ |
⭕️(1) |
⭕️(1) |
[🆗 ] Open |
The BinarySearchArray
class provides the following algorithms:
Algorithm (operation) | Level | Done | Time Complexity | Space Complexity | Tests passed |
---|---|---|---|---|---|
Binary Search Iterative | 🍊 |
✔️ |
⭕️(log(N)) |
⭕️(1) |
[🆗 ] Open |
Binary Search Recursive | 🍊 |
✔️ |
⭕️(log(N)) |
⭕️(log(N)) |
[🆗 ] Open |
The Stack
class provides the following algorithms:
Algorithm (operation) | Level | Done | Time Complexity | Space Complexity | Tests passed |
---|---|---|---|---|---|
getMin() | 🍏 |
✔️ |
⭕️(N) |
⭕️(1) |
[🆗 ] Open |
peek() | 🍏 |
✔️ |
⭕️(1) |
⭕️(1) |
[🆗 ] Open |
pop() | 🍏 |
✔️ |
⭕️(1) |
⭕️(1) |
[🆗 ] Open |
push(data) | 🍏 |
✔️ |
⭕️(1) |
⭕️(1) |
[🆗 ] Open |
The Queue
class provides the following algorithms:
Algorithm (operation) | Level | Done | Time Complexity | Space Complexity | Tests passed |
---|---|---|---|---|---|
isEmpty() | 🍏 |
✔️ |
⭕️(1) |
⭕️(1) |
[🆗 ] Open |
peek() | 🍏 |
✔️ |
⭕️(1) |
⭕️(1) |
[🆗 ] Open |
enqueue() | 🍏 |
✔️ |
⭕️(N) |
⭕️(1) |
[🆗 ] Open |
dequeue() | 🍏 |
✔️ |
⭕️(N) |
⭕️(1) |
[🆗 ] Open |
The BinaryHeap
class provides the following algorithms:
Algorithm (operation) | Level | Done | Time Complexity | Space Complexity | Tests passed |
---|---|---|---|---|---|
insert() | 🍎 |
✔️ |
⭕️(log(N)) |
⭕️(1) |
[🆗 ] Open |
delete(index) | 🍎 |
✔️ |
⭕️(log(N)) |
⭕️(1) |
[🆗 ] Open |
sort() | 🍎 |
✔️ |
⭕️(N log(N)) |
⭕️(1) |
[🆗 ] Open |
fixHeapAbove(index) | 🍎 |
✔️ |
⭕️(log(N)) |
⭕️(1) |
|
fixHeapAbove(index, lastHeapIndex) | 🍎 |
✔️ |
⭕️(log(N)) |
⭕️(1) |
The Tree
class provides the following algorithms:
Algorithm (operation) | Level | Done | Big ⭕️ Notation | Tests passed |
---|---|---|---|---|
Binary Tree Recursive: insert(data) | 🍎 |
✔️ |
⭕️log(N) |
[🆗 ] Open |
Binary Tree Recursive: preOrderPrint() | 🍎 |
✔️ |
⭕️log(N) |
[🆗 ] Open |
Binary Tree Recursive: inOrderPrint() | 🍎 |
✔️ |
⭕️log(N) |
[🆗 ] Open |
Binary Tree Recursive: postOrderPrint() | 🍎 |
✔️ |
⭕️log(N) |
[🆗 ] Open |
Binary Tree Recursive: find(data) | 🍎 |
✔️ |
⭕️log(N) |
[🆗 ] Open |
Binary Tree Recursive: delete() | 🍎 |
✔️ |
⭕️log(N) |
[🆗 ] Open |
Binary Tree Iterative: insert(data) | 🍎 |
✔️ |
⭕️(N) |
[🆗 ] Open |
Binary Tree Iterative: preOrderPrint() | 🍎 |
✔️ |
⭕️(N) |
[🆗 ] Open |
Binary Tree Iterative: inOrderPrint() | 🍎 |
✔️ |
⭕️(N) |
[🆗 ] Open |
Binary Tree Iterative: postOrderPrint() | 🍎 |
✔️ |
⭕️(N) |
[🆗 ] Open |
AVL Tree | 🍎 |
[✍🏻 ] |
||
Fenwick Tree | 🍎 |
[✍🏻 ] |
||
Red-Black Tree | 🍎 |
[✍🏻 ] |
||
Segment Tree | 🍎 |
[✍🏻 ] |
Data Structure: Hash Table<Listnode>
Algorithm (operation) | Level | Done | Big ⭕️ Notation |
---|---|---|---|
hash(key) | 🍏 |
[✍🏻 ] |
|
set(key, value) | 🍏 |
[✍🏻 ] |
|
delete(key) | 🍏 |
[✍🏻 ] |
|
get(key) | 🍏 |
[✍🏻 ] |
|
has(key) | 🍏 |
[✍🏻 ] |
|
getKeys() | 🍏 |
[✍🏻 ] |
|
getValues() | 🍏 |
[✍🏻 ] |
Data Structure: Trie
Algorithm (operation) | Level | Done | Big ⭕️ Notation |
---|---|---|---|
addWord | 🍎 |
[✍🏻 ] |
|
deleteWord | 🍎 |
[✍🏻 ] |
Data Structure: Graph
Algorithm (operation) | Level | Done | Big ⭕️ Notation |
---|---|---|---|
directed | 🍎 |
[✍🏻 ] |
|
undirected | 🍎 |
[✍🏻 ] |
mvn clean test