Algorithm and Data Structures

data_structures.java

// Linked List
class Node {
    Node next = null;
    Object data;
    Node(Object data) {
        this.data = data;
    }
}

class LinkedList {
    Node head;
    
    public void append(Object item) {
        if (head == null) {
            head = new Node(item);
        } else {
            Node n = head;
            while (n.next != null) {
                n = n.next;
            }
            n.next = new Node(item);
        }
    }

    public void delete(Object item) {
        if (head != null) {
            if (head.data.equals(item)) { // assume data is not null
                head = head.next;
            } else {
                Node n = head;
                while (n.next != null) {
                    if (n.next.data.equals(item)) {
                        n.next = n.next.next;       
                        return;
                    }
                    n = n.next;
                }
            }
        }
    }
}

// Stack and Queue
class Stack {
    Node top;

    public void push (Object item) {
        Node n = new Node(item);
        n.next = top;
        top = n;
    }

    public Object pop () {
        if (top != null) {
            Object item = top.data;
            top = top.next;
            return item;
        }
        return null;
    }

    public Node peek() {
        return top;
    }
}

class Queue() {
    Node first, last;
    
    public void enqueue(Object item) {
        if (first == null) {
            last = new Node(item);
            first = last;
        } else {
            last.next = new Node(item);
            last = last.next;
        }
    }

    public Object dequeue() {
        if (first != null) {
            Object item = first.data;
            first = first.next;
            return item;
        }
        return null;
    }
}

// Trees
class TreeNode {
    TreeNode left;
    TreeNode right;
    int key; // assume key is data

    TreeNode(int key) {
        this.key = key;
    }
}


class BinarySearchTree {
    TreeNode root;

    TreeNode findMin(TreeNode t) {
        if (t == null) {
            return null;
        } else if (t.left == null) {
            return t;
        }
        return findMin(t.left);
    }

    TreeNode add(TreeNode t, int key) {
        if (t == null) {
            t = new TreeNode(key);
        } else if (key < t.key) {
            t.left = add(t.left, key);
        } else if (key > t.key) {
            t.right = add(t.right, key);
        }
        return t;
    }

    TreeNode remove(TreeNode t, int key) {
        if (t == null) return t;
        if (t.key < key) {
            t.left = remove(t.left, key);
        } else if (t.key > key) {
            t.right = remove(t.right, key);
        } else if (t.left != null && t.right != null) {
            t.key = findMin(t.right).key;
            t.right = remove(t.right, t.key);
        } else if (t.left != null) {
            t = t.left;
        } else {
            t = t.right;
        }
        return t;
    }

    void add(int key) {
        root = add(root, key);      
    }

    void remove(int key) {
        root = remove(root, key);
    }

    void inOrderTraverse(TreeNode t) {
        if (t != null) {
            inOrderTraverse(t.left);
            t.visit();
            inOrderTraverse(t.right);
        }
    }

    void preOrderTraverse(TreeNode t) {
        if (t != null) {
            t.visit();
            inOrderTraverse(t.left);
            inOrderTraverse(t.right);
        }
    }

    void postOrderTraverse(TreeNode t) {
        if (t != null) {    
            inOrderTraverse(t.left);
            inOrderTraverse(t.right);
            t.visit();
        }
    }
}

sorting.java

// bubble sort
public void bubble_sort(int[] a) {
    int n = a.length;
    boolean swapped = true;
    
    while (swapped) {
        swapped = false;
        for (int i = 0; i < n - 1; i++) {
            if (a[i] > a[i + 1]) {
                int tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                swapped = true;
            }
        }
    }
}

// insertion sort
public void insertion_sort(int[] a) {
    int n = a.length;
    int key;
    
    for (int i = 1; i < n; i++) {
        key = a[i];
        int j = i;
        while (j > 0 && a[j - 1] > key) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = key;
    }
}

// selection sort
public void selection_sort(int[] a) {
    int n = a.length;
    int m;

    for (int i = 0; i < n - 1; i++) {
        m = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[m]) {
                m = j;
            }
        }
        if (m != i) {
            int tmp = a[i];
            a[i] = a[m];
            a[m] = tmp;
        }
    }
}

// quick sort
public void quick_sort(int[] a) {
    int n = a.length;
    partition(a, 0, n - 1);
}

private int[] partition(int[] a, int begin, int end) {
    if (end - begin <= 0) return a;
    
    int i = begin, j = end, m = begin + (end - begin) / 2;
    int pivot = a[m];

    while (i != j) {
        if (a[i] >= pivot && a[j] <= pivot) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        if (a[i] < pivot)
            i++;
        if (a[j] > pivot)
            j--;
    }

    partition(a, begin, i - 1);
    partition(a, j + 1, end);

    return a;
}

// merge sort
public int[] merge_sort(int[] a) {
    return divide(a);
}

private int[] divide(int[] a) {
    int n = a.length;
    if (n == 1) return a;

    int[] a1, a2;
    if ((n % 2) == 0) {
        a1 = new int[n / 2];
        a2 = new int[n / 2];
    } else {
        a1 = new int[n / 2];
        a2 = new int[n / 2 + 1];
    }

    int j = 0;
    for (int i = 0; i < n; i++) {
        if (i < n / 2) {
            a1[i] = a[i];
        } else {
            a2[j] = a[i];
            j++;
        }
    }

    return merge(divide(a1), divide(a2));
}

private int[] merge(int[] a1, int[] a2) {
    int n1 = a1.length;
    int n2 = a2.length;
    int[] a = new int[n1 + n2];
    int i = 0, j = 0, k = 0;

    while (i < n1 || j < n2) {
        if (i < n1 && j < n2) {
            if (a1[i] < a2[j]) {
                a[k] = a1[i];
                i++;
            } else {
                a[k] = a2[j];
                j++;
            }
        } else if (i < n1) {
            a[k] = a1[i];
            i++;
        } else if (j < n2) {
            a[k] = a2[j];
            j++;
        }
        k++;
    }

    return a;
}