CSC 427: Data Structures and Algorithm Analysis
Fall 2008
Test 2 Review
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