TEST 1 MATERIAL

Data Structures
  Java Collections and list implementations
    Collection interface, many useful static methods in Collections  
    List interface (extends Collection)
      ArrayList (implements List): underlying array representation
        O(1) add/remove at end, O(N) add/remove from beginning/middle
        O(1) access, O(N) search
      LinkedList (implements List): underlying doubly-linked list representation
        O(1) add/remove at beginning/end, O(N) add/remove from middle
        O(1) add/remove if have access to location, O(N) access/search	
    iterators
      Iterator interface: hasNext, next, remove
      ListIterator interface: hasPrevious, previous, add, set
  Sets & Maps
    Set interface (extends Collection)
      TreeSet (via balanced BST): O(log N) add/remove/search
      HashSet (via hash table): O(1) add/remove/search expected*, O(N) worst case
    Map interface
      TreeMap (via balanced BST): O(log N) add/remove/search
      HashMap (via hash table): O(1) add/remove/search expected*, O(N) worst case
    trees
      tree terminology: node, root, leaf, path, height, weight
      tree applications: file structure in OS, du command
      binary tree implementation
        pointer/reference manipulation, tree recursion
      binary search tree (BST)
        if roughly balanced, O(log N) search/insert/remove
        if unbalanced, O(N) search/insert/remove
        SimpleTreeSet implementation, tree iterator
      balanced binary search trees
        AVL trees, red-black trees
        ensure O(log N) tree height --> O(log N) search/insert/remove
    hash tables
      key-value mapping, hash function  
        if table size & hash function "reasonable", O(1) search/insert/remove
        if not, O(N) search/insert/remove
      collision handling
        linear probing, lazy deletion, primary clustering, rehashing
        quadratic probing, chaining
      
Algorithmic Approaches
  divide & conquer
    idea: divide into subproblems, solve (usually recursively), then combine
    when: any application that can be divided into independent parts
    e.g.: binary search, merge sort, GCD, tree traversal