Transcript Lists

Java the UML Way
http://www.tisip.no/JavaTheUMLWay/
Data Structures and Algorithms
Graphs
Lists
Java API: Collection, List and LinkedList
Queue
Stack
Recursion
Trees incl. binary search trees
Java API: Map and TreeMap
Hash tables
versjon 2002-04-17
page 2
page 3-6
page 7-9
page 10
page 11
page 12
page 13-17
page 18-20
page 21-25
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17
Graphs
• Applications
– visualizations of computer networks
– logistics
– formal mapping of an object oriented program system
2
vertex
4
edge
2
12
9
5
An undirected graph
A directed and weighted graph
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 2
Lists
•
•
Data is ordered sequentially in the same way as an array
Relevant operations for a list
– Insert element into list: first, last or in given position.
– Remove element from list.
– Go through all elements of list.
•
Lists compared to arrays
– Both data structures fix the data in a particular order.
– The size of a list is dynamic, it is changed by inserting or removing an element. An
array can’t change its size after creation.
– Finding a given element in a list can be time consuming because we always must
start at the end of the list. Any element in an array may be accessed with the index.
Single-linked list
Double-linked list
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 3
Some List Operations in More Detail
• Inserting element at the end
• Inserting element in given position (before *)
*
Why can’t we do the two operations in
reverse order?
*
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 4
Example, a List of
Names
NameElement
next
name
getName
getNext
setName
setNext
next
Joe
next
Aron
neste
next
Liza
next
Anne
null
class NameElement {
private NameElement next;
private String name;
public NameElement(String initName) {
name = initName;
next = null;
}
public NameElement(String initName, NameElement
initNext) {
name = initName;
next = initNext;
}
public String getName() {
return name;
}
public NameElement getNext() {
return next;
}
public void setName(String newName) {
name = newName;
}
public void setNext(NameElement newNext) {
next = newNext;
}
}
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 5
The NameList Class
NameList
firstElement
toString
insertNameAtEnd
findName
deleteName
(toString())
Show program listing 17.2 and 17.3, page 530 and so on.
Solve problems page 534.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 6
Interface java.util.Collection
•
Common features for classes implementing this interface:
– a collection of elements of different types
– methods (remember we have no implementations so far!)
•
•
•
•
•
•
•
public boolean add(Object add)
public boolean contains(Object obj)
public boolean containsAll(Collection otherCollection)
public boolean remove(Object obj)
public boolean removeAll(Collection collection)
public int size()
Collections can be classified by two parameters
– is duplicates allowed?
– are the elements ordered?
Ordered
Duplicates allowed
Duplicates not allowed
List
Not ordered
Multiset
Hashtable
(the table itself, in
many cases)
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Set
Chapter 17, page 7
Interface java.util.List
• List is a sub-interface to Collections:
– The elements must be ordered
• List requires more methods implemented:
–
–
–
–
public void add(int position, Object obj)
public Object set(int position, Object obj)
public Object remove(int position)
public Object get(int position)
• Familiar? The class ArrayList implements this interface.
• May well have identical data in a list, even several references to the
same object (like ArrayList may).
• The implementation of add() decides such things, not dictated by the
interface.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 8
The Class java.util.LinkedList
• Implements List (and hence Collection)
• Will have the performance characteristics expected from a doubly
linked list
• Offers more methods than the interface demands
–
–
–
–
public void addFirst()
public void addLast()
public Object removeFirst()
public Object removeLast()
Solve the problem at page 538.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 9
Queue
• A queue is an ordered collection of data where data is inserted and
removed in one particular place.
• FIFO queue
– First In First Out
• Operations
– insert element
– remove element
import java.util.*;
class FIFOQueue {
private LinkedList list = new LinkedList();
public void insertElement(Object anObject) {
list.addLast(anObject);
}
public Object removeElement() {
return list.removeFirst();
}
public int findNumberOfElements() {
return list.size();
}
}
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 10
Stack
• A stack is a LIFO queue (Last In First Out)
import java.util.*;
class Stack {
private LinkedList list = new LinkedList();
public void insertElement(Object anObject) {
list.addLast(anObject);
}
public Object removeElement() {
return list.removeLast();
}
public int findNumberOfElements() {
return list.size();
}
}
Solve the problem at page 540.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 11
Recursion
• Technically, recursion is when a method calls itself.
• For this not to go on forever, recursion must have a stop condition.
• Example:
public int factorial(int n) {
if (n <= 1) return 1;
else return n * factorial(n-1);
}
Solve the problems at page 541.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 12
Trees
•
A tree is a special case of graph
–
–
–
–
–
–
may not contain cycles
must be connected
always exactly one path between two vertices
one vertex is defined as root
the tree spreads out from the root
any vertex will suffice as root, if thus defined
tree
not a tree
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 13
The Vertices of a Tree
root
parent vertices
leaf
child vertices
leaf
leaf
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 14
Binary Search Trees
• A tree where each parent has at most two
children is called a binary tree.
• The children are the roots of right and left
subtree.
• For each vertex there is data.
– the left child’s data is ”smaller than or
equal to” the parent’s data
– the right child’s data is ”larger than” the
parent’s data
15
10
3
28
14
20
BinarySearchTree
16
root
toString
insertValue
searchForValue
21
left subtree
Show program listing 17.4, pp. 54-545.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 15
The SubTree Class
SubTree
rightTree
leftTree
parent
value
Show program listing 17.5, p.. 546-548.
toString
insertValue
searchForValue
Show program listing 17.6, page 549.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 16
Binary Search Trees Compared to Linked Lists
• Searching for data is much faster in a search tree compared to a linked
list.
– The search time in a linked list is at worst proportional to the number of
elements (= n) in the list.
– To search through a binary search tree requires to descend through the tree
until we find the right object, potentially much faster.
– The tree is balanced if it’s as symmetrical as possible.
– The search is most efficient if the tree is balanced.
– We can show that the search time in a balanced tree is at worst
proportional to log(n).
– log(n) is always smaller than n.
• Inserting data takes longer time in a binary search tree than in a list.
Solve the problem, page 549.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 17
Interface java.util.Map
• A map maintains a connection between keys and data.
– All the keys are different.
– Each key is connected to exactly one value.
– The mapping shall make it quick to fetch data for a given key.
• Interface java.util.Map
– Keys and data are of arbitrary type.
– If you attempt to insert an already existing key, that one key will be
connected to the new data value you are inserting.
– Methods:
• public Object get(Object key)
• public Object put(Object key, Object data)
• public Object remove(Object key)
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 18
The Class java.util.TreeMap
• The class implements a binary search tree well balanced
• Implements Map and also SortedMap:
– public Object firstKey()
– public Object lastKey()
• Requires the keys to be possible to sort
– either a ”comparator” must be passed as argument to the constructor,
example collator from page TBA:
• TreeMap aTree = new TreeMap(java.text.Collator.getInstance());
– or the class which the keys belong to must implement the interface
Comparable
• Example, tree from chapter 17.4 (slide 15).
– The numbers are keys for the vertices.
– We let the data be person names.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 19
We Try TreeMap
class TreeMapTest {
public static void main(String[] args) {
TreeMap treeExample = new TreeMap();
treeExample.put(new Integer(15), "Rick");
treeExample.put(new Integer(10), "Rob");
treeExample.put(new Integer(28), "Melissa");
treeExample.put(new Integer(3), "Harry");
treeExample.put(new Integer(14), "Ted");
treeExample.put(new Integer(20), "Mildred");
treeExample.put(new Integer(16), "Edina");
treeExample.put(new Integer(21), "Patsy");
Printout:
Contents of the tree: {3=Harry, 10=Rob,
14=Ted, 15=Rick, 16=Edina, 20=Mildred,
21=Patsy, 28=Melissa}
11 is not there
10 is there: Rob
Lowest key value: 3
Highest key value: 28
System.out.println("Contents of the tree: " + treeExample.toString());
String test = (String) treeExample.get(new Integer(11));
if (test == null ) System.out.println("11 is not there");
else System.out.println("11 is there: " + test);
test = (String) treeExample.get(new Integer(10));
if (test == null ) System.out.println("10 is not there");
else System.out.println("10 is there: " + test);
System.out.println("Lowest key value: " + treeExample.firstKey());
System.out.println("Highest key value: " + treeExample.lastKey());
}
}
Solve the problem pp. 552-553.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 20
Hashtables
•
A hashtable differs from
– a binary search tree in that the elements don’t have an intrinsic ordering
– a linked list in that search is faster
•
•
•
Is among other things used in operating systems to organize the files in a
directory
The keys are placed in slots
The slots
key value
hash function slot value
– are usually ordered
– must be unique (duplicates not allowed)
•
Searching and inserting is fast
– calculate the correct slot
– search for the value in the relatively short list in the slot, or
– insert the value, for example at the end of the list
•
The load factor is equal to the ratio between the number and elements and
slots.
– high load factor: long search time, good utilization of space
– low load factor: short search time, needs more space, many slots with few elements
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 21
slot no.
Example of a Hashtable
0
Hash function:
Take the last digit of the
key value.
Each key value could correspond to data
about a person. We have ommitted these.
1
11
2
2
31
3
4
94
5
55
6
16
35
85
7
8
18
108
9
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 22
The Class java.util.Hashtable
• The standard constructor creates a hashtable with 101 slots (a prime
number is good!)
• Rehashing is done when the load factor becomes 0,75
– the number of slots is changed, and all addresses recalculated
• Every class can have its hash function, if not, the implementation of
hashCode() is inherited from the class Object.
• The class Hashtable implements the interface map, with familiar
methods:
– public Object get(Object key)
– public Object put(Object key, Object data)
– public Object remove(Object key)
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 23
Class Describing the Key from Slide 22
class Ident {
private int value;
public Ident(int initValue) {
value = initValue;
}
/* Gets the last numeral in the value */
public int hashCode() { // redefines the hashCode() inherited from Object
int power = 10;
while (value / power > 10) power *= 10;
int remaining = value % power;
while (remaining > 10) {
power /= 10;
remaining %= power;
}
System.out.println("Value " + value + " gives code " + remaining);
return remaining;
}
public String toString() {
return "" + value;
}
public boolean equals(java.lang.Object obj) {
return ((Ident) obj).value == value;
}
}
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 24
Client Program Which Creates and Tests the Hashtable
class HashTest {
public static void main(String[] args) {
Hashtable hashExample = new Hashtable(10); // to fit the figure
hashExample.put(new Ident(2), "Matt");
hashExample.put(new Ident(11), "Tony");
hashExample.put(new Ident(16), "Celine");
hashExample.put(new Ident(18), "Baldrick");
hashExample.put(new Ident(31), "Arnie");
hashExample.put(new Ident(35), "Vinnie");
hashExample.put(new Ident(55), "Quentin");
hashExample.put(new Ident(85), "Alexander");
hashExample.put(new Ident(94), "Pat");
hashExample.put(new Ident(108), "Put");
System.out.println("The contents of the hashtable: "
+ hashExample.toString());
String test = (String) hashExample.get(new Ident(11));
if (test == null ) System.out.println("11 is not there");
else System.out.println("11 is there: " + test);
test = (String) hashExample.get(new Ident(6));
if (test == null ) System.out.println("6 is not there");
else System.out.println("6 is there: " + test);
Printout:
Value 2 gives code 2
Value 11 gives code 1
Value 16 gives code 6
Value 18 gives code 8
Value 31 gives code 1
Value 35 gives code 5
Value 55 gives code 5
Value 85 gives code 5
Value 94 gives code 4
Value 108 gives code 8
The contents of the hashtable: {108=Put,
18=Baldrick, 16=Celine, 85=Alexander,
35=Vinnie, 55=Quentin, 94=Pat, 2=Matt,
11=Tony, 31=Arnie}
Value 11 gives code 1
11 is there: Tony
Value 6 gives code 6
6 is not there
}
}
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 17, page 25