Transcript Powerpoint - MHS Comp Sci

ArrayList
Starring: Purse, Sr.
Co-Starring: Purse, Jr.
Poe
Numbers
1
Purpose:
In this lecture series we will introduce the
concept of a LIST.
We will take a look at Java’s ArrayList
class that implements Java’s List interface.
The AP subset includes the ArrayList as
part of the testable material on the AB
exam.
2
Resources:
Barrons Chapter 6, Chapter 11 p.362 &
368-370Java.util.ArrayList
Java Essentials Chapter 13 p.521
Java Essentials Study Guide
Chapter 11 p.163 & Chapter 16
p.263
3
Resources:
Java Methods Data Structures
Chapter 2 p.33
APCS Course Description p.27
Paragraphs 2 & 3
4
Intro:
In Computer Science II we discussed
Arrays as well as Java’s Arrays class.
With Arrays, we learned to use 1 and 2
dimensional arrays of primitives and
objects, passing arrays as parameters,
Bubble Sorting an array.
5
Intro:
With the Arrays Java class (it is really a
Static utility class) , java.util.Arrays, we
used it’s methods to sort & search
(Binary Search) & compare its elements
which can contain primitives or
objects. This class works with existing
user defined arrays.
6
Now we will take one step forward by
discussing the Java ArrayList.
This class introduces the concept of a
List.
The List is an ADT and will be
discussed in greater detail when we
learn about ADT’s & Data Structures.
7
AP AB Subset: Lets read the Course
Description regarding ArrayList on
page 22 (last 2 paragraphs) & page 24
(top)
..\AP Student Reference Material\2006 AP
Course Description.pdf
8
 What we will Cover in this Lecture:
 You will initially create YOUR OWN ArrayList and use
it in a test application.

Elements of a List

A First look at the List interface java.util.List

Arraylist:
Where it fits in the Collections Hierarchy
A Look at java.util.ArrayList
Working with the ArrayList
adding an element
Get the Size
Retrieve (Get) an Element
Modify (Set) the State of an Element
Remove an element
9
What we will Cover in this Lecture:
Arraylist and Generics
Big-O of ArrayList
Best Use for this type of Data
Structure
Wrapping Numbers
What is critical for the AP Exam
10
 TPS:
 Use the following files, located on the
APCompSci WebPage, to create your own
implementation of an ArrayList:
 MyArrayList.java Is a class shell
containing the methods you need to code
 UseMyArrayList.java
Is a sample Driver
program (SPVM) that utilizes your ArrayList.
It should execute as is.
 Download your COPY of these files,
implement and test your version of
MyArrayList
11
Elements of a List:
A Look at the following diagram, one
we will see MANY times throughout the
year, shows a class Hierarchy.
Lets focus on the List Interface
Then we will look at a class, ArrayList,
that implements the List interface.
12
13
On an ABSTRACT Level, a generic List
contains a number of elements (values or
objects) arranged in sequence from
which we can locate a specific list
element, add elements to the list and
remove elements from the list.
This is the framework or definition of an
Abstract List Data Structure
A List is an Abstract Data Type (ADT)
14
We could further define the List to be in
some ordered sequence and include a
behavior that permits an element to be
placed “in order” onto the List
This would be called an Ordered List
This is merely a structure or a set of
criteria that can be implemented different
ways
15
We can have an Array implementation of
the Abstract List Structure. All we need to
do is make sure we provide for the
BEHAVIORS as specified in the Criteria for
a List (add, remove, get, size, modify)
As we will see later in the year, we can
provide other implementations such as a
Linked List implementation
16
The specific implementation of an
Abstract Structure depends on the needs
of the system or problem you are
attempting to resolve.
17
As we will see, we can evaluate the
effectiveness of a specific implementation
by evaluating its order of growth or Big-O.
Each behavior of the List Structure that is
implemented will carry a “COST” that is
specific to the type of implementation.
For example, Suppose we are asked to
develop a system that requires us to
maintain a list of students and the list was
ordered by Last Name.
18
Now, in this system the Dominant
behavior will be Searching for a specific
student in the list. The list , once built ,
will not change much but it will be
accessed frequently for student info.
19
In this case we need to implement a list
with a Data Structure that minimizes the
“cost” of searches. In this case we
COULD design an ArrayList
implementation because it has a low cost
for finding a specific element (binary
search or hash implementation).
20
The “cost” of a find behavior against an
Ordered ArrayList would be Log N (Binary
Search) or O( 1 ) (hash)
That is much better than a “cost” of N
(linear) if we used a Linked List
implementation for this system.
We will soon see that there are other
options such as a Binary Tree
implementation.
21
At this point, make sure you keep clear
that we have a Concept that is an Abstract
Data Structure (ADT) such as a List
An Implementation of that ADT such as an
ArrayList
Each implementation must be evaluated
against their relative “costs” when
deciding which one to use for a particular
system
22
A First look at the List interface interface
java.util.List <E> interface:
boolean add(E o)
int size()
E get(int index)
E set(int index, E element)
/* replaces the element at index with
element returns the element formerly at
the specified position */
Iterator E iterator()
ListIterator E listIterator()
23
The actual Java List interface includes
many more methods, but for AP purposes,
these are the ones we need to be able to
work with although we are adding the
Remove method
As you can see, this interface merely
identifies the behaviors that MUST exist in
a List
24
The actual implementation of which is left
to the specific data structure (ArrayList for
example)
For now, ignore the Iterator and
ListIterator behaviors as we will discuss
these at a later time.
25
NOTE: The List Interface is Typed with
<E>
As we have already discussed, This
indicates that ALL classes that implement
the
List interface will be designed to be
instantiated to be used with a specific
class (or class hierarchy) at design time.
26
The benefit here is there will not be a need
to cast to the desired object.
In previous versions of Java, the List was
designed to work with the Object
Class SO any methods of List accepted
and/or returned a generic Object
Reference that had to be CAST into the
desired class.
Example:
27
BEFORE:
Runner myRunner = new Runner();
List L = new ArrayList();
L.add( myRunner);
// Retrieve from List
Runner r ;
r = (Runner) L.get(0);
r.getHoursTrained();
28
NOW:
Runner myRunner = new Runner();
List<Runner> L = new ArrayList<Runner>();
L.add( myRunner);
// Retrieve from List
i = (L.get(0)).getHoursTrained();
See how the Generic Version will return
the TYPE of object declared in the < >
Therefore, there is no need to cast
29
However, you can still generate an
Arraylist WITHOUT Generics
30
Why is such an Interface Important ?
What benefits, if any, does it provide ?
What does a List limit its elements to be ?
31
Objects, You can only have a List that
contains Objects, you CAN NOT have a
List of primitive data types
What can you do if your list needs to
maintain integers or doubles ?
Since, all classes extends from Object,
you may fill in a List with any kind of
object like Strings, arrays or instances of
your own defined class
32
The List interface, as with other interfaces,
does not define any Constructors that is
left up to the class that implements this
interface
For the methods that remove or find a
specific element they need to handle
situations where the INDEX being sought
is not in the range of the list
In these instances, you need to throw an
IndexOutOfBoundsException
33
Arraylist:
Where it fits in the Collections Hierarchy:
ArrayList implements the List interface
therefore it MUST provide for behaviors
for all of the methods in the interface
A Look at java.util.ArrayList:
public class ArrayList extends
AbstractList
implements List
34
 class java.util.ArrayList
Notes:
 AP Computer Science AB students need to know that
ArrayList implements List & which methods from
ArrayList implement those specified by List.
Required methods specified by interface java.util.List
 ListIterator listIterator() (AB only)
 int size()
 boolean add(Object x)
Required methods not part of interface java.util.List
 E get(int n)
 void set(int n, E element)
 boolean add(int n, E element)
 E remove(int n)
35
Lets look at the java.util.ArrayList in the
Java API (javadocs)
Notice the Constructors and overloaded
methods as well as the Generic Type <E>
36
Working with the ArrayList:
In the previous lecture, Advanced Classes,
we used the Coin and Purse example. The
Purse had a Add method that simply
accumulated the total value of coins in the
purse
However, it did NOT keep track of each
individual Coin or Traveler Check
37
Suppose we were to modify the
requirements of the Purse class to
maintain information on EACH separate
Coin in the Purse.
How could we accomplish this ?
38
One way would be to maintain an Array of
coins
The limitation of this would be that, unless
we knew how many Coins we would have
the array would be too big or too small
39
We might have to repeatedly have to
resize the array (reallocate new space) to
handle a large number of Coins.
Also, if we needed to obtain a specific
Coin in the array or modify a specific Coin
we would need to write that code from
scratch
This is where the ArrayList comes in
40
We could maintain an ArrayList of objects
that implement the Top Interface
In the Purse class we would add a new
class level attribute and modify the
constructor:
private ArrayList myArray;
public Purse ()
{
myArray = new ArrayList(100);
// initial capacity of 100 objects
}
41
This array list can hold any type of object
but we will limit it to any object that
implements the Top interface
We then would need to maintain the
elements every time the user added a new
coin or travelers check to the purse:
42
 Adding an element:
 We are adding an instance of a class that implements
the Top interface to the ArrayList
public void add(Top ci)
{
// code here
if (count == 0 || max.getTop() < ci.getTop() )
{
max = ci;
}
count++;
sum += ci.getTop();
// added for arraylist
// add new "coin" or "TC" superobject to list
myArray.add(ci);
}
43
There is also an overloaded add method
that adds an object at a specified index,
sliding all elements at that index and
higher up one element --- TRY THIS ONE
ON YOUR OWN
44
Get the Size:
Instead of using the count attribute, we
can use the ArrayList’s size method
public int getCount()
{
// return count;
return myArray.size();
}
45
Retrieve (Get) an Element:
public Object getElement(int i)
{
return myArray.get(i);
}
Realize that the get method of ArrayList
returns a generic Object reference
You must cast this return type to the
appropriate child / sub class before using
it
46
 SPVM…
Object o = myPurse.getElement(1);
if (o instanceof Coin)
{
System.out.println("the 2nd element in the Purse is a
Coin");
}
o = myPurse.getElement(2);
if (o instanceof TravelerCheck)
{
System.out.println("the 3rd element in the Purse is a
TC");
}
}
 The output results in both out messages being displayed
47
Modify (Set) the State of an Element :
This method mutates an existing object in
the ArrayList
It accepts an index and an Object and
returns the object that was replaced
Set can only overwrite existing values and
NOT create new elements in the List
48
public Object setElement(int e, Object o)
{
return myArray.set(e, o);
}
 SPVM…
// modify an element -- replace a Coin with a TC
o = myPurse.setElement(0, myStuff[2]);
if (o instanceof Coin)
{
System.out.println("the 1st element was a
Coin");
}
49
Remove an element:
This method will remove a given element
from the list and return it
It will move all elements from the index
removed forward up one place and reduce
the logical size of the List by 1
50
public Object RemoveElement(int i)
{
return myArray.remove(i);
}
SPVM…
51
// remove an element
o = myPurse.RemoveElement(1);
if (o instanceof Coin) // TRUE
{
System.out.println("the 2nd element Coin is
removed");
}
System.out.println("There are " +
myPurse.getCount() + " Objects in the Purse");
o = myPurse.getElement(2);
// the result is an IndexOutOfBoundsException
// as there are now only 2 elements in the
// ArrayList
52
TPS: How Can we display the contents
of the Purse ?
53
 ANS:
// Add to SuperObject:
public String toString()
{
return myName;
}
Add to Purse:
public String toString()
{
String s = " ";
for(int x = 0; x < myArray.size(); x++)
{
s += ((SuperObject)myArray.get(x)).toString();
s += " ";
}
return s;
}
54
Call in SPVM:
// display the types of objects in the purse
String ss = myPurse.toString();
System.out.println("the elements in the
purse are now " + ss);
55
As one of your projects, you will convert
this old style use of ArrayList into a
Generic, TYPED version
This version of the code is ONLINE in the
newpurse.zip file in the code examples
section
56
Big-O of ArrayList:
The “cost” of an operation
Big-o of different options (AVERAGE CASE):
add contains remove size constructor
N N
N
1
1
Arraylist(uniqueness)
1 N or N*M N
N
1
ArrayList(all dups)
57
N
8
1024
1M
LogN
3
10
20
 Be aware that there are “hidden” details that
occur on an ArrayList that are Abstracted from
the user of this type of list implementation.
 The overloaded Add method requires the
ArrayList to MOVE many elements down the list
when a new item is added somewhere inside the
list. This effects efficiency
58
The same can be said for the Remove
method
In the worst case almost ALL of the
elements need to be shifted
The get and set methods operate in
constant time O (1) as regardless of the
list size, they require one step and are,
therefore, extremely efficient
59
Best Use for this type of Data Structure:
This data structure is excellent in
situations where the actual size of the
elements is not known until the program
executes, but once established remains
stable
This structure is also best used in cases
where specific elements are frequently
modified
60
When finding the value of a specific
element index is frequently performed
When you add objects to the end of the
list
When removing a specific object (index)
is frequently performed
61
TPS: How would you store Numbers in
an ArrayList ?
Java Essentials chapter 13 Section 3 p.530
62
Wrapping Numbers:
ArrayLists MUST contain objects
What if we need to maintain a list of
simple numbers ?
You must “wrap” these primitives in a
child of the Number class, HOWEVER…
63
Java Provides AUTO BOXING (barrons
p.181) where the primitive will
automatically be converted into the
appropriate class
Example:
ArrayList<Integer> x = new
ArrayList<Integer> ();
x.add(55);
55 is wrapped into an Integer instance
before the argument is passed to the add
method
64
There is also AUTO UNBOXING where a
returned number class is converted to its
primitive
Example:
int c = x.get(2);
The Integer object returned by get is
converted to its primitive version before
being assigned to the int variable c
65
Tips for the AP Exam:
Elements of a list start at index 0
Make sure any iteration on a list does not
go out of bounds by USING THE FOR
EACH LOOP
ArrayLists store Objects and you need to
TYPE the ArrayList to work with your
specific Object or Object Hierarchy using
Generics
66
Using equals with Array Lists uses the
TYPED Classes’ overloaded equals
method
67
Projects:
NewPurse
ListOfNumbers
68
TEST FOLLOWS THE
PROJECT DUE DATE
!!!
69