Transcript Here are the notes on Chapter 3

Chapter 3
Collections
Objectives
Define the concepts and terminology
related to collections
 Explore the basic structures of the Java
Collections API
 Discuss the abstract design of collections
 Define a set collection
 Use a set collection to solve a problem
 Examine an array implementation of a set

Introduction
A
collection is an object that gathers
and organizes other objects.
 The collection defines the specific
ways in which the elements of the
collection can be accessed and
managed.
 Collections can be separated into two
broad categories: linear and nonlinear.
Order of the Collection

The organization of the elements in
a collection, relative to each other,
is usually determined by one of two
things:
1. The order in which they were added
2. Some inherent relationship among the
elements themselves
Abstract Data Types
An abstraction hides or ignores certain
details at certain times.
 The interface is an abstraction that allows
us to control the object.
 A collection is an abstraction.
 The user interacts with the collection
through the interface.
 The details of how the collection is
implemented is hidden from the user.

Example of an Interface
Collections Concerns
How does the collection operate,
conceptually?
 How do we formally define the interface to
the collection?
 What kinds of problems does the collection
help us solve?
 In which various ways might we
implement the collection?
 What are the benefits and costs of each
implementation?

Related Terms
Data type is a group of values and
operations defined on those values.
 The primitive types in Java are great
examples.
 An abstract data type (ADT) is a data type
whose values and operations are not
inherently defined within a programming
language.
 A data structure is the collection of
programming constructs used to
implement a collection.

Java Collections API
Why should we learn to program
collections, when Java already gives us a
set of collections?
 This set of collections is only a subset of
the collections you may want to use.
 The classes may not be implemented the
way you desire.
 The study of software development
requires a deep understanding of the
issues involved in the design of collections
and the data structures used to implement
them.

Set Collection
 Set
is a collection of element with no
duplicates.
 We can assume that there is no
particular positional relationship
among the element of the set.
 A set is a non-linear collection.
Conceptual View of a Set
Common Operations
 Every
collection has operations that
allow the user to add and remove
 They usually will vary in the details.
 Additional operations such as
isEmpty and size are common.
Interfaces
 An
interface allows us to specify the
method signatures.
 The interface name can be used as
the type of the object reference,
which can be assigned any object of
any class that implements the
interface.
 Interfaces can also be generic
SetADT<T>
package jss2;
import java.util.Iterator;
public interface SetADT<T>
{
/** Adds one element to this set, ignoring duplicates. */
public void add (T element);
/** Removes and returns a random element from this set. */
public T removeRandom ();
/** Removes and returns the specified element from this set. */
public T remove (T element);
/** Returns the union of this set and the parameter */
public SetADT<T> union (SetADT<T> set);
/** Returns true if this set contains the parameter */
public boolean contains (T target);
SetADT<T>
/**
Returns true if this set and the parameter contain exactly
the same elements */
public boolean equals (SetADT<T> set);
/** Returns true if this set contains no elements */
public boolean isEmpty();
/** Returns the number of elements in this set */
public int size();
/** Returns an iterator for the elements in this set */
public Iterator<T> iterator();
/** Returns a string representation of this set */
public String toString();
}
UML for SetADT
Iterators
 An
iterator is an object that provides
the means to iterate over a
collection.
 The iterator interface is defined in
the Java standard class library with
two primary abstract methods:
– hasNext – returns true if the collection
has more elements.
– next – returns the next element in the
iteration.
Iterator Issues
What happens if the collection is modified
while the iterator is in use?
 Most of the collections in Java are fail-fast.
 Meaning they should throw an exception if
the collection is modified while the iterator
is in use.
 However the documentation regarding this
behavior explicitly states that this is not
guarnteed.

Iterator Issues
 How
do you handle these
modification issues?
 Can make iterators that allow
concurrent modificaion and reflect
the changes in the collection.
 Make iterators that iterate over a
snapshot of the collection so
modification makes no changes to
the iterators.
Implementing a Set with Arrays
 Design
Questions:
– How do you implement a non-linear
collection with a linear data structure?
– How do you manage the fact that the
size of an array is fixed?
Managing Capacity
 What
full?
do we do when the array is
– We could throw an exception.
– We could return a success indication
from the add method that the use can
check.
– We could increase the capacity when it
is full.
Array implementation of a set
ArraySet - Constructors
ArraySet - size and isEmpty
ArraySet - add
ArraySet - expandCapacity
ArraySet - addAll
ArraySet - removeRandom
ArraySet - remove
ArraySet - union
ArraySet - contains
ArraySet - equals
ArraySet - equals (continued)
ArraySet - iterator
Listing 3.4
Listing 3.4 (cont.)
Listing 3.4 (cont.)
Analysis of ArraySet
Adding an element to the set is O(n)
because of the need to check to see if
the element is already in the set
 Expanding the capacity is also O(n)
 Removing a particular element,
because it must be found, is O(n)
 Removing a random element is O(1)
 Adding all elements of another set is
O(n)
 The union of two sets is O(n+m),
where m is the size of the second set
