🧠 📚 ⏱ Java Common Data Structures and Algorithms

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.

Notation keys

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;

Data Structures:

The following data structures are implemented in this repository:

Arrays

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

Sorting

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

Matrix

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

Singly Linked List

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

Doubly Linked List

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

Binary Search

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

Stack<SinglyLinkedList Node>

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

Queue<int[]>

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

Binary Heap

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

Tree

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
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	`🍎`	[`✍🏻`]

🛠 Use Tests:

mvn clean test

Autor

meugenom

meugenom/java-common-algorithms