Transcript Chap11

Chapter 11
Array-Based Lists
Knowledge Goals
• Understand the list abstraction and basic list
operations
• Recognize the difference between an array and a
list
• Understand how to use an array to represent a
list
• Know how to use a key to establish the order of a
sorted list
• Understand the principle of "divide and conquer"
as expressed in the binary search algorithm
2
Skill Goals
•
•
•
•
Add an item to a list
Remove an item from a list
Search for an item in a list
Sort the items in a list into ascending or
descending order
• Build a list in sorted order
• Search for an item in a sorted list using a
linear search
3
Skill Goals
• Search for an item using a binary search
• Define a class that extends a Java
interface
• Use Java's Comparable interface
• Use ArrayList from the Java library
4
What is a List?
List
A homogeneous collection of elements, with a
linear relationship between the elements
Linear relationship
Every element (except the first) has a unique
predecessor, and every element (except the last)
has a unique successor
Length (size in Java)
The number of items in a list; it can vary over time
5
What is a List?
Sorted list: The predecessor and successor relationships are determined by the content of the keys
6
What is a List?
We are concerned only with unique keys
7
A List Class
Can you name some of the operations that must
be applied to a List?
8
A List Class
9
A List Class
Transformers
 add
 remove
change state
Observers





isEmpty
isFull
size
contains
hasNext
observe state
Iterators
10
 resetList
 next
process components
A List Class
Attributes
numItems
number of
elements in list
listItems[0]
. . .
listItems[listItems.length-1]
array of list
elements
currentPos
used by iterator
11
A List Class
12
A List Class
Class ListOfStrings is unsorted
UNSORTED LIST
Elements are placed
into the list in
no particular order
with respect to their
content
13
SORTED LIST
List elements are in
an order that is
sorted by the content
of their keys -- either
numerically or
alphabetically
A List Class
public ListOfStrings()
{
numItems = 0;
listItems = new String[100];
currentPos = 0;
}
constructors
public ListOfStrings(int maxItems)
{
numItems = 0;
listItems = new String[maxItems];
currentPos = 0;
}
14
A List Class
public boolean isEmpty()
{
return (numItems == 0)
}
public int size()
{
return numItems;
}
public boolean isFull()
{
return (numItems == listItems.length);
}
15
observers
A List Class
public boolean contains(String item)
{
int index = 0;
while (index < numItems &&
listItems[index].compareTo(item) != 0)
index++;
return (index < numItems);
}
See why this works?
16
Add: Does it matter where we put the item?
numItems
listItems [ 0 ]
15
[1]
39
[2]
-90
[3]
.
[ listItems.length-1 ]
17
3
Place the item
in numItems
location and
increment
numItems
.
.
item
63
After Inserting 64 into an Unsorted List
numItems
listItems [ 0 ]
15
[1]
39
[2]
-90
[3]
64
.
[ listItems.length-1 ]
18
4
.
.
item
64
A List Class
public void add(String item)
// Result: If the list is not full, puts item as
// the last position in the list; otherwise list
// is unchanged
{
if (!isFull())
{
listItems[numItems] = item;
numItems++;
}
}
19
A List class
Remove is more difficult
remove(item)
Search (item, found, index)
if (found)
Shift remainder of list up
Decrement numItems
ShiftUp
for count going from index downTo numItems
Set listItems[count] to listItems[count+1]
20
Can you walk through deleting 39?
numItems
4
listItems
[0]
15
[1]
39
[2]
-90
[3]
.
.
64
.
[ listItems.length-1 ]
21
The List Class
22
public void remove(String item)
{
int index = 0;
boolean found = false;
while (index < numItems && !found)
{
if (listItems[index].compareTo(item) == 0)
found = true;
else
index++;
}
if (found)
{
for (int count = index; count < numItems - 1;
count++)
listItems[count] = listItems[count + 1];
numItems--;
}
}
A List Class
public void resetList() { currentPos = 0; }
public boolean hasNext() { return (currentPos !=
numItems); }
public String next()
// Returns the item at the currentPos position
// Assumptions: No transformers are called during the
// iteration
{
String next = listItems[currentPos];
currentPos++;
return next;
}
23
Read
documentation
carefully!
A List Class
How are
CRC cards
and UML
diagrams
alike?
How are
they
different?
24
A List Class
A class is not complete until
it has been tested!
Command-driven test driver
A driver program that reads in commands and
executes them; an excellent vehicle for unit
testing a class
enum Operations {ADD, REMOVE, SIZE,
ISEMPTY, ISFULL, CONTAINS, PRINT, QUIT}
25
A List Class
Main
Read file into list
Set operation to inOperation()
Set keepGoing to true
while (keepGoing)
Execute operation
Set operation to inOperation
Write list to file
26
A
commanddriven
testing
program
A List Class
executeOperation
switch(operation)
case ADD:
// execute add
case REMOVE: // execute remove
case SIZE:
// execute size
case ISEMPTY: // execute isEmpty
case ISFULL: // execute isFull
case CONAINS: // execute contains
case PRINT:
// print list
case QUIT:
// quit
27
How are
resetList,
hasNext,
and next
tested
?
ListWithSort
Sorting
Arranging the components of a list into order
28
ListWithSort
Straight selection sort
 Examine the entire list to select the smallest element
 Swap that element with first element (with array index 0)
 Examine the remaining list to select the smallest
element from it
 Swap that element with second element (array index 1)
 Continue process until only 2 items remain
 Examine the last 2 remaining list elements to select the
smallest one
 Swap that element with the other
29
ListWithSort
30
ListWithSort
Can
you use
the same
test
driver
?
31
A Sorted List
Is ListWithSort the same as a SortedList?
Are the same operations needed for a List and a
SortedList? Any extra ones needed?
From the client's (user's) point of view, what is
the visible difference between an unsorted list
and a sorted list?
32
33
A Sorted List
34
A Sorted List
Add
35
A Sorted List
public void add(String item)
{
if (! isFull())
{//
find proper location for new element
int index = numItems - 1;
while (index >= 0
&&
item.compareTo(listItems[index]) < 0)
{
listItems[index + 1] = listItems[index];
index--;
}
listItems[index +1] = item; // insert item
numItems++; }
}
36
A Sorted List
remove
and
next
must
maintain
order
but they
already
do!
37
Searching
Linear (sequential) search
Search begins at the beginning of the list and
continues until the item is found or the entire
list has been searched
Can searching be improved if the items are in
sorted order?
38
Searching
3
34
7
99
66
11
[0]
[1]
[2]
[3]
[4]
[5]
How many comparisons are needed to find 11? 67? 2? 100?
3
[0]
7
[1]
11
[2]
34
[3]
66
[4]
99
[5]
How many comparisons are needed to find 11? 67? 2? 100?
That's better, but we can do better yet
39
Searching
Binary search (list must be sorted)
Search begins at the middle and finds the item
or eliminates half of the unexamined items;
process is repeated on the half where the item
might be
Say that again…
40
Searching
41
Searching
Boolean Binary Search (first, last)
If (first > last)
return false
Else
Set middle to (first + last)/2
Set result to item.compareTo(list[middle])
If (result is equal to 0)
return true
Else
If (result < 0)
Binary Search (first, middle - 1)
Else
Binary Search (middle + 1, last)
42
Searching
Searching for "bat"
43
Searching
44
Searching
public boolean isThere(String item)
// Assumption: List items are in ascending order
// Returns true if item is in the list; false otherwise
{ int first = 0; int last = numItems - 1;
int middle; boolean found = false;
while (last >= first && !found)
{
middle = (first + last) / 2;
if (item.compareTo(listItems[middle]) == 0)
found = true;
// Item has been found
else
if (item.compareTo(listItems[middle] < 0)
last = middle - 1;
// Look in first half
else first = middle + 1;
// Look in second half
}
return found;
}
45
Searching
Average Number of iterations
Length
Sequential
Binary
10
5.5
2.9
100
50.5
5.8
1,000
500.5
9.0
10,000
5000.5
12.0
Is a binary search
always better?
46
Refactoring the List Hierarchy
Refactoring
Modifying code to improve its quality without
changing is functionality
There
is
a
better
way!
47
Refactoring the List Hierarchy
public abstract class AbstractList
{
public
public
public
public
public
public
public
public
public
public
public
AbstractList()
AbstractList(int maxItems)
boolean isFull()
boolean isEmpty()
int size()
void resetList()
boolean hasNext()
String next()
boolean contains(String item)
abstract void remove(String item)
abstract void add(String item)
}
What about contains?
48
Refactoring the List Hierarchy
49
List of Comparable Objects
Wouldn't it be nice if we could have one
abstract class for any data type, not one for
each type of item that could be on the list?
You can if you declare the type of the items to
be Comparable
protected Comparable[] listItems
50
List of Comparable Objects
public abstract class AbstractList
{
public
public
public
public
public
public
public
public
public
public
public
}
51
AbstractList()
AbstractList(int maxItems)
boolean isFull()
boolean isEmpty()
int size()
void resetList()
boolean hasNext()
String next()
boolean contains(Comparable item)
abstract void remove(Comparable item)
abstract void add(Comparable item)
List of Comparable Objects
public AbstractList()
{
numItems = 0;
listItems = new Comparable[100];
currentPos = 0;
}
public void add(Comparable item)
{
if (!isFull())
{
listItems[numItems] = (String) item;
numItems++;
}
}
52
Abstract class
Derived class
Preview of Java Collections
Java Collections
A collection of interfaces, abstract classes,
and classes available in java.util that
describe data structures available for you to
use
Why do you think we covered array-based lists
before mentioning the Java Collections?
53
Preview of Java Collections
ArrayList<type>(int
number)
Returns an array with an initial capacity of
number elements.
add(Object anObject)
anObject is appended to the end of the list
size()
Returns the number of elements
remove(Oject
anObject)
isEmpty
Removes an instance of anObject if it is there
contains(Object,
anObject)
Returns true if anObject is in the list
iterator()
Returns an Iterator over the elements of
the list
54
Returns true of the list contains no elements
Plus lots more that are different
Preview of Java Collections
import java.util.*;
import java.io.*;
public class ListDriver
{
private static Scanner inFile;
private static PrintWriter outFile;
public static void main(String[] args) throws
IOException
{
inFile = new Scanner(new FileReader("list.dat"));
outFile = new PrintWriter(new
FileWriter("list.out"));
ArrayList list = new ArrayList(4);
String line;
55
different
Preview of Java Collections
while (inFile.hasNextLine())
{
line = inFile.nextLine();
list.add(line);
}
// Declare and instantiate iterator
Iterator iterator = list.iterator();
while (iterator.hasNext())
System.out.println(iterator.next());
inFile.close();
outFile.close();
}
}
56
different
look
closely
Extras - GUI Track
57
Extras - GUI Track
Handling events from multiple sources with
panels requires
 declaring and instantiating a JPanel object
 setting the layout manager for the panel
 doing everything necessary to create a
button
 adding the button to the panel
 declaring and instantiating multiple objects
of the class with the panel
58
Extras - GUI Track
Three
instances
of class
containing
panel
59
Extras - GUI Track
Handling events from multiple sources with the
same listener requires
 doing everything necessary to create
multiple buttons
 handler gets a button's name from
actionPerformed parameter
 handler uses if statement to determine
which button was pressed
60
Extras - GUI Track
Window
with
three
buttons
and one
listener
61