Class Notes (1,100,000)
CA (620,000)
Carleton (20,000)
COMP (500)
Lecture 2

COMP 2402 Lecture Notes - Lecture 2: Comparator


Department
Computer Science
Course Code
COMP 2402
Professor
Pat Morin
Lecture
2

Page:
of 6
COMP2402AT30120130910Week2Class1
introductiontothefirstassignment.(Justreadingwhat'sontheassignmentwebpage)
donotmodifymain{}.
firstsourceforhelpwiththeassignmentistopostintheculearnforum.
profseemsnervousthatpeoplewillbeabletofinishthisintime.
JavaCollectionsFramework
asajavaprogrammeryoushouldknowthisinsideout
thecolectionsframworkservesasagoodintroductiontodatastructuresandperformancetradeoffs.
Theframeworkcontains
1.Interfaces>specifiestheoperations(methods/functions)thataresupported(bysomeclass)(What)
2.Implementation>code(classes)thatimplementstheoperationsdefinedwithintheinterface(How)
3.Algorithms>coodethatdoes"something".(notadatastructure).Injavaareusuallystaticmethods.Orproceduresinother
languages.
Interfaces
likeaclass
alistofmethodswithnobodies.
Typesofinterfacesinjava
Collection<T>
storessomeobjectsoftypeT
add(x)[usuallysupported],remove(x)[sometimessupported],size()[almostalways],iterate[always]
String[] a =
{"sheldon", "penny", "raj", "leonard", "amy",
"bernadette", "howard", "stuart" };
System.out.println("Contents of a:");
for (String s : a)
System.out.println(s);
Collection<String> c = new ArrayList<String>();
for (String s : a)
c.add(s);
System.out.println("Contents of c: " + c);
System.out.println("c.size() = " + c.size());
Set<T>
amathematicalset
setsareinahashedorderthatcannotbereliedupon,designedtobefast.
anunorderedsetofdistinctitems
add(x)[usuallysupported],remove(x)[sometimessupported],size()[almostalways],contains()[T/Fifsetcontainsx],iterate
[always]
contains()istheadvantageofaset.usuallythismethodisreallyfast.
Set<String> s = new HashSet<String>();
s.addAll(c);
System.out.println("Contents of s: " + s);
System.out.println("s.contain(raj): " + s.contains("raj"));
System.out.println("s.contain(smeldon): " + s.contains("smeldon"));
s.add("smeldon");
s.add("raj");
System.out.println("Contents of s: " + s);
SortedSet<T>
aspecialsetthatstoresthingsinasortedorder.
justalittlebitslowerthanSet
ifyoudon'tspecificallyneedasortedset,useset
SortedSet<String> ss = new TreeSet<String>();
ss.addAll(c);
System.out.println("Contents of ss: " + ss);
System.out.println("ss.contain(raj): " + ss.contains("raj"));
System.out.println("ss.contain(smeldon): " + ss.contains("smeldon"));
ss.add("smeldon");
ss.add("raj");
System.out.println("Contents of ss: " + ss);
List<T>
asequenceofitems,indexed0,1,2,3..,size()1[wheneveryoutalkaboutadatastructuretheelement"n"isthenumberof
elements]
add(i,x),add(x),remove(i),get(i),set(i,x)aresupported.
efficiencyofalistissuspectanddependscompletelyontheimplementationofthelist.
List<String> ell = new ArrayList<String>();
for (String x : c)
ell.add(x);
System.out.println("Contents of ell: " + ell);
ell.remove(2);
System.out.println("Contents of ell: " + ell);
Queue<T>
conceptuallyimagineabagwithsomeelementsinit.
add(x),andremove()<youdon'tgettospecifywhatyouwanttoremove.Theimplementationofthequeuedetermineswhat
isremoved.
FIFO[traditionalqueue]firstinfirstout,LIFO[stack]lastinfirstout
[nocodeexamplegiveninclass]
Map<K,V>
mapsarenotcollectionsbecausetheytakekeysontovalues.
storesasetofkeys
eachkeyisasignedavalue
get(k),put(k,x)
Map<String,String> m = new HashMap<String,String>();
m.put("amy", "girl");
m.put("sheldon", "boy");
m.put("penny", "girl");
m.put("leonard", "boy");
System.out.println("Contents of m: " + m);
m.put("sheldon", "asexual");
System.out.println("Contents of m: " + m);
System.out.println("m.get(sheldon): " + m.get("sheldon"));
COMP2402AT30120130912Week2Class2
Todaywe'regoingtotalkaboutimplimentationsoftheinterfaces.
Asyoucanseefromthetable,theJavaCollectionsFrameworkprovidesseveralgeneralpurposeimplementationsoftheSet,List,
andMapinterfaces.Ineachcase,oneimplementation—HashSet,ArrayList,andHashMap—isclearlytheonetouseformost
applications,allotherthingsbeingequal.NotethattheSortedSetandtheSortedMapinterfacesdonothaverowsinthetable.Eachof
thoseinterfaceshasoneimplementation(TreeSetandTreeMap)andislistedintheSetandtheMaprows.Therearetwogeneral
purposeQueueimplementations—LinkedList,whichisalsoaListimplementation,andPriorityQueue,whichisomittedfromthetable.
Thesetwoimplementationsprovideverydifferentsemantics:LinkedListprovidesFIFOsemantics,whilePriorityQueueordersits
elementsaccordingtotheirvalues.
Ifyouwanttouseamap,onlyuseTreeMapifyouneeditsorted.
ifyouwanttouseaset,onlyuseTreeSetifyouneeditsorted.
handyruletodetermineifyouwanttouseanaraylistorlinkedlist?
arraylistsstoreelementsinanarray
arraylistget(i),set(i,x)add(x)arefast
add(i,x),remove(i)>havetomovenielementstheyarefastonlywhenweaddorremovefromtheend
fi gu re re m ovin ga ni te m from an ArrayLi st.
linkedlistget(i),set(i,x),add(i,x),andremove(i)arenotreallythatfastbecausetheyhavetotraversethroughthenodestofind
theelementwe'reinterestedin.
putsomesortofdiagramherethatillustratesadoublelylinkedlist
ivs.nitoexplainwhichsidetostarton.
fi gu re Dou bl e Li n ke dLi st
anoteaboutqueueimplimentations
anarraylistisagoodchoicetoimplimentastack(describeastack)
alinkedlistisagoodwaytoimplimentaFIFOstackandaqueue.
defineapriorityqueuehere
defineamapquickly.applythattoapriorityqueue