Transcript 04-collections_arraylist

TCSS 143, Autumn 2004
Lecture Notes
Introduction to Collections:
Array List
1
Collections

collection: an object that stores a group of objects
inside it; a.k.a. a "data structure"
 the objects stored are called elements
 some collections allow duplicates, some don't
 some maintain an ordering, some don't
 an array is like a very crude "collection"
 typical operations: add element, remove element,
clear all elements, contains or find element, get size

examples:
java.util.ArrayList, java.util.HashMap,
java.util.TreeSet
2
Collection interface

Java provides an interface
java.util.Collection with the following
methods:
public boolean add(Object o)
Appends the specified element to this collection.
public void clear()
Removes all of the elements of this collection.
public boolean contains(Object o)
Returns true if this collection contains the specified element.
public boolean containsAll(Collection coll)
Returns true if this collection contains all of the elements in the
specified collection.
3
Collection interface, cont'd.
public boolean isEmpty()
Returns true if this list contains no elements.
public Iterator iterator()
Returns a special object for examining the elements of the list in
order (seen later).
public boolean remove(Object o)
Removes the first occurrence in this list of the specified element.
public int size()
Returns the number of elements in this list.
public Object[] toArray()
Returns an array containing all of the elements from this list.
4
Lists

list: an ordered sequence of elements, each
accessible by a 0-based index

one of the most basic collections
5

List features




maintains ordering in order elements were added
(new elements are added to the end by default)
duplicates and null elements allowed
list manages its own size; user of the list does not
need to worry about overfilling it
operations: add element to end of list, insert
element at given index, clear all elements, search
for element, get element at given index, remove
element at given index, get size
6
List interface

Java interface java.util.List adds the
following methods to those in Collection:
public void add(int index, Object o)
Inserts the specified element at the specified position in this list.
public Object get(int index)
Returns the element at the specified position in this list.
public int indexOf(Object o)
Returns the index in this list of the first occurrence of the
specified element, or -1 if the list does not contain it.
7
List interface, cont'd.

More java.util.List methods:
public int lastIndexOf(Object o)
Returns the index in this list of the last occurrence of the specified
element, or -1 if the list does not contain it.
public Object remove(int index)
Removes the object at the specified position in this list.
public Object set(int index, Object o)
Replaces the element at the specified position in this list with the
specified element.
8
Some list questions




all of the list operations on the previous slide
could be performed using an array instead!
open question: What are some reasons why we
might want to use a special List class, rather
than an array, to store our data?
thought question: How might a List be
implemented, under the hood?
why do all the List methods use type Object?
9
ArrayList

Class java.util.ArrayList implements
List using an array as the internal
implementation
10
ArrayList, cont'd.

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
 can call toString on an ArrayList to
print it
 remember to import java.util.*;

11
ArrayList vs. array

construction



storage



String[] names = new String[5];
ArrayList namesList = new ArrayList();
names[0] = "Jennifer";
namesList.add("Jennifer");
retrieval


String name = names[0];
String name = (String)namesList.get(0);

Why the type-cast? What happens without it?
12
ArrayList vs. array, cont'd.

removal (of element #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();
13
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);
System.out.println(list2);
14
Storing primitives in collection


collections like ArrayList store Objects, not
primitive values like int, double, char, boolean
to store these primitives, we need special object
wrappers




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();
15
Collections class

Class java.util.Collections has many utility
methods that do useful things to collections
public
public
public
public
public
public
public
public
static
static
static
static
static
static
static
static
void copy(List dest, List src)
void fill(List list, Object value)
Object max(Collection coll)
Object min(Collection coll)
void reverse(List list)
void shuffle(List list)
void sort(List list)
void swap(List list, int i, int j)
16
Abstract data types (ADTs)

abstract data type: a specification for a
collection of data and the operations that can
be performed on it




does not specify how the collection must be
implemented internally
does specify what ways the data can be viewed and
manipulated (what methods the ADT has)
many collections may implement the same ADT
(example: linked list and array list implement List)
in Java, interfaces specify ADTs, and classes
implement the specific collections
17
Practice problems


Using Scanner, read names from the
keyboard until an empty line is entered. Store
the names in an ArrayList, and print the
names separated by commas after all have
been entered.
Use an ArrayList to store and print the
numbers 1-50 in random order, one per line.
18
References

Koffman, Chapter 4, pp. 193-199
19