CSC152 2005F, Class 38: Linear Structures Admin: * Questions on the exam? (At least one error still needs to be corrected) * Time to torture the prospective Kenyon, Franklin and Marshall, St. Johns, Bates * Grinnell people are nice * Small and close * Yay, We're isolated, so there's nothing to do besides study and interact with your colleagues * Crazy awesome stuff comes to campus (Bela Fleck, Swing band, Awesome harpsichordist, Women's soccer; WMD speaker series) Overview: * Collections * Linear Structures * Randomized Linear Sturctures Exam Questions: * Is null an Integer? Yes. * What does size() return? Larger of specified size and largest-used index (e.g., size set to 100. used 2, return 100)a * Shoudl I be able to change a size field? Yes. public class ExpandableArray { int size; public void set(int index, Integer newval) { if (this.size < index) { this.size = index+1; Integer[] oldcontents = this.contents; this.contents = new Integer[this.size]; ... } } * Do I need a size field? Can't I just use the size of the array? * Certainly About Collections * Many programs collect data * Goal: Find techniques for collecting data * And think about when they are and are not appropriate * Arrays and Vectors: * Collect data by index * Retrieve easily (if some semantics to index) * Gives a sense of order * But ... * Expanding is expensive (O(size)) * No built-in sorting operation * Removing most elements is slow (O(size)) Different problems suggest different philosophysie of collections Linear Structures : Goal: Be as simple as possible * Philosophie: Add and remove, but that's about it * Application: Lots * Methods * add (put) * remove (get) * Problem: What does get return? * We seprately specify a *policy* to answer that question * We encode the policy by writing different kinds of linear structures (different interfaces) * Queue: First in, first out * Stacks: Last in, first out * Priority queue: get returns "most important" * Randomized: Hard to predict