Transcript Data Structures and Java

Data Structures and Java
CS 105
Data structure


Data structure defined: A systematic way of
organizing and accessing data
Examples



Dictionary: words and definitions are arranged for
convenient lookup
Queue: data is arranged so that insertion and
removal follow the “first-in, first-out” rule
Data structures are often components of larger
programs

Course goals: recognize appropriate data structures
and implement them in Java correctly and efficiently
L7: Java
Slide 2
Review of Java Topics
The following Java features play an
important role when implementing data
structures in Java



Interfaces
Exceptions
The Java class hierarchy and the Object class
L7: Java
Slide 3
Interfaces



An interface indicates the method
signatures for the operations of a data
structure
An implementation of the data structure
is a Java class that implements this
interface to enforce the definition of all
methods
There can be multiple implementations of
the same interface/data structure
L7: Java
Slide 4
Example: Dictionary
Dictionary
SimpleDictionary
BetterDictionary
L7: Java
Slide 5
public interface Dictionary
{
public void addWord( String word, String definition );
public String getDefinition( String word );
}
public class SimpleDictionary implements Dictionary
{
// define addWord and getDefinition
}
public class BetterDictionary implements Dictionary
{
// another implementation
// define addWord and getDefinition
}
L7: Java
Slide 6
Exceptions


Some operations of data structures may
be invalid in certain situations
One option: handle the error within that
method by printing an error message


Can be annoying since the user of the
method may get the message interspersed
with other output
Better alternative: throw exceptions so
that the user of the method can decide
how to deal with the error
L7: Java
Slide 7
Exceptions in Java



Exceptions are handled using a try-catch
statement
Exceptions are thrown from the method that
could cause the exception
What needs to be done



Define a class that extends Exception
(the class may be empty)
In the method declaration, include a throws clause
In the method body, include a throw statement
where the exception occurs
L7: Java
Slide 8
Example
public class DuplicateWordException extends Exception
{ // this class could be empty
}
public class SimpleDictionary implements Dictionary
{
//…
public void addWord( String word, String definition )
throws DuplicateWordException
{
if ( getDefinition( word ) != null )
throw new DuplicateWordException();
// code to add dictionary entry here…
}
// …
}
L7: Java
Slide 9
Example
Dictionary d = new SimpleDictionary();
try
{
d.addWord( “bat”, “mammal with wings” );
d.addWord( “cat”, “animal with whiskers” );
d.addWord( “bat”, “equipment used in baseball” );
d.addWord( “elephant”, “a large mammal” );
An exception
will be
thrown on
this call
}
catch( DuplicateWordException e )
{
System.out.println( “Duplicate Word Error” );
}
L7: Java
Slide 10
More on Exceptions


Different kinds of exceptions can be
handled using a try-catch chain
Can have a more elaborate exception
class by defining exception/error details
inside the class; for example:


error message
additional data about the error
(in the example, the word that causes the
duplicate to occur can be stored in the
DuplicateWordException class)
L7: Java
Slide 11
RuntimeException


Make the exception class extend
RuntimeException instead of Exception
whenever you do not want to require
that the exception be caught
The user of the method may or may not
use a try-catch statement


A try-catch is required for Exceptions that
are not RuntimeExceptions
If not within a try-catch and an exception
occurs, the program aborts
L7: Java
Slide 12
Interfaces and Exceptions


In general, when a class implements an
interface, the throws clause should be
present in both the interface and the
class that implements it
However, an implementing class can
throw additional exceptions as long as
they are runtime exceptions
L7: Java
Slide 13
Inheritance hierarchy



The extends keyword/feature in Java
creates an inheritance hierarchy
If a class does not extend another class,
it implicitly extends Object, a built-in
class in Java
This means all classes are subclasses of
Object

Variables of type Object can refer to an
instance of any class
L7: Java
Slide 14
Object and data structures


When establishing interfaces for data
structures, it might be better to use the Object
class instead of particular types
Example for the Queue interface:
public void enqueue( Object o );
public Object dequeue();
instead of
Supports
Strings and
other types of
objects
public void enqueue( String s );
public String dequeue();

Will need to cast when retrieving an object
from the data structure:
String s = ( String ) q.dequeue();
L7: Java
Slide 15
Primitive types & wrapper classes

Minor problem in Java: primitive types like int and
double are treated differently


Workaround: use wrapper classes




ints and doubles are not objects, so it is not straightforward to
have a Queue of integers or doubles
Each primitive type has a corresponding Java wrapper class:
e.g., int -> Integer, double -> Double
Instances of these wrapper classes are now legitimate objects
javap java.lang.WrapperClass for methods under these
classes
Example: if you want to enqueue/dequeue an integer,

Queue q = new Queue();
q.enqueue( new Integer( 5 ) );
int result = ((Integer) q.dequeue()).intValue();
L7: Java
Slide 16
Autoboxing


Recent addition to Java: “automatic”
conversion between primitive types and
wrapper classes
Instead of this:


Queue q = new Queue();
q.enqueue( new Integer( 5 ) );
int result = ((Integer) q.dequeue()).intValue();
We now do this:

Queue q = new Queue();
q.enqueue( 5 );
int result = (Integer) q.dequeue();
L7: Java
Slide 17
Generics


Generics: another recent addition to Java
Recall array lists in CS 21a


We can program our data structures so that contents
are restricted to instances of a particular class



ArrayList<BankAccount> list;
// this array list contains BankAccount objects
Queue<String> q;
// queue of strings
q.enqueue( something ); // something must be a string
This way, a data structure is implemented without
specifying the type of the content
Generics are beyond the scope of this course 

We will use the Object class instead to support any kind of
content type; sufficient for this course
L7: Java
Slide 18
Summary



Interfaces allow us to standardize
method signatures and to have multiple
implementations in a uniform manner
Exceptions allow us to elegantly handle
errors/unexpected situations
The Object class allows our data
structures to contain instances of any
class or type
L7: Java
Slide 19