Transcript Ch10

Collection Classes
• The Need for Flexible Size Collections.
• The ArrayList Class.
• Collections and Object Identity.
• The LinkedList Class.
• Wrapper Classes.
• Iterating through a Collection.
OOP with Java, David
J. Barnes
Collection Classes
1
Flexible Size Collections
• In some applications, the required size for a
collection may be unpredictable or variable.
– Cards in a hand (bounded but variable).
– Callers to a radio phone-in (unbounded).
– Passengers on a ferry (unbounded?).
• Arrays are not always suitable for holding
such data.
OOP with Java, David
J. Barnes
Collection Classes
2
Array Unsuitability
• A smaller array might arbitrarily limit the
capacity.
• A very large array will waste capacity.
– There might be no guarantees that it will not
overflow, anyway.
• We could create a new array if the old one
fills up.
– Problem with notifying aliases.
OOP with Java, David
J. Barnes
Collection Classes
3
Custom Collection Classes
• Two main classes, defined in java.util.
– ArrayList and LinkedList.
•
•
•
•
No fixed size.
Expand and contract as required.
No wasted space, no arbitrary limit.
Can only hold objects, not primitive values.
– Wrapper classes solve this problem.
OOP with Java, David
J. Barnes
Collection Classes
4
An ArrayList for Strings
import java.util.*;
class RadioShow {
...
// Store the names of callers.
private ArrayList callers = new ArrayList();
}
• Compare with an equivalent array declaration:
• private String[] callers = new String[max];
OOP with Java, David
J. Barnes
Collection Classes
5
ArrayList Methods
• Items in a collection `lose' their identity.
• Each item has an index (0...size()-1).
– ArrayList defines add, get, set,
remove and clear methods, for instance.
• Existing items are automatically moved.
– An item's index might change.
• The capacity grows automatically.
– The trimToSize method minimizes it.
OOP with Java, David
J. Barnes
Collection Classes
6
Collections and Object Identity
• Objects have both a dynamic type and a
static type.
– An object's dynamic type is fixed.
– An object's static type depends on the variable
used to refer to it.
• Collections treat everything as Object.
– They are generally passive, not needing to
interact with the items they contain.
OOP with Java, David
J. Barnes
Collection Classes
7
Object Casts
• Retrieving an object usually requires a cast:
// ArrayList callers = getCallers();
// Get the first caller (compilation error).
String caller = callers.get(0);
• The compiler cannot tell that the object is a
String, so an explicit cast is needed:
String caller = (String) callers.get(0);
OOP with Java, David
J. Barnes
Collection Classes
8
The LinkedList Class
• Very similar interface to ArrayList.
– add, clear, get, indexOf, remove, set.
• Additional direct access to first and last
items in the list.
– getFirst, getLast, removeFirst,
addLast, etc.
• Suitable for data structures, e.g., stacks and
queues.
OOP with Java, David
J. Barnes
Collection Classes
9
The Wrapper Classes
• Collection classes cannot hold primitivetype values.
• These must be wrapped in an object.
• Each type has a wrapper class.
– Boolean, Character, Double,
Integer, etc.
– Methods: intValue, doubleValue, etc.
– String parsing methods.
OOP with Java, David
J. Barnes
Collection Classes
10
Wrapping Integers
ArrayList list = new ArrayList();
int num = keyboard.nextInt();
while(num >= 0){
Integer wrapper = new Integer(num);
list.add(wrapper);
num = keyboard.nextInt();
}
// Sort the values.
Collections.sort(list);
OOP with Java, David
J. Barnes
Collection Classes
11
Iterating through a Collection
• We could use integer indices:
final int numItems = nameList.size();
for(int i = 0; i < numItems; i++){
System.out.println((String) nameList.get(i));
}
• This would be inefficient for a LinkedList,
because it does not store its items in an array.
OOP with Java, David
J. Barnes
Collection Classes
12
Iterator
• Provides efficient iteration over an arbitrary
collection.
Iterator names = nameList.iterator();
while(names.hasNext()){
String who = (String) names.next();
if(who.startWith("X")){
names.remove();
}
}
OOP with Java, David
J. Barnes
Collection Classes
13
Queue and Stack Collections
• An ArrayList permits efficient retrieval
of data from random positions.
• Access is often more orderly.
– First-In, First-Out (FIFO) Queue.
– Last-In, First-Out (LIFO) Stack.
• A LinkedList is well suited to
supporting such specialized collections.
OOP with Java, David
J. Barnes
Collection Classes
14
Queues
• Common in every-day life
– Bus queues, traffic jams, cafeteria.
• Enter at the tail
– Use the list's add method.
• Depart at the head.
– Use the list's removeFirst method.
OOP with Java, David
J. Barnes
Collection Classes
15
Public interface of CardQueue
class CardQueue {
// Add a card to the queue.
public void add(Card c){
getQueue().add(c);
}
// Remove (and return) the next card.
public Card next(){
return (Card) getQueue().removeFirst();
}
...
// The collection of objects.
private LinkedList queue = new LinkedList();
}
OOP with Java, David
J. Barnes
Collection Classes
16
Stacks
• Less common in everyday life.
– Trays in a restaurant, cards in a discard pile.
• Common in programming languages.
– Runtime stack, recursive functions.
• Enter at tail (push), remove from tail (pop).
• Similar interface to Queue, but different
semantics.
OOP with Java, David
J. Barnes
Collection Classes
17
Public interface of CardStack
class CardStack {
// Add a card to the stack.
public void add(Card c){
getStack().add(c);
}
// Remove (and return) the last card.
public Card next(){
return (Card) getStack().removeLast();
}
...
// The collection of objects.
private LinkedList stack = new LinkedList();
}
OOP with Java, David
J. Barnes
Collection Classes
18
Queue and Stack
• Additional peek and size methods
commonly available for both.
• java.util.Stack is an example of
inappropriate inheritance.
• Typed Queue and Stack classes easily
created for other classes.
– No generic types in Java.
OOP with Java, David
J. Barnes
Collection Classes
19
Recursion
• Infinite recursion - often accidental.
• Bounded recursion. An alternative to
iteration.
• Recursive solutions to divide-and-conquer
problems.
OOP with Java, David
J. Barnes
Collection Classes
20
Infinite Recursion
• Chicken or Egg conundrum.
• Apportioning blame.
– She hit me, he hit me first, she did, he did, ...
• Inflationary spiral.
– Raise prices to cover higher wages, raise wages
to cover higher prices, etc.
OOP with Java, David
J. Barnes
Collection Classes
21
Chicken or Egg?
• A method invokes itself.
// Which came first?
public void chickenOrEgg(String which){
System.out.println(which);
if(which.equals("Chicken")){
chickenOrEgg("Egg");
}
else{
chickenOrEgg("Chicken");
}
}
OOP with Java, David
J. Barnes
Collection Classes
22
Recursive Calls
1:chickenOrEgg("Chicken") prints Chicken and calls
2: chickenOrEgg("Egg"), which prints Egg and calls
3: chickenOrEgg("Chicken"), which prints Chicken and calls
4:
chickenOrEgg("Egg"), which prints Egg and calls
5:
chickenOrEgg("Chicken"), which prints Chicken and calls
...
• An infinite sequence of numbers:
public void sequencePrint(long n){
System.out.print(n+" ");
sequencePrint(n+1);
// Never reached ...
System.out.println("End of print: "+n);
}
OOP with Java, David
J. Barnes
Collection Classes
23
Recursive Methods
• Direct recursion.
– A method calls itself.
• Indirect recursion.
– Method A calls method Z, and method Z calls
method A before it has finished.
– Harder to spot potential problems.
OOP with Java, David
J. Barnes
Collection Classes
24
Avoiding Infinite Recursion
• Loops can also be infinite.
– The terminating condition is never triggered.
• There must be an 'escape route'.
– A non-recursive path through a recursive
method.
– It provides a limit on the depth of the recursion.
OOP with Java, David
J. Barnes
Collection Classes
25
A Limited Recursive Sequence
public void sequencePrint(long n){
final long limit = 5;
if(n < limit){
System.out.print(n+" ");
sequencePrint(n+1);
System.out.println("End: "+n);
}
}
0 1 2 3 4 End: 4
End: 3
End: 2
End: 1
End: 0
OOP with Java, David
J. Barnes
Collection Classes
26
Recursive Factorial
public static long factorial(long n){
if(n == 0){
// The (non-recursive) base case.
return 1;
}
else{
return n * factorial(n-1);
}
}
• The multiplications cannot be applied until
the recursion unwinds.
OOP with Java, David
J. Barnes
Collection Classes
27
Divide and Conquer Problems
• Divide and conquer problems often involve
recursive solutions.
• A large data set can often be broken down
quickly into smaller subsets.
– The technique is applied recursively to each
sub-set.
– The overall technique is applied recursively to a
single subset.
OOP with Java, David
J. Barnes
Collection Classes
28
Recursive Binary Search
Find the mid-point;
if(the target element is too big){
Try again to the right;
}
else if(the target element is too small){
Try again to the left;
}
else{
We have found it.
}
• 'Try again' implies making a recursive call.
OOP with Java, David
J. Barnes
Collection Classes
29
public int indexOf(int[] numbers, int value,
which-part-to-examine){
final int notPresent = -1;
if(no-more-items-left){
return notPresent;
}
else{
int index = find-the-mid-point;
if(value > numbers[index]){
return indexOf(numbers,value,right-hand-side);
}
else if(value < numbers[index]){
return indexOf(numbers,value,left-hand-side);
}
else{
return index;
}
}
}
OOP with Java, David
J. Barnes
Collection Classes
30
Review
• Many problems require flexible collections.
• Use ArrayList and LinkedList
according to requirements.
• Use a cast when retrieving items.
• Use wrapper classes to store primitives.
• Use an Iterator to iterate through a
collection.
OOP with Java, David
J. Barnes
Collection Classes
31
Review (cont.)
• Collection classes often form the basis for
further specializations.
– Queue and Stack are the most common.
• Recursion is an alternative to iteration.
– Methods may be directly or indirectly
recursive.
– Avoiding infinite recursion requires a nonrecursive 'escape route'.
OOP with Java, David
J. Barnes
Collection Classes
32
Review (cont.)
• Divide-and-conquer solutions often involve
recursion.
– Binary search is one example of a divide-andconquer solution.
OOP with Java, David
J. Barnes
Collection Classes
33