Topics

• Linked lists
• node and list classes
• operations
• traverse, insert, delete
• Generic classes
• using class Object and type casts
• type parameters
• "extends Comparable" and compareTo()
• Stacks
• implementations: array and linked list
• the system stack and stack frames
• Queues
• implementations: array and linked list
• Binary trees
• generic nodes
• traversals
• Binary search trees
• operations
• insert, delete, search
• AVL trees
• definitions
• insert operation (by picture)
• Hashing
• hash functions
• separate chaining
• open addressing
• linear probing
• clustering
• double hashing
• tombstones
• hashing to buckets
• overflow buckets
• Disk stuff
• platter, track, sector
• sector as smallest addressable unit: read/write by sector
• direct access files using hashing
• Graphs
• definitions
• adjacency matrices
• adjacency list representation
• depth-first search
• breadth-first search
• weighted graphs
• Dijkstra's Algorithm