This table comes from page 47 in the book “Cracking the coding interview (5th ed.)”.

Data Structures Algorithms Concepts
Linked Lists Breadth First Search Bit Manipulation
Binary Trees Depth First Search Singleton Design Pattern
Tries Binary Search Factory Design Pattern
Stacks Merge Sort Memory (Stack vs. Heap)
Queues Quick Sort Recursion
Vectors/ArrayLists Tree Insert/Find/etc. Big-O Time
Hash Tables    
Heaps    

Linked Lists

The content comes from the Page 142-146 in the book “Algorithms 4th” by Sedgewick, Wayne.

For a singly linked-list:

Operations Time Complexity
insert at the beginning O(1)
remove from the beginning O(1)
insert at the end O(1) or O(n)
remove a given node O(n)
Insert a new node before a given node O(n)

Java version:

import java.util.ArrayList;
import java.util.List;

public class LinkedList<Item>
{
    private class Node
    {
        Item item;
        Node next;
    }

    private int N;
    private Node first;

    public LinkedList() {
        first = null;
        N = 0;
    }

    public void insertAtBeginning(Item item)
    {
        // save a link to the list
        Node oldfirst = first;
        // create a new node for the beginning
        first = new Node();
        // set the instance variables in the new node
        first.item = item;
        first.next = oldfirst;
        N++;
    }

    public void removeFromBeginning()
    {
        if (first == null) return;
        // remove the first node in a linked list
        first = first.next;
    }

    public void insertAtEnd(Item item)
    {
        // Time complexity: O(n)
        Node last = new Node();
        last.item = item;
        if (first == null) { first = last; return; }

        Node oldlast = first;
        while (oldlast.next != null)
            oldlast = oldlast.next;

        assert oldlast.next == null;
        oldlast.next = last;
    }

    public List<Item> array()
    {
        List<Item> items = new ArrayList<Item>();

        for (Node x = first; x != null; x = x.next)
            items.add(x.item);

        return items;
    }
}

Binary Search Tree

The content comes from the Page 396-414 in the book “Algorithms 4th” by Sedgewick, Wayne.

Worst case:

algorithm
(data structure)
search insert
sequential search
(unordered linked list)
O(N) O(N)
binary search
(ordered array)
O(lgN) O(N)
binary tree search
(BST)
O(N) O(N)

Average case:

algorithm
(data structure)
search insert support ordered
operations?
sequential search
(unordered linked list)
O(N/2) O(N) no
binary search
(ordered array)
O(lgN) O(N/2) yes
binary tree search
(BST)
O(1.39lgN) O(1.39lgN) yes

Java version:

public class BST<Key extends Comparable<Key>, Value>
{
    private Node root;

    private class Node
    {
        private Key key;
        private Value val;
        private Node left, right;
        private int N;

        public Node(Key key, Value val, int N)
        {
            this.key = key;
            this.val = val;
            this.N   = N;
        }
    }

    public int size()
    {
        return size(root);
    }

    private int size(Node x)
    {
        if (x == null) return 0;
        else           return x.N;
    }

    public Value search(Key key)
    {
        return search(root, key);
    }

    private Value search(Node x, Key key)
    {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) return search(x.left, key);
        else if (cmp > 0) return search(x.right, key);
        else return x.val;
    }

    public void insert(Key key, Value val)
    {
        root = insert(root, key, val);
    }

    private Node insert(Node x, Key key, Value val)
    {
        if (x == null) return new Node(key, val, 1);
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) x.left  = insert(x.left, key, val);
        else if (cmp > 0) x.right = insert(x.right, key, val);
        else x.val = val;
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    public Key min()
    {
        return min(root).key;
    }

    private Node min(Node x)
    {
        if (x.left == null) return x;
        return min(x.left);
    }

    public void deleteMin()
    {
        root = deleteMin(root);
    }

    private Node deleteMin(Node x)
    {
        if (x.left == null) return x.right;
        x.left = deleteMin(x.left);
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    // delete: replace x by its successor (smallest node in the right
    // subtree)
    public void delete(Key key)
    {
        root = delete(root, key);
    }

    private Node delete(Node x, Key key)
    {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) x.left  = delete(x.left, key);
        else if (cmp > 0) x.right = delete(x.right, key);
        else
        {
            if (x.right == null) return x.left;
            if (x.left == null) return x.right;
            Node t = x;
            x = min(t.right);
            x.right = deleteMin(t.right);
            x.left = t.left;
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    public static void main(String[] args)
    {
        BST<String, String> bst = new BST<String, String>();

        bst.insert("S","S");
        bst.insert("E","E");
        bst.insert("X","X");
        bst.insert("A","A");
        bst.insert("C","C");
        bst.insert("R","R");
        bst.insert("H","H");

        System.out.println(bst.search("H"));
        System.out.println(bst.size());
        bst.delete("H");
        System.out.println(bst.size());
        System.out.println(bst.search("H"));
    }
}

The content comes from Page 9 (iterative) and Page 380 (recursive) in the book “Algorithms 4th” by Sedgewick, Wayne.

Java version:

import java.util.Arrays;

public class BinarySearch
{
    public static int searchIterative(int key, int[] a)
    {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi)
        {
            int mid = lo + (hi - lo) / 2;
            if      (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else                   return mid;
        }
        return -1;
    }

    public static int searchRecursive(int key, int[] a)
    {
        return searchRecursiveHelper(key, 0, a.length-1, a);
    }

    private static int searchRecursiveHelper(int key, int lo, int hi, int[] a)
    {
        if (hi < lo) return -1;
        int mid = lo + (hi - lo) / 2;
        if      (key < a[mid]) return searchRecursiveHelper(key, lo, mid-1, a);
        else if (key > a[mid]) return searchRecursiveHelper(key, mid+1, hi, a);
        else                   return mid;
    }

    public static void main(String[] args)
    {
        int[] whitelist = new int[] {1,5,52,23,123,32,55,78,21,32};

        Arrays.sort(whitelist);

        System.out.println(searchIterative(1, whitelist));
        System.out.println(searchIterative(55, whitelist));
        System.out.println(searchIterative(32, whitelist));
        System.out.println(searchIterative(11, whitelist));

        System.out.println(searchRecursive(1, whitelist));
        System.out.println(searchRecursive(55, whitelist));
        System.out.println(searchRecursive(32, whitelist));        
        System.out.println(searchRecursive(11, whitelist));
    }
}