Transcript Slide 1

APCS-AB: Java
ArrayLists and Iterators
November 28, 2005
week13
1
Checkpoint
• Sudoku - still missing two, waiting to grade
• Test - Scheduling make-up
week13
2
Intro…
• But Ms. K I don’t know how many items I
am going to need to store… arrays won’t
work for me!
• What should I do? I want a flexible sized
collection!
And in comes….
ArrayList
week13
3
ArrayList - what’s that?
• It’s an object in the java.util package
• A Class that implements a list - a flexiblesized collection
 “List” is a special Java interface (we’ll talk
about interfaces later) that specifies methods
and variables anything called a “List” should
have
• It’s kind of like an array, but can grow and
shrink
 And it has some limitations…
week13
4
Important Features of
ArrayList
• It is able to increase its internal capacity as required, as
•
•
more items are added, it simply makes enough room for
them.
It keeps its own private count of how many items it is
currently storing. Its size method returns the number of
objects currently stored in it.
It maintains the order of items you insert into it. You can
later retrieve them in the same order.
week13
5
Some ArrayList details
• Each ArrayList instance has a capacity. The capacity is
•
the size of the array used to store the elements in the list.
It is always at least as large as the list size. As elements
are added an ArrayList, its capacity grows automatically.
The details of the growth policy are not specified beyond
the fact that adding an element has constant amortized
time cost.
An application can increase the capacity of an ArrayList
instance before adding a large number of elements using
the ensureCapacity operation. This may reduce the
amount of incremental reallocation (creating the space to
add new elements one at a time)
week13
6
Some ArrayList Methods
boolean add(Object o)
Appends the specified element to the end of this list.
void clear()
Removes all of the elements from this list.
boolean contains(Object elem)
Returns true if this list contains the specified element.
Object get(int index)
Returns the element at the specified position in this list.
int indexOf(Object elem)
Searches for the first occurence of the given argument, testing for equality using
the equals method.
boolean isEmpty()
Tests if this list has no elements.
int lastIndexOf(Object elem)
Returns the index of the last occurrence of the specified object in this list.
Object remove(int index)
Removes the element at the specified position in this list.
week13
7
Array versus ArrayList
Benefit
Drawback
week13
Array
ArrayList
Objects and primitives
do not need to be cast
when accessing the
elements
Dynamically sizeable
Not dynamically sizable May not hold primitives
and Objects usually
need to be cast when
accessing the element
8
Going through a whole collection
• What if we wanted to implement a
“ToDoList” with Note Objects
 If users can add and remove notes, the index
numbers can change, so we want a way to list
all the notes with their current index numbers.
 We also want a method called listAllNotes that
can take into account that the list has dynamic
size and can change a lot
week13
9
2 ways to go through a collection
• For an ArrayList, we could loop through
similarly to what we do for an array (using
the index to get each element)
• But going through all items in a collection
is a common activity, so the Java API gives
a way to iterate over contents of a
collection.
week13
10
Iterating
• The java.util package has an Iterator object
• An Iterator is an object that has methods that lets you
•
step through each item in a collection one at a time
This object provides two methods for iteration: hasNext
and next
• Example: Using this object (assume you have an
ArrayList defined called myCollection)
week13
Iterator it = myCollection.iterator();
while(it.hasNext()){
// Call it.next to get the next object
//do something with that object you got
}
11
Why two ways?
• For an ArrayList, either way will work and
is roughly equal in terms of quality
• For other collection classes in Java, it is
impossible or very inefficient to access
elements by providing an index.
• The iterator solution can be used for all
collections in Java, so it is an important
design pattern to use.
week13
12
What does the API say about the
Iterator methods?
• boolean hasNext()
•
•
Returns true if the iteration has more elements.
Object next()
Returns the next element in the iteration.
void remove()
Removes from the underlying collection the last
element returned by the iterator
week13
13
Why an Iterator is even better
than a for loop ….
• So let’s say that you are looping through your ArrayList of
friends with a for loop and you need to delete two of them
from the middle
 What happens?
 ==> your counter ends up being off because you are changing
the data structure as you go through
• However, if you loop through using an Iterator -- you don’t
have this problem
 You can think of the iterator as an “I” beam - when you stop to
remove something, the beam stays where it is
 You don’t have to decrement counter in order not to miss
anything
• Iterators can traverse collections more elegantly and
efficiently if you are changing things as you go along!
week13
14
But I put a String in my
ArrayList…
• My ArrayList has Amnesia!
• Why does the Iterator give me an Object? What can I do
with that Object?
• We just learned that every class has Object as its
superclass, so we need a way of saying to the Java
compiler, “Hey, this thing the Iterator just got for me isn’t a
plain regular Object, it is an object that I’ve put in there,
and I know that it has the data type of String”
week13
15
Casting to the rescue!
• Remember casting from our int/int = double
•
days?
We can use casting to do this too!
 Tell the compiler what specific kind of object is stored
in your ArrayList
String myString = (String) it.next();
I have a String not an
Object!
week13
16
But there’s more…
• The newest version of Java put in something
called Generics that will fix this “amnesia”
problem
 We won’t go into too many details, but it’s really cool
 You can make type-safe collections of Objects
ArrayList<String> myStringList = new ArrayList<String>;
 Now our ArrayList can hold only Objects of type String
and the compiler will enforce it!
• But for now, you still also need to understand the
cast of the Objects in the collection, because the
AP exam may test your knowledge of it
week13
17
Enhanced For - new in Java 5
• Instead of using the regular for loop to step through each
element in an array or in a collection, Java 5 gives a new
kind of loop:
Dog[] aBunchOfDogs = new Dog[20];
//pretend these have been initialized to something
for(Dog d : aBunchOfDogs){
System.out.println(d);
}
• Underneath the scenes, it’s really just an Iterator in a nice
new package (but again, due to the AP exam, you still
need to understand Iterators)
week13
18
Lab/Homework
• 2004 AP CS A Free-Response Question 2
 We will program the whole problem, not just
the specified methods
week13
19
Extra Stuff (Questions during
lab)
• To check the type of an Object for casting:
if(myObject instanceOf Dog)
• To make an Iterator from a Java Collection:
ArrayList li = new ArrayList();
Iterator it = li.iterator();
• To make a parameterized Iterator:
ArrayList<Pet> li = new ArrayList<Pet>();
Iterator<Pet> it = li.iterator();
week13
20
APCS-AB: Java
Exceptions
November 29, 2005
week13
21
Exceptions
• In Java, an Exception is an object that defines a
problem that can usually be fixed
 An error is like an exception except that the problem usually
cannot be fixed
• Handling exceptions – can be done in different ways
 Typically you catch the exception and then do some action to
correct it
• If the exception is not handled, the program will crash and
produce a message with information about what
happened
week13
22
Common Exceptions
•
•
•
•
•
•
•
ArithmeticException (like / by zero)
NullPointerException
ArrayIndexOutOfBoundsException
IndexOutOfBoundsException
ClassCastException
IllegalAccessException
ClassNotFoundException
week13
23
Throwing Exceptions
• The Java runtime environment throws exceptions
• Programmers can also choose to throw
exceptions
 Example:
• throw new NoSuchElementException()
• Exception is a class with a default constructor
with no arguments and a constructor that takes a
String argument that appears in the message
when the exception occurs
week13
24
Making our own exceptions
• We can define our own exceptions by deriving a new
class from Exception or one of its descendants
public class OutOfRangeException extends Exception{
OutOfRangeException(String message){
super(message);
}
}
week13
25
Throwing an exception
import java.util.Scanner;
public class InputGetter{
public int run() throws OutOfRangeException{
Scanner sc = new Scanner(System.in);
System.out.println(“Enter a value between 5 “
+ “and 20”);
int value = sc.nextInt();
if(value < 5 || value > 20)
throw new OutOfRangeException(“Input is out of range”);
return value; //may not be reached
}
}
week13
26
Catching Exceptions
• If you can throw it, you can catch it…
• Try/catch block
try{
//statements that might cause exception;
InputGetter in = new InputGetter();
in.run(); //throws an exception
}
catch(OutOfRangeException e){
//exception-handling statements;
//could print an error message and exit
//could try to recover
}
catch(Exception other){
//exception-handling statements;
//this isn’t needed here, but some methods could
week13 //throw different kinds of exceptions
}
27
But you can also punt
• If you don’t want to deal with an exception, your method
•
could punt and throw it back
For example, let’s say you are working with Files, just
trying to open a File with Scanner can cause a
FileNotFoundException, maybe we don’t want to
deal with this
 Our method could say that it throws a
FileNotFoundException and we just ignore what could
happen
 For Example:
public void readPuzzleFromFile(File f) throws
FileNotFoundException { … }
week13
28
APCS-AB: Java
LinkedLists
November 30, 2005
week13
29
Checkpoint
• Sudoku - still missing one, waiting to grade
• Test - make-up
• Pet and Kennel Lab - missing some
week13
30
SideNote
• I may have misspoke the other day when I talked about Interfaces
• You do not need to declare that Interface methods are abstract
 A method declaration within an interface is followed by a semicolon (;)
because an interface does not provide implementations for the methods
declared within it.
 All methods declared in an interface are implicitly public and abstract.
week13
31
List Interface (AP Subset)
• List extends java.util.Collection
• Here are the methods List implementations
must supply:
week13
32
ArrayLists as data structures
• Maybe you want your arrays to have more flexibility that
•
what we’ve done so far…
How would you program the following operations for an
array?
 Add
• At beginning
• At end
• At a certain location
 Delete
• At beginning, At end, At a certain location
week13
33
Representing data structures
• Arrays are one way to organize a list -- But they are
limited because they have a fixed size and fixed
references
• Some collections get around this – for example,
ArrayList will create larger arrays when needed and
copy everything over into it (but that’s not very efficient)
• But a truly dynamic data structure can grow and shrink
as needed
week13
34
Java Collections
• All Java Collections can be implemented in different ways
• In the Java API, collection classes generally tell the collection type
and the implementation
 ArrayList is a list collection with an array implementation
 LinkedList is a list collection with a “linked” implementation -- let’s look at
what that really means!
week13
35
ADTs
• ADT = abstract data type
• A collection of data and the operations that
are defined on that data.
• Provides a standard interface to define
what the structure does, no matter how it is
implemented
week13
36
Dynamic Data Structures
• Use links between objects to hook them together
in whatever type of structure we need
 Nodes to hold the data
 Links to hook nodes together
• If we are careful, we can make different kinds of
•
structures that are easy to search and modify,
depending on our needs for the data
LinkedList – a dynamic data structure that is
linearly (usually) “linked” together
 Mirrors the functionality of an array
week13
37
ListNode definition
list
class ListNode{
private Object value;
private ListNode next;
}
Now we can instantiate two objects of a
class and chain them together using the
next reference
value
value
This makes
the LinkedList
week13
38
Linked Lists
• And now we have a way to represent a Linked List, but we also need
our list operations
• Want to have a way to add nodes to the list and remove nodes from
list
 Insertion and deletion can happen in 3 places:
• At the front of the list
• In the middle of the list
• At the end of the list
week13
39
Insertion at front
null
X
list
1
2
node
Inserting the red node at the front of the list
week13
40
Insertion in the middle
current
X
list
2
null
1
node
Inserting the red node in the middle of the list
week13
41
Insertion at the end
end
X
null
list
null
node
Inserting the red node at the end of the list
week13
42
Special Insertion Case (Empty List)
• New node is created and inserted as the
first node in the list
• List pointer was pointing to null (because
the list was empty)
• Make sure that list pointer is set up to point
to the first node
week13
43
Deleting nodes
• Any node can be deleted, we just have to
maintain the list and its “linked” properties
• Deleting first element
 Make sure the reference to the list points to the
current second node in the list before deleting the first
element
• Deleting other elements
 Find the node in front of the node that we’re deleting
(have extra “previous” and “current” pointers)
 Update references…
week13
44
Implementing LinkedList
• Need to program the LinkedList class
 Performs all the insertions and deletions,
handles special cases
• Need to program the ListNode class
 Represents the node object
 This is available at:
http://www.cs.duke.edu/csed/ap/subset/annotated/ap/ListNode.java
week13
45
Lab/Homework:
Implement LinkedList
• LinkedList class: (for now a standalone class)







boolean add(int index, Object o)
boolean add(Object o) //adds to end of list
Object get(int index)
Object remove(int index)
boolean set(int index, Object o)
int size()
Methods to be implemented later (For List Interface contract)
• Iterator iterator()
• ListIterator listIterator()
• Tester class: MyCollection
 Make an instance of linked list class and use its methods (test all of
them) to store Objects of your choice (your CD collection, a list of
your favorite songs, etc)
 Have a method for traversing the linked list, that will print each of
week13 object of your collection
46
APCS-AB: Java
More Linked Lists
December 1, 2005
week13
47
CheckPoint
• LinkedList implementation good?
• Today we will implement MyCollection to
test your LinkedList, if you haven’t already
done so
week13
48
More-on Linked Lists
• The LinkedList we wrote yesterday only
allows us to move forward through our list what if we want to move backwards too?
 What would we need?
week13
49
Doubly LinkedLists
• The ListNode class would need to keep
track of the next object and the prev object
• Makes it easier to move back and forth
between nodes in the list
• Insertion & deletion slightly more
complicated – need to make sure you
maintain both links
week13
50
Doubly LinkedList
• List would want to keep track of the first
ListNode and the last ListNode
• More efficient structure for
problems/situations that need it.
Front_list
null
null
End_list
week13
51
Traversal: Stepping through a
LinkedList
• Just follow the next pointers to each object
until the next pointer is null
• Useful for:
 Printing objects
 Looking for a certain object
 etc
week13
52
Circular Linked Lists
• A LinkedList where the end node points
back to the first node
week13
53
Homework: Implement circular
doubly LinkedList
• Use your code from yesterday to create a
DoublyCircularLinkedList, which needs a DoubleNode class
week13
54