CSC152 2005S, Class 36: Dictionaries

Admin:
* Moon pies!
* Exam!
* Prospectives?  (Probably not)
* Warning: Potential visitor Tuesday

Overview:
* Generalizing arrays
* Key methods
* Finishing the ADT
* Implementation strategies

Background: Arrays as ADTs
* Intent/philosophy: What it is or What you want it to do
* Methods: How the client uses them
* Application
* Implementation as Data structure

Philosophy of arrays:
* Collection of data
* Can be quickly accessed by a "location" (integer)
* "Indexed collection of data"

Methods:
* add something at a location 
* change something at a location
* get something from a location
* determine the number of valid locations
* create an array of a given length

Other Methods:
* We would like "resize", but the implementation that comes with Java won't permit resize.
* Rearrange the values according to certain policies (built on top of basic operations)
* Sort
* Search
...

Applying Arrays:
* Implementing other data structures, particularly linear structures
* Store binary trees
* Use sorted arrays to store information for quick retrieval (binary search)_

However, we often don't think about data as being indexed by number

Dictionaries: Like arrays, but index by other things
* E.g., a collection of grades indexed by string
* Hope: Fast access

Methods?
* See sample code

When have you seen things like dictionaries in 151?
* Association lists (cartoon sidekicks)
  * Implementation of dictionaries
* find in this implemention is O(n)
* add in this implementation is O(n)
* CAN WE DO BETTER?
  * Use binary trees (Tuesday) [Lab]
  * Use arrays (Wednesday) [Lab]
* Monday: Lots of exam questions; resolve Lorelei's question
Rebelski
Rabelsky
Repelsky
Rebbellsky