Transcript Working With Collections in the AP Java Subset

Working With Collections in the
AP™ Java Subset
2003 ACTE Convention
© 2003
by Kenneth A. Lambert
Presenter’s Information
Dr. Kenneth A. Lambert
Department of Computer Science
Washington and Lee University
Lexington, VA 24450
Email: [email protected]
Home page: http://www.wlu.edu/~lambertk/
These slides: http://www.wlu.edu/~lambertk/ACTE/
The Second Course in
Computer Science
• Data structures
• Algorithms for processing data structures in
various applications
• Analysis of performance of data structures
and algorithms
Perspectives on Data Structures
• Formal properties
– What are they?
– How are they organized and classified?
• Implementations
– How are they represented?
– What are the performance trade-offs?
• Applications
– What are they good for?
1999-2003:
Data Structures in AP “AB”
• Arrays (also used to implement strings)
• Linked lists
• In C++
–
–
–
–
–
apstring
apvector
apmatrix
apstack
apqueue
2004: Collections
• In Java, data structures are collections
• A collection is an object that contains other objects
• There are zero or more objects in a collection
• There are operations for accessing these objects
Categories of Collections
• Linear
• Hierarchical
• Graph (not covered in second college course)
• Unordered
Linear Collections
• List
• Stack
• Queue
0
D1
1
2
D2
D3
• Objects are ordered by position
• Each object except the first has a unique predecessor
• Each object except the last has a unique successor
• Access is more restricted for stacks and queues
Hierarchical Collections
•
•
•
•
Binary tree
General tree
Binary search tree
Heap
D2
D1
D3
• Each object except the root has a unique predecessor
• Each can have zero or more successors
Unordered Collections
• Set
• Bag
• Map (table)
D1
D2
D3
D4
D5
• Objects are in no particular order
• Implementations use hashing to approach constant-time access
Standard Java Collections
• Lists - linear, supporting many operations
• Sets - unordered, unique items
• Sorted sets - like sets, but items can be
visited in sorted order
Standard Java Collections
• Maps - unordered, items accessed by keys
• Sorted maps - same as maps, but keys can
be visited in sorted order
Non-Standard Collections
• Stacks
• Queues
• Priority queues
Abstract Data Types (ADTs)
Separate the user (client) of a collection from the implementer
(server)
A list has a set of abstract operations for insertions,
removals, etc. This set of operations is called an interface.
Example: A list can be implemented with an array or a linked
structure, but this implementation is invisible to the
users. The data and methods of an implementation are
defined in a class.
Multiple Implementations
A client can choose among several implementations of
the same ADT.
The client’s code looks the same, because it uses an
interface.
Client’s program
List
Interface
Implementing
classes
ArrayList
LinkedList
Java Collection Interfaces
Collection
List
Set
SortedSet
Map
SortedMap
SortedSet extends Set, which extends Collection
Java Collection Classes
Object
AbstractCollection
AbstractList
ArrayList
AbstractSequentialList
LinkedList
AbstractSet
HashSet
TreeSet
= concrete class ( instantiated by clients)
= abstract class (organizes code in the server)
AbstractMap
HashMap
TreeMap
Non-Standard AP Collections
Interfaces: Stack, Queue, and PriorityQueue
Implementing classes: whatever seems appropriate
Client’s program
Interface
Implementing
classes
Stack
ArrayStack
LinkedStack
The Stack Interface
public interface Stack{
// Returns true if the stack is empty or false otherwise
public boolean isEmpty();
// Postcondition: obj is added to the top of the stack
public void push(Object obj);
// Precondition: the stack is not empty
// Postcondition: the object is removed from the top of
//
the stack and returned to the client
// Throws:
IllegalStateException if the stack is empty
public Object pop();
// Precondition: the stack is not empty
// Postcondition: the object at the top of the stack is
//
returned to the client
// Throws:
IllegalStateException if the stack is empty
public Object peekTop();
}
Using Stack Collections
// Create two stacks using different implementations
Stack s1 = new ArrayStack();
Stack s2 = new LinkedStack();
// Push some Integer objects onto s1 and some
// String objects onto s2
for (int i = 1; i <= 5; i++){
s1.push(new Integer(i));
s2.push("" + i);
}
// Remove and display the contents of s1
while (!s1.isEmpty()){
Object obj = s1.pop();
System.out.println(obj);
}
// Cause an exception to be thrown by looking at top of s1
System.out.println(s1.peekTop());
Performance Analysis
• Each implementation of a collection has
performance characteristics
• Each implementation can be measured for its
running time and memory usage
• A wise client chooses the implementation whose
performance most enhances the application
Performance Tradeoffs
// Create two lists using different implementations
List list1 = new ArrayList();
List list2 = new LinkedList();
// Add some objects to the two lists
. . .
// Display the contents of list1
for (int i = 0; i list1.size(); i++)
System.out.println(list1.get(i));
// Display the contents of list2
for (int i = 0; i list2.size(); i++)
System.out.println(list2.get(i));
Method get runs in linear time for linked lists, so traversals
of linked lists using get run in quadratic time!!
Iterators
• An iterator allows the client to track a
position in a collection and visit the object
at that position
• Two basic operations
– Test for more items
– Get the next item
collection
iterator
A stream of
elements
The Iterator Interface
public boolean hasNext()
public Object next()
public void remove()
remove deletes the object most recently accessed
with next
remove need not be supported, for example, with stacks
Using an Iterator
// Add some objects to list2
. . .
Iterator iter = list2.iterator();
while (iter.hasNext()){
Object obj = iter.next();
System.out.println(obj);
}
The iterator method returns an object whose class
implements the Iterator interface.
Traversals of any list with an iterator take linear time.
The Collection Interface
Collection
List
Set
SortedSet
List and Set extend
the Collection
interface, so a list or a set
can be used wherever a
collection is expected.
Creating a Collection from
Another Collection
Set mySet = new HashSet();
// Add some objects to mySet
. . .
// Transfer the objects in the set to a new list
List myList = new ArrayList(mySet);
• Define a constructor that expects an object of type
Collection as a parameter
• Use an iterator in that constructor to access the
collection’s objects
Example: Any Collection to Stack
import java.util.*;
public class LinkedStack implements Stack{
public LinkedStack(){
// Initialize the instance variables
}
public LinkedStack(Collection col){
this();
Iterator iter = col.iterator();
while (iter.hasNext())
push(iter.next());
}
// Other method definitions
// Instance variables
}
The Collection Interface
boolean
boolean
void
boolean
boolean
boolean
int
boolean
Iterator
boolean
boolean
boolean
int
Object[]
Object[]
add(Object o)
addAll(Collection c)
clear()
contains(Object o)
containsAll(Collection c)
equals(Object o)
hashCode()
isEmpty()
iterator()
remove(Object o)
removeAll(Collection c)
retainAll(Collection c)
size()
toArray()
toArray(Object[] a)
High-level operations
Operations common
to all collections
Not All Collections
Implement Collection
Collection
List
Set
SortedSet
Map
SortedMap
Stack
Queue
PriorityQueue
Collection-View
A collection-view is an object that
– implements the Collection interface
– has a collection as a backing store which does not
implement the collection interface
– allows clients to use many of the Collection
methods with such collections as stacks, queues, etc.
A Collection-View Is
Similar to an Iterator
backing store
collection
backing store
collection
iterator
object
collection-view
object
client using
hasNext, next
client using
removeAll,
retainAll,
etc.
A collection-view allows an object to masquerade
as a collection
The Method collectionView
Iterator iterator()
// Returns an iterator
Collection collectionView()
// Returns a collection-view
Any class that implements collectionView will be
compatible with the Collection interface without
implementing that interface.
Any class that implements collectionView should
also include an iterator method.
List to Stack and Stack to List
List myList = new ArrayList();
// Add some objects to myList
. . .
// Transfer the objects in the list to a new stack
Stack myStack = new ArrayStack(myList);
// Open a collection-view on the stack
Collection colView = myStack.collectionView();
// Transfer the objects in the stack to a new list
List anotherList = new LinkedList(colView);
Useful Resources
Textbook:
Fundamentals of Java Comprehensive
(by Lambert & Osborne, Course Technology, 2003)
Web sites:
Textbook page: http://home.wlu.edu/~lambertk/hsjava/
AP Central: http://apps.apcentral.collegeboard.com/Login.jsp