Transcript 01b-arraylist_review

TCSS 342, Winter 2005
Lecture Notes
Array List Review
Weiss Ch. 4, pp. 43-45
Weiss Ch. 6, pp. 190-201
1
Java's ArrayList class

Class java.util.ArrayList implements
List using an array as the internal
implementation


when you want to use ArrayList, remember to
import java.util.*;
encapsulates array and # of elements (size)
2
ArrayList features




think of it as an auto-resizing array that can
hold any type of object, with many convenient
methods
maintains most of the benefits of arrays, such
as fast random access
frees us from some tedious operations on
arrays, such as sliding elements and resizing
can call toString on an ArrayList to print
its elements

[1, 2.65, Marty Stepp, Hello]
3
ArrayList vs. array usage

construction



storing an element




String[] names = new String[5];
ArrayList namesList = new ArrayList();
names[0] = "Jennifer";
namesList.add("Jennifer");
namesList.set(0, "Jennifer");
// or,
retrieval of an element's value


String name = names[0];
String name = (String)namesList.get(0);

Why is the type-cast needed? What happens without it?
4
ArrayList vs. array, cont'd.

removal of an element (at index 2)



search to see if "Marty" is there



for (int i = 2; i < names.length - 1; i++)
names[i] = names[i+1];
namesList.remove(2);
for (int i = 0; i < names.length; i++)
if (names[i].equals("Marty")) { ... }
if (namesList.contains("Marty")) { ... }
erase all names from the list


for (int i = 0; i < names.length; i++)
names[i] = null;
namesList.clear();
5
ArrayList and references


a collection such as ArrayList stores
references to its elements
if two collections refer to the same object, side
effects from one can be seen in the other
BankAccount acct = new BankAccount("Ed", 0);
ArrayList list1 = new ArrayList();
list1.add(acct);
ArrayList list2 = new ArrayList();
list2.add(acct);
acct.deposit(100.00);
System.out.println(list1); // the lists will
System.out.println(list2); // show the $100.00!
6
Storing primitives in collection


collections like ArrayList store objects, not primitive
types like int, double, char, boolean
to store these primitives, we need special object
wrappers (see Java API docs for details):




class
class
class
class
Integer / public int intValue()
Double / public double doubleValue()
Character / public char charValue()
Boolean / public boolean booleanValue()
ArrayList list = new ArrayList();
list.add(new Integer(42));
int value = ((Integer)list.get(0)).intValue();
7
A list of ints, using an array


We like arrays, but they can be clunky to use
Let's write a class that implements a "list" as
described previously, of ints, using an array




it will wrap up the functionality of an array of int,
but make it simpler to use and have more power
we'll call it IntArrayList
behavior: add, remove, get size, is empty, clear, get
element, set element, search for element
the list's "size" will be the number of elements
we've added to it (0 <= index < size)
8
IntArrayList vs. array

construction


int[] numbers = new int[5];
IntArrayList numberList = new IntArrayList();


storage



Where did the capacity of 5 go? Why didn't we use it?
numbers[0] = 42;
numberList.set(0, 42);
retrieval


int number = numbers[0];
int number = numberList.get(0);
9
IntArrayList vs. array, cont'd.

removal (of element #2)



search to see if 27 is there



for (int i = 2; i < numbers.length - 1; i++)
numbers[i] = numbers[i+1];
numberList.remove(2);
for (int i = 0; i < numbers.length; i++)
if (numbers[i] == 27) { ... }
if (numberList.contains(27)) { ... }
erase all numbers from the list


for (int i = 0; i < numbers.length; i++)
numbers[i] = 0;
numberList.clear();
10
Example IntArrayList usage
IntArrayList list = new IntArrayList();
for (int i = 0; i < 20; i++)
list.add(i*i);
System.out.println(list);
System.out.println("element 5: " + list.get(5));
list.set(7, 999);
list.add(4, 444);
System.out.println("Index of 121? " +
list.indexOf(121));
System.out.println("is 10 in the list? " +
list.contains(10));
11
Pros and cons of IntArrayList

pro (benefits)




simple syntax
don't have to keep track of array size and capacity
has some powerful methods (indexOf, add, contains)
con (drawbacks)

it only works for ints!


we can make arrays of any type, but we can only make
an IntArrayList of ints
syntax is a bit different to learn and use
12
IntArrayList practice problems


Implement it! (implementation on web site)
Rewrite our maximum subsequence sum
solution from last time, using an IntArrayList
instead of an array.
13