Transcript ArrayList - 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:
Java.util.ArrayList
Java Essentials Chapter 13
p.521
Java Essentials Study Guide
Chapter 11 p.163 & Chapter 16
p.263
Java Methods Data Structures
Chapter 2 p.33
APCS Course Description p.27
Paragraphs 2 & 3
3
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.
4
Intro:
With the Arrays Java class (it is really a
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.
5
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.
6
AP AB Subset: Lets read the Course
Description regarding ArrayList on
page 27 (paragraphs 2 & 3)
7
 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
Big-O of ArrayList
Best Use for this type of Data Structure
Wrapping Numbers
What is critical for the AP Exam
8
 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
9
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.
10
11
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)
12
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
13
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
14
The specific implementation of an
Abstract Structure depends on the needs
of the system or problem you are
attempting to resolve.
15
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.
16
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.
17
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).
18
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.
19
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
20
A First look at the List interface
java.util.List interface:
boolean add(Object x)
int size()
Object get(int index)
Object set(int index, Object x)
// replaces the element at index with x
// returns the element formerly at the
specified position
Iterator iterator()
ListIterator listIterator()
21
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
22
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.
23
Why is such an Interface Important ?
What benefits, if any, does it provide ?
What does a List limit its elements to be ?
24
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
25
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
26
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
27
 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
 Object get(int n)
 void set(int n, Object x)
 boolean add(int n, Object x)
 Object remove(int n)
28
Lets look at the java.util.ArrayList in the
Java API (javadocs)
Notice the Constructors and overloaded
methods
29
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
30
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 ?
31
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
32
We might have to repeatedly have to re
size 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
33
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
}
34
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:
35
 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);
}
36
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
37
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();
}
38
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
39
 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
40
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
41
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");
}
42
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
43
public Object RemoveElement(int i)
{
return myArray.remove(i);
}
SPVM…
44
// 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
45
TPS: How Can we display the contents
of the Purse ?
46
 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;
}
47
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);
48
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)
49
N LogN
8 3
1024
10
1M 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
50
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
51
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
52
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
53
TPS: How would you store Numbers in
an ArrayList ?
Java Essentials chapter 13 Section 3 p.530
54
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
55
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
ArrayLists store Objects and to access
these objects, you must cast them to the
appropriate type
56
Using equals with Array Lists uses the
default Object equals and compares
references and NOT contents.
So it returns TRUE if two ArrayList
elements are the same, otherwise it
returns false
57
Projects:
NewPurse
ListOfNumbers
58
TEST FOLLOWS THE
PROJECT DUE DATE
!!!
59