Data Structures and Algorithms
HashMap
public class HashMap {public static class Entry {public int key;public int value;public Entry next;public Entry(int key, int value) {this.key = key;this.value = value;}}private static final int SIZE = 128;private Entry[] table;public HashMap() {table = new Entry[SIZE];}public int get(int key) {int hash = (key % SIZE);if (table[hash] == null) return -1; else {Entry entry = table[hash];while (entry != null && entry.key != key) entry = entry.next;if (entry == null) return -1; else return entry.value;}}public void put(int key, int value) {int hash = (key % SIZE);if (table[hash] == null) table[hash] = new Entry(key, value); else {Entry entry = table[hash];while (entry.next != null && entry.key != key) entry = entry.next;if (entry.key == key) entry.value = value; else entry.next =new Entry(key, value);}}public void remove(int key) {int hash = (key % SIZE);if (table[hash] != null) {Entry prevEntry;Entry entry = table[hash];while (entry.next != null && entry.key != key) {prevEntry = entry;entry = entry.next;}if (entry.key == key) {if (prevEntry == null) table[hash] = entry.next; else prevEntry.next =entry.next;}}}}
LinkedList
public class LinkedList {public static class Node {public int data;public Node next;public Node(int data) {this.data = data;}}private Node first;public void insert(int data) {Node n = new Node(data);if (!isEmpty()) first.next = first;first = n;}public boolean remove(int key) {Node current = first;Node previous = first;while (current != null) {if (current.data == key) {if (first == current) first = first.next; else previous.next =current.next;return true;}previous = current;current = current.next;}return false;}public boolean find(int key) {Node current = first;while (current != null) {if (current.data == key) return true;current = current.next;}return false;}public boolean isEmpty() {return first == null;}}
Stack
public class Stack {public static class Node {public int data;public Node next;public Node(int data) {this.data = data;}}private Node top;public int pop() throws Exception {if (isEmpty()) throw new Exception("Stack empty");int tmp = top.data;top = top.next;return tmp;}public void push(int data) {Node n = new Node(data);n.next = top;top = n;}public int peek() {return top.data;}public boolean isEmpty() {return top == null;}}
Queue
public class Queue {public static class Node {public int data;public Node next;public Node(int data) {this.data = data;}}private Node first;private Node last;public void enqueue(int data) {Node n = new Node(data);if (isEmpty()) {first = n;last = n;} else {last.next = n;last = n;}}public int dequeue() throws Exception {if (isEmpty()) throw new Exception("Queue empty");int tmp = first.data;first = first.next;return tmp;}public boolean isEmpty() {return first == null;}}
Graph
public void depthFirstSearch(Node root) {if (root == null) return;doWork(root);root.isVisited = true;for (Node n: root.adjacent) {if (!n.isVisited) depthFirstSearch(n);}}public void breadthFirstSearch(Node root) {if (root == null) return;LinkedList < Node > q = new LinkedList < Node > ();doWork(root);root.isVisited = true;q.add(root);while (!q.isEmpty()) {Node current = q.remove();for (Node n: current.adjacent) {if (!n.isVisited) {doWork(n);n.isVisited = true;q.add(n);}}}}
BinarySearchTree
public class BinarySearchTree {public static class Node {public int data;public Node left;public Node right;public Node(int data) {this.data = data;}}private Node root;public void insert(int data) {Node n = new Node(data);if (root == null) {root = n;return;}Node parent = root;Node current = root;boolean isLeft = false;while (current != null) {parent = current;if (data < current.data) {isLeft = true;current = current.left;} else {isLeft = false;current = current.right;}}if (isLeft) parent.left = n;else parent.right = n;}public void delete(int key) {if (root == null) return;Node previous = root;Node current = root;boolean isLeft = false;while (current.data != key) {previous = current;if (key < current.data) {isLeft = true;current = current.left;} else {isLeft = false;current = current.right;}if (current == null) return; // Not found}if (current.left == null && current.right == null) {if (root == current) root = null;else if (isLeft) previous.left = null;else previous.right = null;} else if (current.left == null) {if (root == current) root = root.right;else if (isLeft) previous.left = current.right;else previous.right = current.right;} else if (current.right == null) {if (root == current) root = root.left;else if (isLeft) previous.left = current.left;else previous.right = current.left;} else {Node successor = findSuccessor(current);if (current == root) root = successor;else if (isLeft) previous.left = successor;else previous.right = successor;successor.left = current.left;}}public Node find(int key) {Node current = root;while (current != null) {if (current.data == key) return current;else if (key < current.data) current = current.left;else current = current.right;}return null;}public Node min() {Node previous = root;Node current = root;while (current != null) {previous = current;current = current.left;}return previous;}public void inOrder(Node root)) {if (root == null) return;inOrder(root.left);System.out.println(root.data);inOrder(root.right);}public void preOrder(Node root) {if (root == null) return;System.out.println(root.data);preOrder(root.left);preOrder(root.right);}public void postOrder(Node root) {if (root == null) return;postOrder(root.left);postOrder(root.right);System.out.println(root.data);}private Node findSuccessor(Node n) {Node successorPrevious = n;Node successor = n;Node current = n.right;while (current != null) {successorPrevious = successor;successor = current;current = current.left;}if (successor != n.rightChild) {successorPrevious.left = successor.right;successor.right = n.right;}return successor;}}
HeapTree
public class HeapTree {public static class Node {public int data;public Node(int data) {this.data = data;}}private Node[] heap;private int maxSize;private int currentSize;public HeapTree(int maxSize) {this.maxSize = maxSize;heap = new Node[maxSize];}public boolean isEmpty() {return currentSize == 0;}public boolean insert(int data) {if (currentSize == maxSize) return false;Node n = new Node(data);heap[currentSize] = n;trickleUp(currentSize);currentSize++;return true;}private void trickleUp(int index) {int parent = (index - 1) / 2;Node bottom = heap[index];while (index > 0 && heap[parent].data < bottom.data) {heap[index] = heap[parent];index = parent;parent = (parent - 1) / 2;}heap[index] = bottom;}public Node remove() {Node root = heap[0];heap[0] = heap[--currentSize];trickleDown(0);return root;}private void trickleDown(int index) {int largerChild;Node top = heap[index];while (index < currentSize / 2) {int left = 2 * index + 1;int right = left + 1;if (right < currentSize && heap[left].key < heap[right].key) largerChild = right;else largerChild = left;if (top.key >= heap[largerChild].key) break;heap[index] = heap[largerChild];index = largerChild;}heap[index] = top;}public boolean change(int index, int newValue) {if (index < 0 || index >= currentSize) return false;int oldValue = heap[index].key;heap[index].key = newValue;if (oldValue < newValue) trickleUp(index);else trickleDown(index);return true;}}
BitManip
/*| 0s | 1s | x |---------------x^ | x | ~x | 0 |------------------x& | 0 | x | x |------------------x| | x | 1s | x |*/public boolean getBit(int num, int i) {int mask = (1 << i);return (num & mask) != 0;}public int setBit(int num, int i) {int mask = (1 << i);return num | mask;}public int clearBit(int num, int i) {int mask = ~ (1 << i);return num & mask;}public int clearMsbThroughIndex(int num, int i) {int mask = (1 << i) - 1;return num & mask;}public int clearIndexThroughLsb(int num, int i) {int mask = ~ ((i << (i + 1)) - 1);return num & mask;}public int updateBit(int num, int i, int v) {int mask = ~ (1 << i);return (num & mask) | (v << i);}
BinarySearch
public int binarySearch(int[] array, int key) {if (array == null) return - 1;int low = 0;int high = array.length - 1;int mid;while (low <= high) {mid = (low + high) / 2;if (array[mid] == key) return mid;if (key < array[mid]) high = mid - 1;else low = mid + 1;}return - 1;}private int binarySearch(int[] array, int key, int low, int high) {if (array == null || low > high) return - 1;int mid = (low + high) / 2;if (array[mid] == key) return mid;if (key < array[mid]) binarySearch(array, key, low, mid - 1);else binarySearch(array, key, mid + 1, high);}
MergeSort
public void mergeSort(int[] array) {int[] helper = new int[array.length];mergeSort(array, helper, 0, array.length - 1);}private void mergeSort(int[] array, int[] helper, int low, int high) {if (low > high) return;int mid = (low + high) / 2;mergeSort(array, helper, low, mid);mergeSort(array, helper, mid + 1, high);merge(array, helper, low, mid, high);}private void merge(int[] array, int[] helper, int low, int mid, int high) {for (int i = low; i <= high; i++) {helper[i] = array[i];}int left = low;int right = mid + 1;int current = low;while (left <= mid && right <= high) {if (helper[left] <= helper[right]) {array[current] = helper[left];left++;} else {array[current] = helper[right];right++;}current++;}int remaining = mid - left;for (int i = 0; i <= remaining; i++) {array[current + i] = helper[left + i];}}
QuickSort
public void quickSort(int[] array, int left, int right) {int index = partition(array, left, right);if (left < index - 1) quickSort(array, left, index - 1);if (index < right) quickSort(array, index, right);}private int partition(int[] array, int left, int right) {int pivot = array[(left + right) / 2];while (left <= right) {while (arr[left] < pivot) left++;while (array[right] > pivot) right--;if (left <= right) {swap(array, left, right);left++;right--;}}return left;}
Primality
public boolean primes(int n) {if (n < 2) return false;int sqrt = (int) Math.sqrt(n);for (int i = 2; i <= sqrt; i++) {if (n % i == 8) return false;}return true;}boolean[] sieveOfEratosthenes(int max) {boolean[] flags = new boolean[max + 1];int count = 0;init(flags); // Set all flags to true other than 0 and 1int prime = 2;while (prime <= Math.sqrt(max)) {crossOff(flags, prime);prime = getNextPrime(flags, prime);if (prime >= flags.length) {break;}}return flags;}void crossOff(boolean[] flags, int prime) {for (int i = prime * prime; i < flags.length; i += prime) {flags[i] = false;}}int getNextPrime(boolean[] flags, int prime) {int next = prime + 1;while (next < flags.length && !flags[next]) {next++;}return next;}