Transcript Lec. notes

ISOM
MIS 215 Module 1 –
Ordered Lists
Where are we?
ISOM
MIS215
Basic Algorithms
Introduction List Structures
Search
Techniques
Intro to
Java, Course
Java lang.
basics
Linked
Lists
Arrays
Sorting Techniques
Hashtables
Binary Search
Stacks,
Queues
Advanced structures
Graphs,
Trees
Bubblesort
Fast Sorting algos
(quicksort, mergesort)
Newbie
Programmers
Designers
Developers
Professionals
2
Today’s buzzwords
ISOM
• Ordered Lists
 Lists that need to be kept ordered for whatever semantic
reason
 We always assume that order is based on a key
• Templates
 A special Object-Oriented technique by which collections
can be created which do not have a “hardcoded” content
type
Primary difference
ISOM
• Items must have a (partial) ordering
• Orders among basic types is simple using < = >
• Orders among objects are achieved in Java using
the “Comparable” interface
compareTo
equals
• So… how do you make a list of objects?
Templates in Java
ISOM
• Problem: You want to store an object in a
list.
• Examples:
• So should you create a separate list
class for every object?
• Solution: Template
How do you use a Template?
ISOM
/**
* Turning our good old Mylist to a template
*/
public class MyTemplateList<T> {
// The array to store the values
private T datastore[];
private final int MAX = 50;
private int numelements =0;
/**
* The MyList Constructor - we may need variants later
*/
public MyTemplateList() {
datastore = (T[])(new Object[MAX]);
}
…
/**
* The find method - takes a target and returns true if item is in the list
**/
public boolean find(T target) {
for(int i=0; i < this.size(); i++)
if (datastore[i].equals(target)) return true;
return false;
}
/**
* Insert method - insert a new element
* returns true if insert was successful, false otherwise
**/
public boolean insert(T x) {
if (isListFull()) return false;
datastore[numelements] = x;
numelements ++;
return true;
}
And how do we use it?
ISOM
To use it with integers:
MyTemplateList<Integer> l = new MyTemplateList<Integer>();
l.insert(new Integer(50)); l.insert(new Integer(35));
l.insert(new Integer(75)); l.insert(new Integer(532));
System.out.println("List empty returns: " + l.isListEmpty());
System.out.println("List full returns: " + l.isListFull());
System.out.println("List size returns: " + l.size());
l.traverse();
To use it with strings:
MyTemplateList<String> lstr = new MyTemplateList<String>();
lstr.insert("John"); lstr.insert("Jill");
lstr.insert("Mike"); lstr.insert("Mary");
lstr.traverse();
System.out.println("find(John) - item in the list - returns: " +
lstr.find("John"));
System.out.println("find(Tom) - item not in the list - returns: " +
lstr.find("Tom"));
Exercise: How would you turn
MyLinkedList to Templates?
ISOM
Lets get back to Ordered Lists
ISOM
• Think array implementation for now
• How would insert change?
• How would find change?
What about complexity?
ISOM
Complexity of _____________
A. O(1) … i.e., Constant time
B. O(lg n) … faster than linear!
C. O(n) … i.e., proportional to #items
D. More than O(n)?
The binary search algorithm
ISOM
• Since the list is ordered, there is no
point starting at the beginning
• Lets start at the middle
If target is > item where would it be?
Otherwise?
• What do we achieve?
• Whats the worst case number of
comparisons, for, say, 15 items?
Build this table for lists
ISOM
Operation
Unordered List
Ordered List
create/constructor
O(1)
O(1)
size
clear
traverse
isListFull
isListEmpty
insert
remove
find
findMin
findMax
findAvg
Points to Ponder
ISOM
• Would it make sense to implement an
ordered list using a Linked List?