#LyX 1.1 created this file. For more info see http://www.lyx.org/ \lyxformat 218 \textclass article \language english \inputencoding auto \fontscheme default \graphics default \paperfontsize default \spacing single \papersize Default \paperpackage a4 \use_geometry 1 \use_amsmath 0 \paperorientation portrait \leftmargin 1in \topmargin 1in \rightmargin 1in \bottommargin 1in \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \defskip medskip \quotes_language english \quotes_times 2 \papercolumns 1 \papersides 1 \paperpagestyle default \layout Standard Paul Johnson \layout Standard Java Nodes Day 3 \layout Standard \added_space_top medskip 1. Array \layout Standard \SpecialChar ~ \layout Standard An array is a collection.\SpecialChar ~ It is a collection of fixed size \layout Standard where you add items at particular positions. \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 1.1. Advantages of Arrays \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 1.1.1. Fast insert \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 1.1.2. Fast removal by offset. \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 1.1.3. Java has many many "facilitators" for arrays, like System.arraycopy() \layout Standard for quick duplication of an array. See also Arrays class, a set of \layout Standard static methods for sorting and doing common chores to arrays. \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 1.2. Limitations \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 1.2.1. Hard to resize \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 1.2.2. Tedious to search for a particular item. \layout Standard \SpecialChar ~ \layout Standard 2. Overview of container alternatives \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 2.1. List \layout Standard \SpecialChar ~ \layout Standard Add and remove things easily, automatically expands to fit. \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 2.2. Set \layout Standard \SpecialChar ~ \layout Standard This is a container that stops you from inserting the same object \layout Standard twice.\SpecialChar ~ It can have various underlying "implementations" (ways of \layout Standard writing the code that does the double-checking). \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 2.2.1. Sets may be sorted or not. \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 2.3. Map \layout Standard \SpecialChar ~ \layout Standard Insert items with a "key", and then ask for items with the "key". \layout Standard Generally, the key must be an object, which means that if you want to \layout Standard have an integer key, you must "wrap" the integer in an object of type \layout Standard Integer. \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 2.4. Some important terms \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 2.4.1. Hash \layout Standard \SpecialChar ~ \layout Standard An advanced computer science term referring to a way of storing \layout Standard objects and searching for them. \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 2.4.2. Binary search tree \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 2.5. Notes about sorting \layout Standard \SpecialChar ~ \layout Standard 1.\SpecialChar ~ compareTo() method (The Comparable Interface). \layout Standard \SpecialChar ~ \layout Standard If a class has a compareTo() method, then it can tell you if it is \layout Standard less than,equal to, or greater than the thing it is compared against \layout Standard (in this case, x) \layout Standard \SpecialChar ~ \layout Standard 2.\SpecialChar ~ Comparator interface. \layout Standard \SpecialChar ~ \layout Standard Create a Comparator class that can take 2 objects and tell which is \layout Standard greater, or if they are equal \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 2.6. Objects removed from a collection "LOSE THEIR IDENTITY". \layout Standard \SpecialChar ~ \layout Standard Since a Java collection is a general purpose thing, it cannot be aware of \layout Standard the kind of object it is holding. Hence, when something comes out of a \layout Standard collection, it must be told what kind of object it is. Do this by an \layout Standard explicit cast, as in \layout Standard \SpecialChar ~ \layout Standard anObject = (Student) someCollection.get(4); \layout Standard \SpecialChar ~ \layout Standard This says the item at offset 4 is a Student object.\SpecialChar ~ If in fact it is \layout Standard a member of some other class, you will get runtime errors in your program. \layout Standard \SpecialChar ~ \layout Standard See Eckel p. 454 for a way to "type" lists. (Create a subclass of a \layout Standard container and then override the add() and get() methods.) \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 2.7. Please study the interfaces \layout Standard \SpecialChar ~ \layout Standard Collection (some highlights) \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ boolean add(Object) \layout Standard \SpecialChar ~ boolean contains(Object) \layout Standard \SpecialChar ~ boolean remove(Object) \layout Standard \SpecialChar ~ Iterator iterator() \layout Standard \SpecialChar ~ int size() \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 2.8. Note what an Iterator can do. \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard 3. More about Lists \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 3.1. Many flavors of lists \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 3.1.1.ArrayList \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 3.1.2.LinkedList \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 3.2.List: important added methods \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 3.2.1. Object get(int) \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 3.2.2. int\SpecialChar ~ \SpecialChar ~ \SpecialChar ~ indexOf(object) \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 3.2.3. boolean add(int,Object)\SpecialChar ~ \SpecialChar ~ to insert at a point. \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 3.3.ArrayList fast access by offset. Rather like a regular Array, but \layout Standard resizable.\SpecialChar ~ Capacity can be preset, adjusted \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 3.4. LinkedList: more general purpose class. \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 3.4.1. boolean addFirst(object) \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 3.4.2. boolean addLast(object) \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 3.4.3. Object getFirst() \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 3.4.4. Object getLast() \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 3.4.5. Object removeFirst() \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 3.4.6. Object removeLast() \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 3.5.ListIterator: special methods that can change a collection \layout Standard without wrecking the iterator.\SpecialChar ~ ListIterator can do "next()" to a \layout Standard point, then add or remove objects. The ability to add is the big \layout Standard supplement from ListIterator over Iterator. \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard 4. More about Sets \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 4.1. Should it be sorted or not? \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 4.2. HashSet: a not sorted Set.\SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 4.2.1. Faster at "getting" objects by name than a List. \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \SpecialChar ~ \SpecialChar ~ 4.2.2. Slower at inserting objects. \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 4.3. TreeSet: Uses a binary search tree to place items in an order, \layout Standard to allow quick retrieval of the maximum or minimum. \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard 5. More about Maps \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 5.1. A Map is different than a set in 2 ways. \layout Standard \SpecialChar ~ \layout Standard 1. A Map lets you insert an object only if you give a "key" object. \layout Standard It is possible, I guess, to give a key that is the same as the object, \layout Standard but why would you ever want to? \layout Standard \SpecialChar ~ \layout Standard 2. A map allows you to insert an object more than once, as long as you \layout Standard use a different key for each object. \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ 5.2. Maps can be sorted as well.\SpecialChar ~ (TreeMap) \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \layout Standard \SpecialChar ~ \the_end