BIG O
It measures time complexity and space complexity of algorithms.
- Time complexity is measured based on how many steps an algorithm executes to finish its work.
- Space complexity is measured based on how many space in memory a data algorithm occupies.
Types of Big O Measurement
- Omega
- Theta
- Omacron aka O as in Big O
[1,2,3,4,5,6,7]
e.g. to check the time complexty for an array of 7 elements, we would use a for loop so
in this case, If looking for number 1, this is our best case (Omega), number 7 would be the worst (O) case and average case would be number 4 (theta).
Big-O Graph
Balanced Brackets
The code checks if a string of brackets is balanced by utilizing a stack data structure to match opening and closing brackets, following the Last-In-First-Out (LIFO) principle, and efficiently determining if the brackets are properly matched or not.
import java.util.List;
import java.util.Stack;
public class Brackets {
public static void main(String[] argh) {
List<String> values = List.of("((()))",
"[]{}(){()}((())){{{}{()()}{{}{",
"[[]][][]", "{}");
for (String s : values) {
System.out.println(check(s));
}
}
public static boolean check(String input) {
Stack<Character> stack = new Stack<>();
if (input.startsWith("") || input.startsWith("]]")
|| input.startsWith("))")
|| input.length() % 2 != 0) {
return false;
}
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
switch (c) {
case '{':
case '[':
case '(':
stack.push(c);
break;
case '}':
if (stack.isEmpty() || stack.pop() != '{') {
return false;
}
break;
case ')':
if (stack.isEmpty() || stack.pop() != '(') {
return false;
}
break;
case ']':
if (stack.isEmpty() || stack.pop() != '[') {
return false;
}
break;
}
}
return stack.size() == 0;
}
}
Linear Searching
Linear search method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. Linear search has a time complexity of O(n)
public class LinearSearch {
public static void main(String[] args) {
int a[] = {11, 24, 37, 49, 510};
System.out.println(hasElement(a, 11));
}
private static boolean hasElement(int items[], int elem) {
for (int i = 0; i < items.length; i++) {
if (items[i] == elem) {
return true;
}
}
return false;
}
}
Binary Search Tree
A Binary Search Tree (BST) is a data structure in which each node has at most two children, referred to as the left child and the right child, and each node represents a value, with all values in the left subtree being less than the node's value and all values in the right subtree being greater, allowing for efficient searching, insertion, and deletion of nodes with an average time complexity of O(log n), making it a fundamental data structure in computer science.
public class Main {
public static void main(String[] args) {
BinarySearchTree myBST = new BinarySearchTree();
myBST.insert(47);
myBST.insert(21);
myBST.insert(76);
myBST.insert(18);
myBST.insert(27);
myBST.insert(52);
myBST.insert(82);
System.out.println("BST Contains 27:");
System.out.println(myBST.contains(27));
System.out.println("\nBST Contains 17:");
System.out.println(myBST.contains(17));
}
}
class BinarySearchTree {
private Node root;
class Node {
public int value;
public Node left;
public Node right;
Node(int value) {
this.value = value;
}
}
public boolean insert(int value) {
Node newNode = new Node(value);
if (root == null) {
root = newNode;
return true;
}
Node temp = root;
while (true) {
if (newNode.value == temp.value) return false;
if (newNode.value < temp.value) {
if (temp.left == null) {
temp.left = newNode;
return true;
}
temp = temp.left;
} else {
if (temp.right == null) {
temp.right = newNode;
return true;
}
temp = temp.right;
}
}
}
public boolean contains(int value) {
if (root == null) return false;
Node temp = root;
while (temp != null) {
if (value < temp.value) {
temp = temp.left;
} else if (value > temp.value) {
temp = temp.right;
} else {
return true;
}
}
return false;
}
}
Binary Search Tree - Recursive
public class Main {
public static void main(String[] args) {
BinarySearchTree myBST = new BinarySearchTree();
myBST.rInsert(47);
myBST.rInsert(21);
myBST.rInsert(76);
myBST.rInsert(18);
myBST.rInsert(27);
myBST.rInsert(52);
myBST.rInsert(82);
myBST.rInsert(3);
System.out.println("BST Contains 57:");
System.out.println(myBST.rContains(57));
System.out.println("\nBST Contains 52:");
System.out.println(myBST.rContains(52));
System.out.println("\nBST Contains 3:");
System.out.println(myBST.rContains(3));
myBST.rDelete(3);
System.out.println("\nBST Min Value:");
System.out.println(myBST.minValue(myBST.root));
}
}
class BinarySearchTree {
public Node root;
class Node {
public int value;
public Node left;
public Node right;
Node(int value) {
this.value = value;
}
}
private boolean rContains(Node currentNode, int value) {
if (currentNode == null) return false;
if (currentNode.value == value) return true;
if (value < currentNode.value) {
return rContains(currentNode.left, value);
} else {
return rContains(currentNode.right, value);
}
}
private Node rInsert(Node currentNode, int value) {
if (currentNode == null) return new Node(value);
if (value < currentNode.value) {
currentNode.left = rInsert(currentNode.left, value);
} else if (value > currentNode.value) {
currentNode.right = rInsert(currentNode.right, value);
}
return currentNode;
}
public int minValue(Node currentNode) {
while(currentNode.left != null) {
currentNode = currentNode.left;
}
return currentNode.value;
}
private Node deleteNode(Node currentNode, int value) {
if (currentNode == null) return null;
if (value < currentNode.value) {
currentNode.left = deleteNode(currentNode.left, value);
} else if (value > currentNode.value) {
currentNode.right = deleteNode(currentNode.right, value);
} else {
if (currentNode.left == null && currentNode.right == null) {
return null;
} else if (currentNode.left == null) {
currentNode = currentNode.right;
} else if (currentNode.right == null) {
currentNode = currentNode.left;
} else {
int subTreeMin = minValue(currentNode.right);
currentNode.value = subTreeMin;
currentNode.right = deleteNode(currentNode.right, value);
}
}
return currentNode;
}
public void rDelete(int value) {
deleteNode(root, value);
}
public boolean rContains(int value) {
return rContains(root, value);
}
public void rInsert(int value) {
if (root == null) {
root = new Node(value);
}
rInsert(root, value);
}
}
Binary Search
Binary Search is an efficient algorithm for finding an element in a sorted array or list by repeatedly dividing the search interval in half and searching for the element in one of the two halves, resulting in a time complexity of O(log n), making it much faster than linear search for large datasets, and is particularly useful for searching in sorted arrays, databases, and file systems, where the data is already organized in a specific order.
public class BinarySearch {
public static void main(String[] args) {
int[] items = {11, 24, 37, 49, 510};
System.out.println(binarySearch(items, 24));
}
private static int binarySearch(int items[], int elem) {
int lowIndex = 0;
int highIndex = items.length;
for (int i = 0; i < items.length; i++) {
int middleIndex = (int) Math.floor((lowIndex + highIndex) / 2);
if (items[middleIndex] == elem) {
return middleIndex;
} else if (elem > items[middleIndex]) {
lowIndex = middleIndex;
} else {
highIndex = middleIndex;
}
}
return -1;
}
}
Linked Lists
A linked-list is a sequence of data structures which are connected together via links. It contains a head which represents the first element in the list and a tail which contains the last element.
The value represents the data itself and the next is a pointer to the next node in the list. If next is null, this represents the end of the list.
LinkedList.java
class LinkedList {
private Node head;
private Node tail;
private int length;
class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}
public LinkedList(int value) {
Node newNode = new Node(value);
head = newNode;
tail = newNode;
length = 1;
}
public void printList() {
Node temp = head;
while (temp != null) {
System.out.println(temp.value);
temp = temp.next;
}
}
public void getHead() {
if (head == null) {
System.out.println("Head: null");
} else {
System.out.println("Head: " + head.value);
}
}
public void getTail() {
if (head == null) {
System.out.println("Tail: null");
} else {
System.out.println("Tail: " + tail.value);
}
}
public void getLength() {
System.out.println("Length: " + length);
}
public void append(int value) {
Node newNode = new Node(value);
if (length == 0) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
length++;
}
public Node removeLast() {
if (length == 0) return null;
Node temp = head;
Node pre = head;
while(temp.next != null) {
pre = temp;
temp = temp.next;
}
tail = pre;
tail.next = null;
length--;
if (length == 0) {
head = null;
tail = null;
}
return temp;
}
public void prepend(int value) {
Node newNode = new Node(value);
if (length == 0) {
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head = newNode;
}
length++;
}
public Node removeFirst() {
if (length == 0) return null;
Node temp = head;
head = head.next;
temp.next = null;
length--;
if (length == 0) {
tail = null;
}
return temp;
}
public Node get(int index) {
if (index < 0 || index >= length) return null;
Node temp = head;
for(int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
}
public boolean set(int index, int value) {
Node temp = get(index);
if (temp != null) {
temp.value = value;
return true;
}
return false;
}
public boolean insert(int index, int value) {
if (index < 0 || index > length) return false;
if (index == 0) {
prepend(value);
return true;
}
if (index == length) {
append(value);
return true;
}
Node newNode = new Node(value);
Node temp = get(index - 1);
newNode.next = temp.next;
temp.next = newNode;
length++;
return true;
}
public Node remove(int index) {
if (index < 0 || index >= length) return null;
if (index == 0) return removeFirst();
if (index == length - 1) return removeLast();
Node prev = get(index - 1);
Node temp = prev.next;
prev.next = temp.next;
temp.next = null;
length--;
return temp;
}
}
Main.java
public class Main {
public static void main(String[] args) {
LinkedList myLinkedList = new LinkedList(1);
myLinkedList.append(2);
myLinkedList.append(3);
myLinkedList.append(4);
myLinkedList.append(5);
System.out.println("LL before remove():");
myLinkedList.printList();
System.out.println("\nRemoved node:");
System.out.println(myLinkedList.remove(2).value);
System.out.println("LL after remove() in middle:");
myLinkedList.printList();
System.out.println("\nRemoved node:");
System.out.println(myLinkedList.remove(0).value);
System.out.println("LL after remove() of first node:");
myLinkedList.printList();
System.out.println("\nRemoved node:");
System.out.println(myLinkedList.remove(2).value);
System.out.println("LL after remove() of last node:");
myLinkedList.printList();
}
}
Doubly Linked Lists
A Doubly Linked List is a data structure in which each node has two pointers, one pointing to the previous node (prev) and one pointing to the next node (next), allowing for efficient traversal in both forward and backward directions, and enabling operations such as insertion and deletion at any position in the list with a time complexity of O(1), making it a versatile and efficient data structure for applications that require frequent insertion and deletion of nodes.
public class DoublyLinkedList {
private Node head;
private Node tail;
private int length;
class Node {
int value;
Node next;
Node prev;
Node(int value) {
this.value = value;
}
}
public DoublyLinkedList(int value) {
Node newNode = new Node(value);
head = newNode;
tail = newNode;
length = 1;
}
public void printList() {
Node temp = head;
while (temp != null) {
System.out.println(temp.value);
temp = temp.next;
}
}
public void getHead() {
if (head == null) {
System.out.println("Head: null");
} else {
System.out.println("Head: " + head.value);
}
}
public void getTail() {
if (head == null) {
System.out.println("Tail: null");
} else {
System.out.println("Tail: " + tail.value);
}
}
public void getLength() {
System.out.println("Length: " + length);
}
public void append (int value) {
Node newNode = new Node(value);
if(length == 0) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
length++;
}
public Node removeLast() {
if(length == 0) return null;
Node temp = tail;
if (length == 1) {
head = null;
tail = null;
} else {
tail = tail.prev;
tail.next = null;
temp.prev = null;
}
length--;
return temp;
}
public void prepend(int value) {
Node newNode = new Node(value);
if(length == 0) {
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
length++;
}
public Node removeFirst() {
if(length == 0) return null;
Node temp = head;
if(length == 1) {
head = null;
tail = null;
} else {
head = head.next;
head.prev = null;
temp.next = null;
}
length--;
return temp;
}
public Node get(int index) {
if (index < 0 || index >= length) return null;
Node temp = head;
if (index < length/2) {
for (int i = 0; i < index; i++) {
temp = temp.next;
}
} else {
temp = tail;
for (int i = length - 1; i > index; i--) {
temp = temp.prev;
}
}
return temp;
}
public boolean set(int index, int value) {
Node temp = get(index);
if(temp != null) {
temp.value = value;
return true;
}
return false;
}
public boolean insert(int index, int value) {
if(index < 0 || index > length) return false;
if(index == 0) {
prepend(value);
return true;
}
if(index == length) {
append(value);
return true;
}
Node newNode = new Node(value);
Node before = get(index - 1);
Node after = before.next;
newNode.prev = before;
newNode.next = after;
before.next = newNode;
after.prev = newNode;
length++;
return true;
}
public Node remove(int index) {
if(index < 0 || index >= length) return null;
if(index == 0) return removeFirst();
if(index == length - 1) return removeLast();
Node temp = get(index);
temp.next.prev = temp.prev;
temp.prev.next = temp.next;
temp.next = null;
temp.prev = null;
length--;
return temp;
}
}
Main.java
public class Main {
public static void main(String[] args) {
DoublyLinkedList myDLL = new DoublyLinkedList(1);
myDLL.append(2);
myDLL.append(3);
myDLL.append(4);
myDLL.append(5);
System.out.println("DLL before remove():");
myDLL.printList();
System.out.println("\nRemoved node:");
System.out.println(myDLL.remove(2).value);
System.out.println("DLL after remove() in middle:");
myDLL.printList();
System.out.println("\nRemoved node:");
System.out.println(myDLL.remove(0).value);
System.out.println("DLL after remove() of first node:");
myDLL.printList();
System.out.println("\nRemoved node:");
System.out.println(myDLL.remove(2).value);
System.out.println("DLL after remove() of last node:");
myDLL.printList();
}
}
Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly iterates through a list of elements, comparing adjacent elements and swapping them if they are in the wrong order, with the largest element "bubbling" to the end of the list with each iteration, resulting in a sorted list after multiple passes, with a time complexity of O(n^2), making it less efficient than other sorting algorithms like quicksort or merge sort, but still useful for small datasets or educational purposes.
public class BubbleSort {
public static void main(String[] args) {
int[] items = {9, 3, 72, 101, 12, 65, 1, 6, 57, 5, 2};
bubbleSort(items);
for (int i = 0; i < items.length; i++) {
System.out.println(items[i]);
}
}
public static void bubbleSort(int[] array) {
boolean isSorted = false;
int lastUnsorted = array.length - 1;
while(!isSorted) {
isSorted = true;
for(int i = 0; i <= lastUnsorted - 1; i++) {
if(array[i] > array[i + 1]) {
swap(array, i, i + 1);
isSorted = false;
}
}
lastUnsorted--;
}
}
public static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
Hash Tables
Hash tables are a data structure that use a hash function to map keys to their corresponding values. The hash function takes a key as input and returns an index or address in the hash table where the value associated with that key is stored. This allows for constant-time average-case lookup, insertion, and deletion of key-value pairs. Hash tables are commonly used in a variety of applications that require efficient lookup, such as caching, databases, and compilers. The main tradeoff with hash tables is that they require additional memory to store the hash table itself, and can suffer from collisions where multiple keys hash to the same index, requiring additional handling to resolve.
A hash table contains two main functions: put() and get(). put() is used for storing data into the hash table, while get() is used for retrieving data from the hash table. There's another important function which is called hash function. It converts a specific key to an array index where the values are stored.
One technique that os commonly used to generate a key index is using modulus operator on a prime number e.g
- 4 % 11 = 4
- 7 % 11 = 7
- 9 % 11 = 9
- 15 % 11 = 4
But this technique can cause a key collision as you can see on item 4 15 % 11 = 4
It's possible to avoid these collisions using one of the three strategies below:
1 - Linear Probing
It finds the next empty index in the array using linear search.
2 - Quadratic Probing
Quadratic probing uses perfect squares instead of incrementing by 1 each time. h + (1)^2, h + (2)^2, h + (3)^2, h + (4)^2
3 - Rehashing / Double-Hashing
This uniformly distribute the keys by having a second hashing function that hashes the result from the original.
hash2(x) = R − (x % R)
x is the result from hashing the first time, and R is less than the size of the hash table.
Examples
Linear Probing
public class HashTable {
int size;
int[] keys;
int[] values;
int limit;
public HashTable(int size) {
this.size = size;
this.keys = initArray();
this.values = initArray();
this.limit = 0;
}
public void put(int key, int value) throws Exception {
if (this.limit > this.size) {
throw new Exception("Table is full");
}
int hashedIndex = this.hash(key);
while (this.keys[hashedIndex] != 0) {
hashedIndex++;
hashedIndex = hashedIndex + this.size;
}
this.keys[hashedIndex] = key;
this.values[hashedIndex] = value;
this.limit++;
}
public int get(int key) {
var hashedIndex = this.hash(key);
while (this.keys[hashedIndex] != key) {
hashedIndex++;
hashedIndex = hashedIndex % this.size;
}
return this.values[hashedIndex];
}
public int hash(int key) {
return key % this.size;
}
public int[] initArray() {
int[] arr = new int[this.size];
for (var i = 0; i < this.size; i++) {
arr[i] = 0;
}
return arr;
}
public static void main(String[] args) throws Exception {
HashTable ht = new HashTable(4);
ht.put(7, 1);
ht.put(20, 2);
ht.put(33, 3);
ht.put(46, 4);
for (int i = 0; i < ht.size; i++) {
System.out.println(ht.keys[i]);
System.out.println(ht.values[i]);
}
}
}
Quadratic Probing
import java.util.Arrays;
public class HashTable {
int size;
int[] keys;
int[] values;
int limit;
public HashTable(int size) {
this.size = size;
this.keys = initArray();
this.values = initArray();
this.limit = 0;
}
public void put(int key, int value) throws Exception {
if (this.limit > this.size) {
throw new Exception("Table is full");
}
int squareIndex = 1;
int hashedIndex = this.hash(key);
while (this.keys[hashedIndex] != 0) {
hashedIndex += Math.pow(squareIndex, 2);
hashedIndex++;
squareIndex++;
}
this.keys[hashedIndex] = key;
this.values[hashedIndex] = value;
this.limit++;
}
public int get(int key) {
int squareIndex = 1;
var hashedIndex = this.hash(key);
while (this.keys[hashedIndex] != key) {
hashedIndex += Math.pow(squareIndex, 2);
hashedIndex = hashedIndex % this.size;
squareIndex++;
}
return this.values[hashedIndex];
}
public int hash(int key) {
return key % this.size;
}
public int[] initArray() {
int[] arr = new int[this.size];
for (var i = 0; i < this.size; i++) {
arr[i] = 0;
}
return arr;
}
public static void main(String[] args) throws Exception {
HashTable ht = new HashTable(20);
ht.put(7, 1);
ht.put(20, 2);
ht.put(33, 3);
ht.put(46, 4);
ht.put(50, 5);
ht.put(63, 26);
ht.put(77, 17);
ht.put(91, 8);
System.out.println(Arrays.toString(ht.keys));
System.out.println(Arrays.toString(ht.values));
}
}
Rehashing / Double-Hashing
On the output you can notice the difference on the hash keys where Double-Hashing is more uniformly distributed than Quadratic Probing
import java.util.Arrays;
public class HashTable {
int size;
int[] keys;
int[] values;
int limit;
public HashTable(int size) {
this.size = size;
this.keys = initArray();
this.values = initArray();
this.limit = 0;
}
public void put(int key, int value) throws Exception {
if (this.limit > this.size) {
throw new Exception("Table is full");
}
int hashedIndex = this.hash(key);
while (this.keys[hashedIndex] != 0) {
hashedIndex++;
hashedIndex = hashedIndex % this.size;
}
this.keys[hashedIndex] = key;
this.values[hashedIndex] = value;
this.limit++;
}
public int get(int key) {
var hashedIndex = this.hash(key);
while (this.keys[hashedIndex] != key) {
hashedIndex++;
hashedIndex = hashedIndex % this.size;
}
return this.values[hashedIndex];
}
public int hash(int key) {
return this.secondHash(key % this.size);
}
public int secondHash(int key) {
var R = this.size -2;
return R - key % R;
}
public int[] initArray() {
int[] arr = new int[this.size];
for (var i = 0; i < this.size; i++) {
arr[i] = 0;
}
return arr;
}
public static void main(String[] args) throws Exception {
HashTable ht = new HashTable(20);
ht.put(7, 1);
ht.put(20, 2);
ht.put(33, 3);
ht.put(46, 4);
ht.put(50, 5);
ht.put(63, 26);
ht.put(77, 17);
ht.put(91, 8);
System.out.println(Arrays.toString(ht.keys));
System.out.println(Arrays.toString(ht.values));
}
}
Merge Sort
Merge sort is a divide-and-conquer sorting algorithm that works by recursively breaking down a list into smaller sublists until they consist of individual elements, and then merging those sublists back together in a sorted manner. The basic steps of merge sort are:
- Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
- Repeatedly merge the sublists to produce new sorted sublists until there is only 1 sublist remaining. This is the sorted list.
The merge step works by comparing the first elements of each sublist, and adding the smaller element to the new sorted list. This is repeated until all elements from the sublists have been added to the new sorted list.
The time complexity of merge sort is $O(n \log n)$, making it an efficient sorting algorithm, especially for large datasets. The main tradeoff is the additional memory required to store the temporary sublists during the merge process.
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
System.out.println("mergesort");
int[] input = { 87, 57, 370, 110, 90, 610, 02, 710, 140, 203, 150 };
System.out.println("array before sorting");
System.out.println(Arrays.toString(input));
// sorting array using MergeSort algorithm
mergesort(input);
System.out.println("array after sorting using mergesort algorithm");
System.out.println(Arrays.toString(input));
}
public static void mergesort(int[] input) {
mergesort(input, 0, input.length - 1);
}
private static void mergesort(int[] input, int start, int end) {
// break problem into smaller structurally identical problems
int mid = (start + end) / 2;
if (start < end) {
mergesort(input, start, mid);
mergesort(input, mid + 1, end);
}
// merge solved pieces to get solution to original problem
int i = 0, first = start, last = mid + 1;
int[] tmp = new int[end - start + 1];
while (first <= mid && last <= end) {
tmp[i++] = input[first] < input[last] ? input[first++] : input[last++];
}
while (first <= mid) {
tmp[i++] = input[first++];
}
while (last <= end) {
tmp[i++] = input[last++];
}
i = 0;
while (start <= end) {
input[start++] = tmp[i++];
}
}
}
Queues
A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).
public class Queue {
private static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
}
private Node head;
private Node tail;
public boolean isEmpty() {
return head == null;
}
public int peek() {
return head.data;
}
public void add(int data) {
Node node = new Node(data);
if (tail != null) {
tail.next = node;
}
tail = node;
if (head == null) {
head = node;
}
}
public int remove() {
int data = head.data;
head = head.next;
if (head == null) {
tail = null;
}
return data;
}
}
class QueueTest {
public static void main(String[] args) {
Queue queue = new Queue();
queue.add(3);
queue.add(2);
queue.add(5);
System.out.println(queue.peek());
queue.remove();
System.out.println(queue.peek());
queue.remove();
System.out.println(queue.peek());
}
}
Stacks
Stack is a data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
public class Stack {
private static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
}
private Node top;
public boolean isEmpty() {
return top == null;
}
public int peek() {
return top.data;
}
public void push(int data) {
Node node = new Node(data);
node.next = top;
top = node;
}
public int pop() {
int data = top.data;
top = top.next;
return data;
}
}
class StackTest {
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(3);
stack.push(2);
stack.push(5);
System.out.println(stack.peek());
stack.pop();
System.out.println(stack.peek());
stack.pop();
System.out.println(stack.peek());
}
}
Insertion Sort
Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands with a time Complexity of O(n2) on Big O notation.
import java.util.Arrays;
public class InsertionSort {
public static void main(String[] args) {
int[] items = {123, 3, 72, 101, 12, 65, 3, 24, 57, 93, 100};
int[] result = insertionSort(items);
Arrays.stream(result).forEach(System.out::println);
}
private static int[] insertionSort(int[] items) {
int i; // index into unsorted section
int j; // index into sorted section
for (i = 0; i < items.length; i++) {
int current = items[i];
for (j = i - 1; j > -1 && items[j] > current; j--) {
items[j + 1] = items[j];
}
items[j + 1] = current;
}
return items;
}
}
Selection Sort
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
public class SelectionSort {
public static void main(String[] args) {
int [] a = {99, 1, 77, 12, 55, 88, 23, 11, 7, 3, 2};
int [] result = selectionSort(a);
Arrays.stream(result).forEach(System.out::println);
}
private static int[] selectionSort(int items[]) {
for (int i = 0; i < items.length; i++) {
int min = i;
for (int j = i + 1; j < items.length; j++) {
if (items[j] < items[min]) {
min = j;
}
}
if (i != min) {
int swap = items[i];
items[i] = items[min];
items[min] = swap;
}
}
return items;
}
}
Quick Sort
QuickSort is a divide and conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways. This algorithm has a time complexy of O(nlog2(n)) on average and O(n2) for worst case.
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] items = {6, 1, 23, 4, 2, 3};
int[] result = quickSort(items, 0, items.length - 1);
Arrays.stream(result).forEach(System.out::println);
}
private static int[] quickSort(int[] items, int left, int right) {
int index = 0;
if (items.length > 1) {
index = partition(items, left, right);
if (left < index - 1) {
quickSort(items, left, index - 1);
}
}
if (index < right) {
quickSort(items, index, right);
}
return items;
}
private static int partition(int[] items, int left, int right) {
int pivot = items[(int) Math.floor((right + left) / 2)];
while (left <= right) {
while (pivot > items[left]) {
left++;
}
while (pivot < items[right]) {
right--;
}
if (left <= right) {
int tmp = items[left];
items[left] = items[right];
items[right] = tmp;
left++;
right--;
}
}
return left;
}
}
Tree
A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.
public class Node {
private int data;
private Node left, right;
public Node(int data) {
this.data = data;
}
public void insert(int value) {
if (value <= data) {
if (left == null) {
left = new Node(value);
} else {
left.insert(value);
}
} else {
if (right == null) {
right = new Node(value);
} else {
right.insert(value);
}
}
}
public boolean contains(int value) {
if (value == data) {
return true;
}
else if (value < data) {
if (left == null) {
return false;
} else {
return left.contains(value);
}
}
else {
if (right == null) {
return false;
} else {
return right.contains(value);
}
}
}
public void print() {
if(left != null) {
left.print();
}
System.out.println(data);
if(right != null) {
right.print();
}
}
}
class TreeTest {
public static void main(String[] args) {
Node node = new Node(10);
System.out.println(node.contains(4));
node.print();
}
}
Graphs
Graphs, as a fundamental data structure, consist of a set of vertices (or nodes) and a collection of edges that connect pairs of vertices, allowing for the representation of complex relationships and interactions. They can be implemented in various ways, such as using adjacency matrices or adjacency lists, each offering different trade-offs in terms of space and time complexity. Graphs can be classified into directed and undirected types, where directed graphs have edges with a specific direction, while undirected graphs have bidirectional edges. Additionally, graphs can be weighted, where edges carry values representing costs or distances, or unweighted, where all edges are treated equally. Common operations on graphs include traversal methods like Depth-First Search (DFS) and Breadth-First Search (BFS), as well as algorithms for finding the shortest path, such as Dijkstra's and Bellman-Ford algorithms. Due to their versatility, graphs are widely used in various applications, including network routing, social network analysis, and resource allocation.
import java.util.ArrayList;
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
Graph myGraph = new Graph();
myGraph.addVertex("A");
myGraph.addVertex("B");
myGraph.addVertex("C");
myGraph.addVertex("D");
myGraph.addEdge("A", "B");
myGraph.addEdge("A", "C");
myGraph.addEdge("A", "D");
myGraph.addEdge("B", "D");
myGraph.addEdge("C", "D");
System.out.println("\nGraph before removeVertex():");
myGraph.printGraph();
myGraph.removeVertex("D");
System.out.println("\nGraph after removeVertex():");
myGraph.printGraph();
}
}
class Graph {
private final HashMap<String, ArrayList<String>> adjList = new HashMap<>();
public void printGraph() {
System.out.println(adjList);
}
public boolean addVertex(String vertex) {
if (adjList.get(vertex) == null) {
adjList.put(vertex, new ArrayList<>());
return true;
}
return false;
}
public boolean addEdge(String vertex1, String vertex2) {
if (adjList.get(vertex1) != null && adjList.get(vertex2) != null) {
adjList.get(vertex1).add(vertex2);
adjList.get(vertex2).add(vertex1);
return true;
}
return false;
}
public boolean removeEdge(String vertex1, String vertex2) {
if (adjList.get(vertex1) != null && adjList.get(vertex2) != null) {
adjList.get(vertex1).remove(vertex2);
adjList.get(vertex2).remove(vertex1);
return true;
}
return false;
}
public boolean removeVertex(String vertex) {
if (adjList.get(vertex) == null) return false;
for (String otherVertex : adjList.get(vertex)) {
adjList.get(otherVertex).remove(vertex);
}
adjList.remove(vertex);
return true;
}
}