Collection

• Container
• Data structure whose primary purpose is to hold other elements
• Familiar case - array
• Properties/attributes
  • Random access via explicitly-specified position (index)
  • Fixed-size vs variable size
  • Ordered vs unordered

• Linked lists are linear structures and provide sequential access
• Hash tables provide (nearly) constant access, but no order
• Trees provide access/insertion/removal in logarithmic time, and order.

Collection

• Represents a group of objects called elements
  • Ordered/unordered
  • Duplicates/no duplicates
• Operations
  • add
  • clear
  • contains
  • equals
  • isEmpty
  • iterator
    • Provides an object that allows iteration over the collection
    • This is where order comes in
  • remove
  • size
  • toArray - allows collections to be converted into an array

• A type of Collection
• Ordered
• Sequence
• User has control over insertion point
• Elements are accssed by integer index
• Allows for duplicate elements
• Operations (in addition to those of Collection)
  • add (to a particular position)
  • find position of an object in list
  • get
  • remove (at a particular position)
  • set
• Analysis
  • Access may be proportional to index being accessed
  • Searching may be linear in cost

• A type of Collection
• No duplicate elements
• No new operations-- merely new constraints on existing operations

• maps keys to values
• One value (at most) per key
• Ordered/unordered (by key)
• Not quite a collection-- its own beast
  • Though you may have seen this in math-- it's essentially a relation - a set of pairs
• Operations
  • clear
  • containKey
  • containsValue
  • entrySet - gets a Set of the key/value pairs in the map
  • get (the value associated with a key)
  • isEmpty
  • keySet - gets the Set of keys
  • put - associates a key with a value
  • remove - a value associated with the given key
  • values - gets the Collection of values in the map

• A type of Set
• Ordered by natural order of keys
• Operations (in addition to those of a Set)
  • first
  • headSet
  • last
  • subSet
  • tailSet

• A type of Map
• Ordered by natural order of keys
• Operations (in addition to those of a Set)
  • firstKey
  • headMap
  • lastKey
  • subMap
  • tailMap

• Supports iteration over a collection
• Operations
  • hasNext
  • next

• A type of List
• Growable array of objects
• Random access via explicitly-specified position (index)
• Number of elements varies dynamically
• Automatic memory management
• Analysis
  • Constant time insertion/removal at end
  • Linear time insertion/removal at beginning or middle
• Operations
  • add/addElement
  • add (to a particular position)/insertElementAt
  • elementAt/get
  • firstElement
  • lastElement
  • remove/removeElementAt
  • set/setElementAt
• Iteration
  • From first to last element in index order

Vector v = new Vector();
String line = br.readLine(); // assume BufferedReader br
while (line != null) {
	v.add(line);					// could add ANY object to v
	line = br.readLine();
}
		
Iterator iter = v.iterator();
while (iter.hasNext()) {
	String s = (String)iter.next();		// Have to state that it's a String
	System.err.println(s);					//  or do whatever you want with the string
}
	

Stack

• (A type of Vector)
• LIFO (last-in-first-out)
• Implicit access (no real control on part of user)
• Operations (in addition to those of Vector)
  • push, pop, empty, peek

• A type of Collection
• FIFO (first-in-first-out)
• Implicit access
• Operations (in addition to those of Collection
  • peek

• A type of Set
• No guaranteed order
• Analysis
  • Constant time access/insert/remove

HashSet hs = new HashSet();
String line = br.readLine(); // assume BufferedReader br
while (line != null) {
	hs.add(line);					// could add ANY object to hs
	line = br.readLine();
}
		
Iterator iter = hs.iterator();			
while (iter.hasNext()) {					// No particular order
	String s = (String)iter.next();		// Have to state that it's a String
	System.err.println(s);					//  or do whatever you want with the string
}
	

HashMap

• A type of Map
• No guaranteed order
• Analysis
  • Constant time access/insert/remove

HashMap hm = new HashMap();
Employee employee = Employee.read(br); // assume BufferedReader br
while (employee != null) {
	hm.put(employee.getSSNum(), employee));	// could use ANY key or value for tm
	employee = Employee.read(br);
}
		
Set keys = hm.keySet();						// Get the set of keys
Iterator iter = keys.iterator();			
while (iter.hasNext()) {					// No particular order
	String sSNum = (String)iter.next();	// Have to state that it's a String
	Employee e = (Employee)tm.get(sSNum);		
	System.err.println(e);					//  or do whatever you want with the Employee object
}
	

TreeSet ts = new TreeSet();
String line = br.readLine(); // assume BufferedReader br
while (line != null) {
	ts.add(line);					// could add ANY object to ts
	line = br.readLine();
}
		
Iterator iter = ts.iterator();			
while (iter.hasNext()) {					// Natural order of String (alphabetical order)
	String s = (String)iter.next();		// Have to state that it's a String
	System.err.println(s);					//  or do whatever you want with the string
}
	

TreeMap tm = new TreeMap();
Employee employee = Employee.read(br); // assume BufferedReader br
while (employee != null) {
	tm.put(employee.getSSNum, employee));	// could use ANY key or value for tm
	line = br.readLine();
}

Set keys = tm.keySet();						// Get the set of keys
Iterator iter = keys.iterator();			
while (iter.hasNext()) {					// Natural order of the key -- a String (alphabetical order)
	String sSNum = (String)iter.next();	// Have to state that it's a String
	Employee e = (Employee)tm.get(sSNum);		
	System.err.println(e);					//  or do whatever you want with the Employee object
}