Transcript Chap12

Chapter 12
Data Structures
and Collections
Knowledge Goals
• Understand the difference between array and
linked implementations of a list
• Know how to a stack works
• Know how a queue works
• Know how a binary tree works
• Know how a hash table works
• Understand the concepts behind the java
collections framework
2
Skill Goals
• Develop a linked data structure
• Use the ArrayList and LinkedList
classes
• Use the HashSet and TreeSet classes
• Use the Stack class
• Use the LinkedList class to implement a
queue
• Choose when to use an array-based versus a
linked implementation of a data structure
3
Linked Structures
Arraybased
list is
fixed
size
4
Linked Structures
Arraybased is
physically
ordered;
linked is
logically
ordered,
which
means …
5
Linked Structures
Insertions
and
deletions
are
easier
6
Linked Structure
Linked list
A list in which the order of the components is
determined by an explicit link field in each node,
rather than by the sequential order of the
components in memory
External reference (pointer)
A named variable that references (points to) the
first node (head) of a linked list
7
Yes, but how does it work?
Linked Structure
List
External pointer
A node
Each node contains
item and a link
8
Linked Structures
class Node
{
null is a keyword
meaning points to
nothing
Node link = null;
String item;
Node()
{ item = ""; }
default
constructor
Node(String data)
{ item = data; }
}
9
parameterized
constructor
Linked Structures
Let's create a linked list with three nodes, containing
"Adams", "Baker", and "Carter"
We begin by creating two variables
Node current;
// Pointer used to keep track
// of where we
are in the list
Node list;
Result
10
// External point to the list
Linked Structures
list = new Node("Adams");
current = list;
Result
11
Linked Structures
current.link = new Node("Baker");
Result
12
Linked Structures
current = current.link;
Result
13
Linked Structures
current.link = new Node("Carter");
current = current.link;
Result
14
Linked Structures
Traversal
Visiting every node in a data structure following
an organized pattern of access
current = list;
while (current.link != null)
{
System.out.println(current.item);
current = current.link;
}
15
What is the pattern of access?
Linked Structures
Which of these
will change
with the
linked
version?
16
Linked Structures
Does the CRC card
for a class change
with the
implementation?
17
Linked Structures
Observer operations
public boolean isEmtpy()
{ return list == null; }
public boolean contains(String item)
{
Node current = list;
while (current != null &&
curent.item.compareTo(item) != 0)
curent = current.link;
return current != null
}
18
Linked Structures
if (list.contains("Doggett"))…
Search
when
item
is not
in the
list
19
Linked Structures
Size in an array-based list just returns numItems;
What about in a linked-implementation?
– Can keep a counter
increment with each insertion
decrement with each deletion
– Can count the number of items each time
Which is best (better)?
20
Linked Structures
public int size()
{
Node current = list;
int numItems = 0;
while (current != null)
{
numItems++;
current = current.link;
}
return numItems;
}
21
Is this an
example
of a
traversal?
Linked Structures
Mutators
Add
– Insert where? To match array-based traversal, new
item must go at the end
– How to find end? Search or keep a pointer
– Special case(s)? Empty list
tail
22
Linked Structure
public void add(String newItem)
{
Node item = new Node(newItem);
if (list == null)
{
list = item;
tail = item;
}
else
{
tail.link = item;
tail = tail.link;
}
}
23
Empty list
Set list and tail
to item
Not empty list
Set item as last node
Set tail to last node
Linked Structures
Remove
– Item not there? Do nothing
– What if item is the first? Reset external pointer
– What if item is the last? Reset tail pointer
– What if item is anywhere else? General case
24
Linked Structures
Can't be reached;
System recaptures it
25
Linked Structures
Remove "Adams"
What is prior?
26
Linked Structures
Remove "Carter"
27
Linked Structures
Remove "Adams" (only node)
28
public void remove(String item)
{
Node current = list;
Node prior = null;
while (current != null &&
current.item.compareTo(item) != 0)
{
prior = current;
current = current.link;
}
if (current != null)
{
if (current == tail)
tail = prior;
if (prior == null)
list = list.link;
else
prior.link = current.link;
}
}
29
Search for item
item in last node
item in first node
item in interior node
Linked Structures
Iterator "trio"
public void resetList()
{ current = list; }
public boolean hasNext()
{ return current != null; }
public String next()
{
String item = current.item;
current = current.link;
return item;
}
30
What
assumptions
must be in
documentation?
Other Data Structures
What do these
objects have
in common?
31
Other Data Structures
Stack
A data structure in which insertions and
deletions can be made from only one end
LIFO
Last In First Out
Can you name some additional LIFO structures
in every day life?
32
Other Data Structures
First
item
called
"top"
33
Other Data Structures
What properties does this illustration exhibit?
34
Other Data Structures
Queue
A data structure in which insertions are
made at one end and deletions are made at
the other end
FIFO
First In First Out
Can you name some additional FIFO
structures in every day life?
35
Other Data Structures
36
Other Data Structures
37
Other Data Structures
Jake's Pizza Shop
Owner
Jake
Manager
Brad
Waitress
Joyce
Chef
Carol
Waiter
Chris
Cook
Max
Helper
Len
What properties does this illustration exhibit?
38
Other Data Structures
ROOT NODE
Owner
Jake
Manager
Brad
Waitress
Joyce
39
Chef
Carol
Waiter
Chris
Cook
Max
Helper
Len
Other Data Structures
Owner
Jake
Manager
Brad
Waitress
Joyce
LEAF NODES
40
Chef
Carol
Waiter
Chris
Cook
Max
Helper
Len
Other Data Structures
Owner
Jake
Manager
Brad
Waitress
Joyce
Chef
Carol
Waiter
Chris
LEFT SUBTREE OF ROOT NODE
41
Cook
Max
Helper
Len
Other Data Structures
Owner
Jake
Manager
Brad
Waitress
Joyce
42
Chef
Carol
Waiter
Chris
Cook
Max
Helper
Len
RIGHT SUBTREE
OF ROOT NODE
Other Data Structures
Binary tree
A data structure, each of whose nodes refer to
left and right child nodes
43
Other Data Structures
Binary search tree
A binary tree in which the
value in any node is
greater than the value in
the left child and any of
its children and less than
the value in its right child
and any of its children
44
Other Data Structures
Binary search trees provide rapid searches
Search
for
50
45
Other Data Structures
Search
for
18
Where
would
18 be
if there?
46
Other Data Structures
Traversals
Inorder(tree)
if tree is not NULL
Inorder(Left(tree))
Visit Info(tree)
Inorder(Right(tree))
PostOrder(tree)
if tree is not NULL
Postorder(Left(tree))
Postorder(Right(tree))
Visit Info(tree)
47
PreOrder(tree)
if tree is not NULL
Visit Info(tree)
Preorder(Left(tree))
Preorder(Right(tree))
Other Data Structures
48
Other Data Structures
Graph
A data
structure in
which the
nodes can
be arranged
in any
pattern
49
Other Data Structures
Hashing
A technique to
perform insertions
and access to an
item in constant
time by using the
value to identify
its location in the
structure
50
Other Data Structures
values
[0]
Empty
[1]
4501
[2]
Empty
[3]
8903
7803
[4]
.
.
.
Empty
index = partNum % 100
.8
.
10
.
[ 97]
Empty
[ 98]
2298
[ 99]
3699
51
HandyParts company
makes no more than 100
different parts, but the
parts all have four digit numbers
Hash function
A function used to manipulate the
value to produce an index that
identifies its location
Other Data Structures
values
[0]
Empty
[1]
4501
[2]
Empty
[3]
8903
7803
[4]
.
.
.
Hash(key) = partNum % 100
to place the element with
Empty
.8
.
10
.
[ 97]
Empty
[ 98]
2298
[ 99]
3699
52
Use the hash function
part number 5502 in the
array
Other Data Structures
values
[0]
Empty
[1]
4501
[2]
5502
[3]
[4]
.
.
.
6702 % 100 = 2
7803
Empty
.
.
.
[ 97]
Empty
[ 98]
2298
[ 99]
3699
53
Next place part number
6702 in the array
But values[2] is already
occupied, causing a
collision
Other Data Structures
values
[0]
Empty
[1]
4501
[2]
5502
[3]
[4]
.
.
.
7803
Empty
.
.
.
[ 97]
Empty
[ 98]
2298
[ 99]
3699
54
One solution
Repeatedly increment index
until an empty location
is found for part number 6702
Hashing
values
[0]
Empty
[1]
4501
[2]
5502
[3]
[4]
.
.
.
7803
Empty
.
.
.
[ 97]
Empty
[ 98]
2298
[ 99]
55
3699
Part 6702 can be placed at
the location with index 4
Hashing
values
[0]
Empty
[1]
4501
[2]
5502
[3]
7803
[4]
6702
.
.
.
[ 97]
[ 98]
[ 99]
56
.
.
.
Empty
2298
3699
Part 6702 is placed at
the location with index 4
Where would the part with
number 4598 be placed using
this scheme?
Other Data Structures
Handling collisions with chaining
57
Other Data Structures
Comparison of incrementing index and chaining
58
Generic Types in Java
Generic types
A type for which the operations are defined
but the type of the objects being manipulated
is not
How have we handled generics previously?
59
Generic Types in Java
class Node <ItemType extends
Comparable<ItemType>>
{
Node<ItemType> link = null;
ItemType item;
Node() { }
Node(ItemType newItem)
{ item = newItem; }
}
60
Node<ItemType> list;
Node<ItemType> tail;
In client code
Java Collections Framework
Interface
Hierarchy
Classes that
implement
Collection
are data
structures that
hold items in an
organized
manner
Set is Java's list with no duplicates
61
Java Collections Framework
Rest of Interface hierarchy
Classes that implement
Map hold values in
association with objects
called keys
62
Java Collections Framework
63
Let's look at this another way
Interfaces
Collection
List
Set
SortedSet
Abstract Classes
AbstractList
AbstractCollection
AbstractSet
implements
AbstractSequentialList
extends
64
Abstract
SequentialList
LinkedList
AbstractList
ArrayList
Observers in
AbstractCollection
contains
containsAll
isEmpty
toArray
toString
size
65
Vector
Stack
AbstractSet
HashSet
TreeSet
Linked
HashSet
Concrete Classes
Java Collections Framework
AbstractCollections implements the
Iterable Interface that has one method
iterator that returns an Iterator object
Iterator myIter = myList.iterator();
while (myIter.hasNext())
System.out.println(myIter.next());
66
Java Collections Framework
Collections class contains static helper methods
for use with the classes in the collection
void sort(List)
int binarySearch(List, key)
void reverse(List)
void shuffle(List)
void copy(DestinationList, SourceList)
Object min(Collection)
Object max(Collection)
boolean replaceAll(List, OldValueObject,
NewValueObject)
boolean disjoint(Collection, Collection)
67
Java Collections Framework
ArrayList is a concrete list class using an
array-based implementation with the usual list
operations and some array-specific methods as
well such as:
add(index, item)
position
set(index, item)
position;
Inserts the item at the index
Replaces the item at the index
returns replaced object
Removes the item at the index
remove(index)
position
trimToSize()
ensureCapacity(limit)
68
has
Trim array to list size
Makes sure the underlying array
Java Collections Framework
LinkedList is a concrete list class with a
linked implementation with the usual list
operations and some additional ones such as:
add(index, item)
getFirst()
getLast()
poll()
element
removeLast()
remove(index)
index
69
Inserts item at the index position
Returns a reference to the first item
Returns a reference to the last item
Deletes and returns the first
Deletes and returns last element
Deletes and returns the item in the
position
Java Collections Framework
ArrayList and LinkedList also have
methods that take collections as arguments
removeAll(collection)
retainAll(collection)
addAll(collection)
Removes all items from list
that match items in collection
Removes all items that do not
match items in the collection
Adds all the items in the collection
to the end of the list
Do these operations add any new functionality?
70
Java Collections Framework
Sets (a lists without duplicates) is implemented
in two concrete classes: HashSet and
TreeSet
– Names give the underlying data structure
– Both implement all the regular list
operations
– TreeSet is able to return subtrees
(collections) with values less than or
greater than a parameter
71
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;
while (inFile.hasNextLine())
{
line = inFile.nextLine();
list.add(line);
}
Iterator iterator = list.iterator();
while (iterator.hasNext())
System.out.println(iterator.next());
72
What will the output look like?
Java Collections Framework
File:
red
blue
yellow
brown
black
pink
green
orange
white
violet
crimson
rose
73
Output:
red
blue
yellow
brown
black
pink
green
orange
white
violet
crimson
rose
Output
from
ArrayList
implementation
Java Collections Framework
HashSet list = new HashSet();
File:
red
blue
yellow
brown
black
pink
green
orange
white
violet
crimson
rose
74
Output:
green
rose
red
white
orange
crimson
pink
brown
blue
yellow
violet
black
Output from
HashSet
implementation
Java Collections Framework
TreeSet list = new TreeSet();
File:
red
blue
yellow
brown
black
pink
green
orange
white
violet
crimson
rose
75
Output:
black
blue
brown
crimson
green
orange
pink
red
rose
violet
white
yellow
Output from
TreeSet
implementation
Extras
I designed
one of the
best known
sorting
algorithms
and was
knighted
recently
Who am I
76
Extras - GUI Track
Handling events with radio buttons requires






77
declaring and instantiating a ButtonGroup
object
declaring and instantiating each radio button
registering an ActionListener with each
radio button
adding each button to ButtonGroup object
adding each button to panel
parameter to getActionCommand tells which
button was pressed
Extras - GUI Track
Window
with
three
radio
buttons
and a
label
78