Transcript Lists

Lists
Chapter 4
Chapter Contents

Specifications for the ADT List

Redefining the Specifications

Using the ADT List

Using a List Is Like Using a Vending Machine
2
Specifications for the ADT List

A list provides a way to organize data
A to-do list, address list,
grocery list etc…
ADT list must be considered in
general, not necessarily a list of
strings. It can contain any type of
objects.
3
Specifications for the ADT List

Operations on lists









Add new entry – at end, or anywhere
Remove an item
Remove all items
Replace an entry
Look at any entry
Look for an entry of a specific value
Count how many entries
Check if list is empty, full
Display all the entries
4
Specifications for the ADT List

To specify an ADT list

Describe its data( A collection of objects in a specific order
and having the same data type, the number of objects in the
collection.)



Specify the operations
ADT does not indicate how to store the data
or how to implement the operations.
In contrast, a data structure is an
implementation of an ADT within a
programming language.
5
Example
The effect of ADT list operations on an initially empty list.
Convenient way of identify a particular entry is by the
entry’s position within the list. Position-oriented ADT
6
Potential Problem Operations

add, remove, replace, getEntry
work OK when valid position given



remove, replace and getEntry not
meaningful on empty lists
A list could become full, what happens to
add?
What else operations may cause
problems?
7
Possible Solutions





Assume the invalid situations will not occur.
 State a precondition, up to the client to check
Ignore the invalid situations
 Nothing will be done. Client is left with no knowledge.
Make reasonable assumptions, guess at the client’s intention. act in
predictable way
 E.g. If a client wants to remove the 6th entry for a list with only three
entries. Remove the third entry.
Return a signal or Boolean value indicating success or failure of the
operation
 E.g. return null if getEntry method gives an nonexistent position
Throw an exception

Simply report a problem without deciding what to do. The exception allow each client to do
what is needed in its own particular situation. The method invocation in the client must appear
within a try block.
The documentation for ADT should describe
these possible solutions.
8
Redefining Specifications

A first draft of an ADT specifications may
ignore potential problems


Concentrate on details after major portions of
specifications written


Simplifies the first draft
Makes the specifications complete
After writing specifications,


Write Java interface for its operations
Java interface can be used for class to implement
the ADT
9
Generic Types Within an Interface
and Class
public interface Pairable<S>
{
public void setPairs(S firstItem, S secondItem)
}
A class that implements this interface could begin with the statement
public class OrderedPair<T> implements Pairable<T>
A class to represent pair of objects of the same type. Since each pair can be of any class type,
we used a generic type in the definition of the class.
The method setPair has parameters of a generic type. Imagine an interface Pairable that
declares this method.
10
ListInterface
/** An interface for the ADT list.
* Entries in the list have positions that begin with 1.*/
public interface ListInterface<T>
{
/** Task: Adds a new entry at a specified position within the list. The list’s size is
* increased by 1.
* @param newPosition an integer that specifies the desired position of the new entry
* @param newEntry the object to be added as a new entry.
* @return true if the addition is successful, or false if either the list is full, newPosition <1, or
newPosition > getLength() +1 */
public boolean add( int newPosition, T newEntry);
How to write the comments for method remove?
public T remove( int givenPosition);
}
11
Using the ADT List
A list of numbers that identify runners in the order
in which they finish a race
12
Using the ADT List
public class ListClient
{
public static void main(String[] args) {
testList(); } // end main
public static void testList() {
ListInterface<String> runnerList = new AList<String>();
// has only methods
// in ListInterface
runnerList.add("16");
// winner
runnerList.add(" 4");
// second place
runnerList.add("33");
// third place
runnerList.add("27");
// fourth place
runnerList.display();
AList implements interface
} // end testList
ListInterface.
} // end ListClient
The data type of runnerList is ListInterface<String>. This declaration
obliges runnerList to call only methods in the interface. If the data type
13
was Alist<String>, what methods are available to runnerList?
Question?
1. What changes to testList are necessary to
represent the runner’s numbers as Integer
objects instead of strings?
2. Write Java statements that exchange the third
and seventh entries in a list of 10 string
objects by only using remove and add
methods.
We name the list to be Mylist.
14
Java Class Library: The Interface List


The standard package java.util contains a list
interface – called List
Methods provided
public boolean add(Object newEntry)
public void add(int index, Object newEntry)
public Object remove(int index)
public void clear()
public Object set(int index, Object anEntry) // like replace
public Object get(int index) // like getEntry
public boolean contains(Object anEntry)
public int size() // like getLength
public boolean isEmpty()
15
A List Interface is Like a Vending
Machine
A vending machine.
16
A List Interface is Like a Vending
Machine
Observations about vending machines
 Can perform only tasks shown on interface
 Must understand the tasks
 Cannot see inside the machine
 Can use the machine even though don’t know
what happens inside
 If inside of machine replaced with new
improved version


Interface remains unchanged
Customer uses machine in same way as before
17
A List Interface is Like a Vending
Machine
Observations about clients and List ADT
 Client can perform only operations from the ADT List
 Client must adhere to specifications
 Client cannot access data without an ADT
operation. Encapsulation hides the data
representation within the ADT
 Client can use the list – even though unable to
access entries directly. Don’t need to know how the
data is stored.
 If implementation is changed, client still uses list in
same way as before
18
Exercise



Suppose that you have a list that is created by the following
statement:
ListInterface<Double> quizScores = new AList<Double>();
Imagine that someone has added to this list the quiz scores
received by a student throughout a course. The professor would
like to know the average of these quiz scores, ignoring the lowest
score.
a. Write Java statements at the client level that will find and
remove the lowest score in the list.
b. Write Java statements at the client level that will compute the
average of the scores remaining in the list.
19