Rocky Warren

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 1
int 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;
}

Stay up to date

Get notified when I publish. Unsubscribe at any time.