Transcript Data Structures and Java

Data Structures
and Java
CS 110: Data Structures and Algorithms
First Semester, 2010-2011
Learning Objectives
► Review
Interface, Exceptions, and
Generics in Java
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
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
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
Example: Dictionary
Dictionary
Simple
Dictionary
Better
Dictionary
Example: Dictionary
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
}
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
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
►
Example
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…
}
//…
}
public class DuplicateWordException extends Exception
{
// this class could be empty
}
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" );
}
catch( DuplicateWordException e )
{
System.out.println( "Duplicate Word Error" );
}
An exception
will be
thrown at
this call
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)
►
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
►
► If
A try-catch is required for Exceptions that are
not RuntimeExceptions
not within a try-catch and an exception
occurs, the program aborts
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
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
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();
Primitive Types & Wrapper Classes
►
►
►
Minor problem in Java: primitive types like int and double are
treated differently
► ints and doubles are not objects, so it is not straightforward to
have a Queue of integers or doubles
Workaround: use wrapper classes
► 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();
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();
Generics
Generics: another recent addition to Java
► Recall array lists in CS 21a
►
►
►
ArrayList<BankAccount> list;
// this array list contains BankAccount objects
We can program our data structures so that contents
are restricted to instances of a particular class
►
Queue<String> q;
q.enqueue( something );
// queue of strings
// 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
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