Java程序辅导

1COMP2160/2860 - Data Structures
The University of Sydney
School of Information Technologies
Week 1: 
- Introduction
- Abstract data types
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-2
Welcome to COMP2160
• Dr Michael Charleston (Unit coordinator)
Rm 412
mcharleston@it.usyd.edu.au
• Dr Tasos Viglas
Rm 411 
tasos@it.usyd.edu.au
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-3
Lectures
• Tuesdays 15:00-17:00, 
Carslaw Lecture Theatre 373
• Labs and tutorials on Wednesdays and 
Thursdays (see unit website for details)
• COMP2860:
Advanced tutorials
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-4
Announcements
• Website
http://www.it.usyd.edu.au/~comp2160
• Also accessible from webCT
• All tutorials start next week
– School of IT Lab 115
– 1 hour
• Tutors
– Enoch Lau (Wednesdays)
– Timothy De Vries (Thursdays)
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-5
Textbook:
Data Abstraction & 
Problem Solving with 
Java 
2e
COMP2160/2860 Data Structures
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-6
COMP2860 (Advanced)
• Same textbook
• Extra material for the advanced section
(advanced tutorials)
2COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-7
Assessment
% of final markAssessment
60Final Exam
10Assignment 2
10Assignment 1
2 x 10 = 202 quizzes
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-8
Marks
• Quizzes are during lecture times
• Quizzes will focus on theoretical aspects
Assignments will be more practical
• Final exam mark must be above 40% to 
pass this course
• Final mark may undergo scaling
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-9
COMP2160 …
• is not about Java
• is not only a programming course
• is not “Problem Based Learning”
• includes both theoretical and practical 
work
• involves programming in Java
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-10
COMP2160 is good for you
• Toolbox for solving complex problems
• Prevent re-inventing the wheel
• Efficient implementation of algorithms
• Building blocks of programs
• Better understanding of programs
• Modular solutions
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-11
What is a data structure?
• A table of data including structural 
relationships
– Donald Knuth (Turing award ’74)
• Algorithms + data structures = programs
– Niklaus Wirth (Turing award ’84)
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-12
Data structures
• Programs use data
• Data needs to be stored and accessed
• Efficiently
• Different applications have different 
requirements
3COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-13
Course contents (short)
• List structures, stacks, queues
• Trees
• Sorting
• Heaps, priority queues
• Hashing
• Graphs
• Introduction to algorithms
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-14
Course contents (long)
• List structures
• Stacks
• Queues
• Implementation issues
– Arrays, linked lists
– Doubly linked lists
– Dynamic or static
• Recursion
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-15
Course contents (long)
• Trees
• Binary trees
• Balanced trees
– 2-3 trees, red-black
• Binary search trees
• Recursion 
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-16
Course contents (long)
• Tables
– Items with a search key
• Priority queues
• Heaps and heapsort
• Hashing
• Hash functions and hash tables 
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-17
Course contents (long)
• Sorting
• Selection and insertion sort
• Bubblesort
• Mergesort
• Quicksort
• Heapsort
• Comparison of sorting algorithms
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-18
Course contents (long)
• Graphs
• Representations
• Graph traversals
• Topological sorting
• Spanning trees
• Shortest paths
4COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-19
Course contents (long)
• Advanced Data structures
• Binomial queues
• Treaps
• Disjoint sets/union find
• Fibonacci heaps
• Analysis of data structures
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-20
What is Problem Solving?
• Problem solving
– The process of taking the statement of a problem and 
developing a computer program that solves that problem
• A solution consists of:
– Algorithms
• Algorithm: a step-by-step specification of a method to solve a 
problem within a finite amount of time
– Ways to store data
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-21
What is a Good Solution?
• A solution is good if:
– The total cost it incurs over all phases is minimal
• Specification, Design, Verification
• Coding, testing, refining
• Maintenance 
• The cost of a solution includes:
– Computer resources that the program consumes
– Difficulties encountered by those who use the program
– Consequences of a program that does not behave correctly
• Programs must be well structured and documented
• Efficiency is only one aspect of a solution’s cost
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-22
Achieving a Modular Design:
Abstraction and Information Hiding
• A modular solution to a problem should 
specify what to do, not how to do it
• Abstraction
– Separates the purpose of a module from its 
implementation
• Procedural abstraction
– Separates the purpose of a method from 
its implementation
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-23
Abstraction and Information 
Hiding
Figure 1.2
The details of the sorting algorithm are hidden from other parts of the solution.
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-24
Abstraction and Information 
Hiding
• Data abstraction
– Focuses on the operations of data, not on the 
implementation of the operations
– Abstract data type (ADT)
• A collection of data and a set of operations on the data
• An ADT’s operations can be used without knowing how 
the operations are implemented, if:
– the operations’ specifications are known
– Data structure
• A construct that can be defined within a programming 
language to store a collection of data
5COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-25
Abstraction and Information 
Hiding
• Public view of a module
– Described by its specifications
• Private view of a module
– Consists of details which should not be described by the 
specifications
• Principle of information hiding
– Hide details within a module
– Ensure that no other module can tamper with these hidden 
details
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-26
A simple example
keyboard Operating
System
key buffer
Press a key: key code is written in the buffer
Operating system reads keys First In First Out (FIFO)
How do we implement the buffer ?
What does the buffer need to do ?
Two things: 
add keys to the queue or en-q
read keys from the queue or de-q
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-27
Buffer example
key buffer
Need a data structure that supports two operations: enq and deq.
The actual implementation is not part of this abstract description,
or Abstract Data Type (ADT)
Any implementation can be used
• Array with two pointers
• Linked list
enq deq
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-28
Abstract Data Types
• Abstract description of a data structure
• Describe what the data structure does
– not how it does it
• How to use the data structure
– interface
• Properties of the data structure
– example: operation en-queue must be O(log n)
– buffer example: both operations O(1)
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-29
Object-Oriented Design
• Principles of object-oriented programming (OOP)
– Encapsulation
• Objects combine data and operations
– Inheritance
• Classes can inherit properties from other classes
– Polymorphism
• Objects can determine appropriate operations at execution time 
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-30
Top-Down Design
• Object-oriented design (OOD)
– Produces modular solutions for problems that 
primarily involve data
• Top-down design (TDD)
– Produces modular solutions for problems in which 
the emphasis is on the algorithms
– A task is addressed at successively lower levels of 
detail
6COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-31
Top-Down Design
Figure 1.4
A structure chart showing the hierarchy of modules
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-32
General Design Guidelines
• Use Object Oriented and Top Down Design
– Use Object Oriented Design for problems that primarily 
involve data
– Use Top Down Design to design algorithms for an 
object’s operations
• Focus on what, not how, when designing both 
ADTs and algorithms
• Consider incorporating previously written 
software components into your design
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-33
A Summary of Key Issues in 
Programming
• Modularity
– Has a favorable impact on:
• Constructing the program
• Debugging the program
• Reading the program
• Modifying the program
• Eliminating redundant code
• Modifiability
– Ways to make a program easy to modify:
• Use of methods
• Named constants
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-34
A Summary of Key Issues in 
Programming
• Ease of Use
– Considerations for the user interface
• In an interactive environment, the program 
should prompt the user for input in a clear 
manner
• A program should always echo its input
• The output should be well labeled and easy to 
read
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-35
A Summary of Key Issues in 
Programming
• Fail-Safe Programming
– Fail-safe program
• A program that will perform reasonably no 
matter how anyone uses it
– Types of errors:
• Errors in input data
• Errors in the program logic
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-36
A Summary of Key Issues in 
Programming
• Style
– Five issues of style
• Extensive use of methods
• Use of private data fields
• Error handling
• Readability
• Documentation
7COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-37
A Summary of Key Issues in 
Programming
• Debugging
– Programmer must systematically check a 
program’s logic to determine where an 
error occurs
– Tools to use while debugging:
• Watches
• Breakpoints
•System.out.println statements
• Dump methods
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-38
Summary
• Software engineering studies ways to facilitate the 
development of computer programs
• Software life cycle consists of:
– Specifying the problem
– Designing the algorithm
– Analyzing the risks
– Verifying the algorithm
– Coding the programs
– Testing the programs
– Refining the solution
– Using the solution
– Maintaining the software
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-39
Summary
• An evaluation of the quality of a solution must 
take into consideration
– The solution’s correctness
– The solution’s efficiency
– The time that went into the development of the 
solution
– The solution’s ease of use
– The cost of modifying and expanding the solution
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-40
Summary
• A combination of object-oriented and top-down 
design techniques will lead to a modular solution
• The final solution should be as easy to modify as 
possible
• A method should be as independent as possible and 
perform one well-defined task
• A method should always include an initial comment 
that states its purpose, its precondition, and its 
postcondition
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-41
Summary
• A program should be as fail-safe as possible
• Effective use of available diagnostic aids is one of the 
keys to debugging
• To make it easier to examine the contents of complex 
data structures while debugging, dump methods that 
display the contents of the data structures should be 
used
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-42
Abstract Data Types
• Modularity
– Keeps the complexity of a large program 
manageable by systematically controlling the 
interaction of its components
– Isolates errors
– Eliminates redundancies
– A modular program is
• Easier to write
• Easier to read
• Easier to modify
8COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-43
Abstract Data Types
Figure 3.1
Isolated tasks: the implementation of task T does not affect task Q
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-44
Abstract Data Types
• The isolation of modules is not total
– Methods’ specifications, or contracts, govern how they interact with 
each other
Figure 3.2
A slit in the wall
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-45
Abstract Data Types
• Typical operations on data
– Add data to a data collection
– Remove data from a data collection
– Ask questions about the data in a data collection
• Data abstraction
– Asks you to think what you can do to a collection 
of data independently of how you do it
– Allows you to develop each data structure in 
relative isolation from the rest of the solution
– A natural extension of procedural abstraction
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-46
Abstract Data Types
• Abstract data type (ADT)
– An ADT is composed of
• A collection of data
• A set of operations on that data
– Specifications of an ADT indicate
• What the ADT operations do, not how to 
implement them
– Implementation of an ADT
• Includes choosing a particular data structure
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-47
Abstract Data Types
• Data structure
– A construct that is defined within a programming language to 
store a collection of data
– Example: arrays
• ADTs and data structures are not the same
• Data abstraction
– Results in a wall of ADT operations between data structures 
and the program that accesses the data within these data 
structures
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-48
Abstract Data Types
Figure 3.4
A wall of ADT operations isolates a data structure from the program that uses it
9COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-49
Specifying ADTs
• In a list
– Except for the first and last 
items, each item has
• A unique predecessor
• A unique successor
– Head or front
• Does not have a 
predecessor
– Tail or end
• Does not have a successor
Figure 3.5
list A grocery 
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-50
The ADT List
• ADT List operations
– Create an empty list
– Determine whether a list is empty
– Determine the number of items in a list
– Add an item at a given position in the list
– Remove the item at a given position in the list
– Remove all the items from the list
– Retrieve (get) the item at a given position in the list
• Items are referenced by their position within the list
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-51
The ADT List
• ADT List operations – needed ?
– Remove all the items from the list
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-52
The ADT List
• ADT List operations – all needed ?
– Remove all the items from the list
• Determine number of items n in the list
• for i=1 to n remove item at position i
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-53
The ADT List
• Specifications of the ADT operations
– Define the functionality of the ADT list
– Do not specify how to store the list or how 
to perform the operations
• ADT operations can be used in an 
application without the knowledge of 
how the operations will be implemented
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-54
The ADT List
Figure 3.6
The wall between displayList and the implementation of the ADT list
10
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-55
The ADT Sorted List
• The ADT sorted list
– Maintains items in sorted order
– Inserts and deletes items by their values, 
not their positions
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-56
Designing an ADT
• The design of an ADT should evolve 
naturally during the problem-solving 
process
• Questions to ask when designing an 
ADT
– What data does a problem require?
– What operations does a problem require?
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-57
Axioms
• For complex abstract data types, the 
behavior of the operations must be 
specified using axioms
– Axiom: A mathematical rule
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-58
Axioms
• Axioms for the ADT List
– (aList.createList()).size() = 0
– (aList.add(i, x)).size() = aList.size() + 1
– (aList.remove(i)).size() = aList.size() – 1
– (aList.createList()).isEmpty() = true
– (aList.add(i, item)).isEmpty() = false
– (aList.createList()).remove(i) = error
– (aList.add(i, x)).remove(i) = aList
– (aList.createList()).get(i) = error
– (aList.add(i, x)).get(i) = x
– aList.get(i) = (aList.add(i, x).get(i+1)
– aList.get(i+1) = (aList.remove(i)).get(i)
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-59
Implementing ADTs
• Choosing the data structure to represent the ADT’s 
data is a part of implementation
– Choice of a data structure depends on
• Details of the ADT’s operations
• Context in which the operations will be used
• Implementation details should be hidden behind a 
wall of ADT operations
– A program would only be able to access the data structure 
using the ADT operations
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-60
Implementing ADTs
Figure 3.7
ADT operations provide access to a data structure
11
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-61
Implementing ADTs
Figure 3.8
Violating the wall of ADT operations
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-62
Java Classes
• Object-oriented programming (OOP) views a 
program as a collection of objects
• Encapsulation
– A principle of OOP
– Can be used to enforce the walls of an ADT
– Combines an ADT’s data with its method to form an object
– Hides the implementation details of the ADT from the 
programmer who uses it
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-63
Java Classes
Figure 3.9
An object’s data and 
methods are encapsulated
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-64
Java Classes
• A Java class
– A new data type whose instances are 
objects
– Class members
• Data fields
– Should almost always be private
• Methods
– All members in a class are private, unless 
the programmer designates them as public
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-65
Java Classes
• A Java class (Continued)
– Constructor
• A method that creates and initializes new 
instances of a class
• Has the same name as the class
• Has no return type
– Java’s garbage collection mechanism
• Destroys objects that a program no longer 
references
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-66
Java Classes
• Constructors
– Allocate memory for an object and can 
initialize the object’s data
– A class can have more than one 
constructor
– Default constructor
• Has no parameters
• Typically, initializes data fields to values the 
class implementation chooses
12
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-67
Java Classes
• Constructors (Continued)
– Compiler-generated default constructor
• Generated by the compiler if no constructor is 
included in a class
• Client of a class
– A program or module that uses the class
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-68
Java Classes
• Inheritance
– Base class or superclass
– Derived class or subclass
• Inherits the contents of the superclass
• Includes an extends clause that indicates the 
superclass
•super keyword
– Used in a constructor of a subclass to call the 
constructor of the superclass
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-69
Java Classes
• Object Equality
– equals method of the Object class
• Default implementation
– Compares two objects and returns true if they are 
actually the same object
• Customized implementation for a class
– Can be used to check the values contained in two 
objects for equality
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-70
Java Interfaces
• An interface
– Specifies methods and constants, but 
supplies no implementation details
– Can be used to specify some desired 
common behavior that may be useful over 
many different types of objects
– The Java API has many predefined 
interfaces
• Example: java.util.Collection
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-71
Java Interfaces
• A class that implements an interface must
– Include an implements clause
– Provide implementations of the methods of the interface
• To define an interface
– Use the keyword interface instead of class in the 
header
– Provide only method specifications and constants in the 
interface definition
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-72
Java Exceptions
• Exception
– A mechanism for handling an error during 
execution
– A method indicates that an error has 
occurred by throwing an exception
13
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-73
Java Classes
• A Java class
– A new data type whose instances are 
objects
– Class members
• Data fields
– Should almost always be private
• Methods
– All members in a class are private, unless 
the programmer designates them as public
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-74
Java Classes
• A Java class (Continued)
– Constructor
• A method that creates and initializes new 
instances of a class
• Has the same name as the class
• Has no return type
– Java’s garbage collection mechanism
• Destroys objects that a program no longer 
references
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-75
Java Classes
• Constructors
– Allocate memory for an object and can 
initialize the object’s data
– A class can have more than one 
constructor
– Default constructor
• Has no parameters
• Typically, initializes data fields to values the 
class implementation chooses
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-76
Java Classes
• Constructors (Continued)
– Compiler-generated default constructor
• Generated by the compiler if no constructor is 
included in a class
• Client of a class
– A program or module that uses the class
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-77
Java Classes
• Inheritance
– Base class or superclass
– Derived class or subclass
• Inherits the contents of the superclass
• Includes an extends clause that indicates the 
superclass
•super keyword
– Used in a constructor of a subclass to call the 
constructor of the superclass
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-78
Java Classes
• Object Equality
– equals method of the Object class
• Default implementation
– Compares two objects and returns true if they are 
actually the same object
• Customized implementation for a class
– Can be used to check the values contained in two 
objects for equality
14
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-79
Java Interfaces
• An interface
– Specifies methods and constants, but 
supplies no implementation details
– Can be used to specify some desired 
common behavior that may be useful over 
many different types of objects
– The Java API has many predefined 
interfaces
• Example: java.util.Collection
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-80
Java Interfaces
• A class that implements an interface must
– Include an implements clause
– Provide implementations of the methods of the interface
• To define an interface
– Use the keyword interface instead of class in the 
header
– Provide only method specifications and constants in the 
interface definition
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-81
Java Exceptions
• Exception
– A mechanism for handling an error during 
execution
– A method indicates that an error has 
occurred by throwing an exception
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-82
Java Exceptions
• Catching exceptions
– try block
• A statement that might throw an exception is 
placed within a try block
• Syntax
try {
statement(s);
} // end try
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-83
Java Exceptions
• Catching exceptions (Continued)
– catch block
• Used to catch an exception and deal with the 
error condition
• Syntax
catch (exceptionClass identifier) {
statement(s);
} // end catch
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-84
Java Exceptions
• Types of exceptions
– Checked exceptions
• Instances of classes that are subclasses of the 
java.lang.Exception class
• Must be handled locally or explicitly thrown 
from the method
• Used in situations where the method has 
encountered a serious problem
15
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-85
Java Exceptions
• Types of exceptions (Continued)
– Runtime exceptions
• Used in situations where the error is not 
considered as serious
• Can often be prevented by fail-safe 
programming
• Instances of classes that are subclasses of the 
RuntimeException class
• Are not required to be caught locally or 
explicitly thrown again by the method
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-86
Java Exceptions
• Throwing exceptions
– A throw statement is used to throw an 
exception
throw new exceptionClass (stringArgument);
• Defining a new exception class
– A programmer can define a new exception 
class
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-87
An Array-Based Implementation 
of the ADT List
• An array-based implementation
– A list’s items are stored in an array items
– A natural choice
• Both an array and a list identify their items by 
number
– A list’s kth item will be stored in 
items[k-1]
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-88
An Array-Based Implementation 
of the ADT List
Figure 3.10
An array-based implementation of the ADT list
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-89
List implementations
• Options for implementing an ADT
– Array
• Has a fixed size
• Data must be shifted during insertions and 
deletions
– Linked list
• Is able to grow in size as needed
• Does not require the shifting of items during 
insertions and deletions
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-90
An Array-Based Implementation 
of the ADT List
Figure 3.10
An array-based implementation of the ADT list
16
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-91
Preliminaries
Figure 4.1
a) A linked list of integers; b) insertion; c) deletion
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-92
Object References
• A reference variable
– Contains the location of an object
– Example
Integer intRef;
intRef = new Integer(5);
– As a data field of a class
• Has the default value null
– A local reference variable to a method
• Does not have a default value
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-93
Object References
Figure 4.2
A reference to an  
Integer object
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-94
Object References
• When one reference variable is assigned to 
another reference variable, both references 
then refer to the same object
Integer p, q;
p = new Integer(6);
q = p;
• A reference variable that no longer 
references any object is marked for garbage 
collection
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-95
Object References
Figure 4.3a-d
a) Declaring reference 
variables; b) allocating an 
object; c) allocating another 
object, with the dereferenced 
object marked for garbage 
collection
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-96
Object References
Figure 4.3e-g
e) allocating an object; f) 
assigning null to a 
reference variable; g) 
assigning a reference with 
a null value
17
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-97
Object References
• An array of objects
– Is actually an array of references to the 
objects
– Example
Integer[] scores = new Integer[30];
– Instantiating Integer objects for each array 
reference
scores[0] = new Integer(7);
scores[1] = new Integer(9); // and so on …
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-98
Object References
• Equality operators (== and !=)
– Compare the values of the reference variables, 
not the objects that they reference
• equals method
– Compares objects field by field
• When an object is passed to a method as an 
argument, the reference to the object is 
copied to the method’s formal parameter
• Reference-based ADT implementations and 
data structures use Java references 
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-99
Resizable Arrays
• The number of references in a Java array is 
of fixed size
• Resizable array
– An array that grows and shrinks as the program 
executes
– An illusion that is created by using an allocate and 
copy strategy with fixed-size arrays
• java.util.Vector class
– Uses a similar technique to implement a growable 
array of objects
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-100
Recursive Solutions
• Recursion
– An extremely powerful problem-solving 
technique
– Breaks a problem in smaller sub-problems
– An alternative to iteration
• An iterative solution involves loops
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-101
Recursive Solutions
• Facts about a recursive solution
– A recursive method calls itself
– Each recursive call solves an identical, but 
smaller, problem
– A test for the base case enables the recursive 
calls to stop
• Base case: a known case in a recursive definition
– Eventually, one of the smaller problems must be 
the base case
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-102
Recursive Solutions
• Four questions for constructing recursive 
solutions
– How can you define the problem in terms of a 
smaller problem of the same type?
– How does each recursive call diminish the size of 
the problem?
– What instance of the problem can serve as the 
base case?
– As the problem size diminishes, will you reach this 
base case?
18
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-103
A Recursive Valued Method: 
The Factorial of n
• Problem
– Compute the factorial of an integer n
• An iterative definition of factorial(n)
factorial(n) = n * (n-1) * (n-2) * … * 1 for any integer n > 0
factorial(0) = 1
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-104
A Recursive Valued Method: 
The Factorial of n
• A recursive definition of factorial(n)
factorial(n)  = 1 if n = 0
n * factorial(n-1) if n > 0 
• A recurrence relation
– A mathematical formula that generates the 
terms in a sequence from previous terms
– Example
factorial(n) = n * [(n-1) * (n-2) * … * 1]
= n * factorial(n-1)
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-105
A Recursive Valued Method: 
The Factorial of n
• Box trace
– A systematic way to trace the actions of a 
recursive method
– Each box roughly corresponds to an 
activation record
– An activation record
• Contains a method’s local environment at the 
time of and as a result of the call to the method
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-106
A Recursive Valued Method: 
The Factorial of n
• A method’s local 
environment includes:
– The method’s local 
variables
– A copy of the actual 
value arguments
– A return address in the 
calling routine
– The value of the method 
itself
Figure 2.3
A box
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-107
Function calls
• Function call
– save the “environment” -- PUSH operation
– execute the function
– restore the environment -- POP operation
– continue execution
• We need a stack for nested function 
calls
A B C
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-108
Factorial example
fact(n):
if n=1 return 1
return fact(n-1) * n
• The ‘environment’ here is just ‘n’
• Execute fact(3)
19
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-109
Factorial example
Execution
stack
fact(3):
if (n=1) return 1
return fact(2) * 3
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-110
Factorial example
Execution
stack
fact(n:=3):
if (n=1) return 1
return fact(n:=2) * n
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-111
Factorial example
Execution
stack
fact(n:=3):
if (n=1) return 1
return fact(n:=2) * n
function call
-save environment
on the stack
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-112
Factorial example
Execution
stack
fact(n:=3):
if (n=1) return 1
return fact(n:=2) * n
fact(n)
n=3
function call
-saved environment
on the stack
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-113
Factorial example
Execution
stack
fact(n:=3):
if (n=1) return 1
return fact(n:=2) * n
fact(n)
n=3
if (n=1) return 1
return fact(n:=1) * n
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-114
Factorial example
Execution
stack
fact(n:=3):
if (n=1) return 1
return fact(n:=2) * n
fact(n)
n=3
if (n=1) return 1
return fact(n:=1) * n
fact(n)
n=2
if (n=1) return 1
return fact(n:=0) * n
20
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-115
Factorial example
Execution
stack
fact(n:=3):
if (n=1) return 1
return fact(n:=2) * n
fact(n)
n=3
if (n=1) return 1
return    1       * n
fact(n)
n=2
Pop previous environment
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-116
Factorial example
Execution
stack
fact(n:=3):
if (n=1) return 1
return fact(n:=2) * n
fact(n)
n=3
if (n=1) return 1
return    1      * n
fact(n)
n=2
Current environment
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-117
Factorial example
Execution
stack
fact(n:=3):
if (n=1) return 1
return     2     * n
fact(n)
n=3
Pop previous environment
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-118
Factorial example
Execution
stack
fact(n:=3):
if (n=1) return 1
return     2     * n
fact(n)
n=3
Current environment
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-119
A Recursive void Method: 
Writing a String Backward
• Problem
– Given a string of characters, write it in 
reverse order
• Recursive solution
– Each recursive step of the solution 
diminishes by 1 the length of the string to 
be written backward
– Base case
• Write the empty string backward
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-120
A Recursive void Method: 
Writing a String Backward
Figure 2.6
A recursive solution
21
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-121
A Recursive void Method: 
Writing a String Backward
• Execution of writeBackward can be 
traced using the box trace
• Temporary System.out.println
statements can be used to debug a 
recursive method
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-122
Writing a String Backward
writeBackward( s ):
if (s is empty)
do nothing
else
write the last character of s
writeBackward(s minus its last character)
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-123
Multiplying Rabbits 
(The Fibonacci Sequence)
• “Facts” about rabbits
– Rabbits never die
– A rabbit reaches sexual maturity exactly two 
months after birth, that is, at the beginning of its 
third month of life
– Rabbits are always born in male-female pairs
• At the beginning of every month, each sexually mature 
male-female pair gives birth to exactly one male-female 
pair
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-124
Multiplying Rabbits 
(The Fibonacci Sequence)
• Problem
– How many pairs of rabbits are alive in 
month n?
• Recurrence relation
rabbit(n) = rabbit(n-1) + rabbit(n-2)
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-125
Multiplying Rabbits 
(The Fibonacci Sequence)
Figure 2.10
Recursive solution to the rabbit problem
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-126
Multiplying Rabbits 
(The Fibonacci Sequence)
• Base cases
– rabbit(2), rabbit(1)
• Recursive definition
rabbit(n) =      1 if n is 1 or 2
rabbit(n-1) + rabbit(n-2) if n > 2
• Fibonacci sequence
– The series of numbers rabbit(1), rabbit(2), 
rabbit(3), and so on
22
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-127
Searching an Array:
Finding the Largest Item in an Array
• A recursive solution
if (anArray has only one item) {
maxArray(anArray) is the item in anArray
}
else if (anArray has more than one item) {
maxArray(anArray) is the maximum of
maxArray(left half of anArray) and
maxArray(right half of anArray)
}  // end if
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-128
Finding the Largest Item in an 
Array
Figure 2.13
Recursive solution to the largest-item problem
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-129
Binary Search
• A high-level binary search
• Looking for a value ‘x’ in a sorted array
1 n
a
• x < a ? Continue on left half else right
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-130
Binary Search
• A high-level binary search
if (anArray is of size 1) {
Determine if anArray’s item is equal to value
}
else {
Find the midpoint of anArray
Determine which half of anArray contains value
if (value is in the first half of anArray) {
binarySearch (first half of anArray, value)
}
else {
binarySearch(second half of anArray, value)
} // end if
} // end if
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-131
Binary Search
• Implementation issues:
– How will you pass “half of anArray” to the 
recursive calls to binarySearch?
– How do you determine which half of the 
array contains the value?
– What should the base case(s) be?
– How will binarySearch indicate the 
result of the search?
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-132
Binary Search
• Searching a number in a list of length n
• How many steps ? (worst case)
• “Step” is “list item access”
• T(n) = ?
• T(1) = 1
23
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-133
Binary Search
• Searching a number in a list of length n
• How many steps ? (worst case)
• “Step” is “list item access”
• T(n) = 1 + T(n/2)
= 1 + 1 + T((n/2) /2)
= 2 + T(n/4)
= …… (repeat k times)
= k + T(n/2^k)
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-134
Binary Search
• T(1) = 1
• T(n) =  k + T(n/2^k)
• Stop when: n/2^k = 1
or k = log n
• T(n) = O( log n )
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-135
The Towers of Hanoi
Figure 2.19a and b
a) The initial state; b) move n - 1 disks from A to C
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-136
The Towers of Hanoi
Figure 2.19c and d
c) move one disk from A to B; d) move n - 1 disks from C to B
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-137
The Towers of Hanoi
• Pseudocode solution
solveTowers(count, source, destination, spare)
if (count is 1) {
Move a disk directly from source to destination
}
else {
solveTowers(count-1, source, spare, destination)
solveTowers(1, source, destination, spare)
solveTowers(count-1, spare, destination, source)
} //end if
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-138
Recursion and Efficiency
• Some recursive solutions are so 
inefficient that they should not be used
• Factors that contribute to the 
inefficiency of some recursive solutions
– Overhead associated with method calls
– Inherent inefficiency of some recursive 
algorithms
24
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-139
Summary
• Data abstraction: a technique for controlling 
the interaction between a program and its 
data structures
• An ADT: the specifications of a set of data 
management operations and the data values 
upon which they operate
• The formal mathematical study of ADTs uses 
systems of axioms to specify the behavior of 
ADT operations
• Only after you have fully defined an ADT 
should you think about how to implement it
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-140
Summary
• A client should only be able to access the 
data structure by using the ADT operations
• An object encapsulates both data and 
operations on that data
– In Java, objects are instances of a class, which is 
a programmer-defined data type
• A Java class contains at least one 
constructor, which is an initialization method
• Typically, you should make the data fields of 
a class private and provide public methods to 
access some or all of the data fields
COMP2160 © The University of Sydney
Material adapted from © 2004 Pearson Addison-Wesley. All rights reserved 1-141
Done
• This lecture: lists, recursion
• Next week: stacks and queues
• Next week tutorial: implementation 
issues for stacks and queues
• Textbook: p113-170 (recursion)
p170-250 (lists)