ENG1003 Lecture Notes - Lecture 10: Lowest Common Ancestor, Linked List
30 May 2018
School
Department
Course
Professor
Linked'lists'**VS'arrays
!"#$%&$&% '()*"+,&$&"&-.,"(*&/01#%&"2#(1*)"*#"*,&"1&3*"41*('"*,&"&1%"#5"*,&".,-(1
6''#+"&-)7"(*&$-*(#1 *,$#48,"*,&"'()*
9
:'&/)".-1";&"-%%&%0$&/#<&%"*#"'()*"(1".#1)*-1*"*(/&="(1<#'<&)"-%>4)*(18"-"
)(18'&"next <-'4&"*#"2#(1*"*#"1&+"1#%&
9
?)&54'"5#$"(/2'&/&1*(18"%-*-")*$4.*4$&)"'(@&"queues
A;>)"-$&"2$#.&))&%"B-1%"$&/#<&%C"5$/"5$#1*"#5"D4&4&="1&+"#;>)"#1'7"
-%%&%"*#"&1%
○
9
?)&%"5#$"5('&")*#$-8&"#1"%()@)"+,&$&"-"'-$8&"5('&"+'%";&")2'(*"(1*#"2(&.&)"-1%"
)2$&-%"-.$#))"%()@
9
E#1F* -''#+"$-1%#/ -..&))"*#"-17"&'&/
G#"8&*"*#"-"2-$*(.4'-$"1#%&=",-<&"*#"*$-<&$)&"next '(1@)")&D4&1*(-''7
5$/";&8(11(18"#5"'()*
○
9
data 2$#2&$*7"H"next 2$#2&$*7"B2#(1*)"*#"*,&"1&3*"1#%&"<(-"IJ"$&5"#$"nullC
Trees
!"%-*-")*$4.*4$&)"(1"+,(.,"&-.,"1#%&",-)"-1"&%8&".#11&.*(18"(*"-17"14/;&$"#5
.,('%"1#%&)
K-1"$&2",(&$-$.,(.-'"(15#"&8L"#$8-1()-*(#1-'".,-$*)="$&2#$*(18")*$4.*4$&="
5-/('7"*$&&
9
E&2*,M5($)*")&-$.,N"611-O"I#-1P
9
Q$&-%*,M5($)*")&-$.,N"611-O"I-.@P
9
R#+&)*".#//#1"-1.&)*#$"B&8L"#5"J-/-1*,-"-1%"S#&"MMT"I-.@C"B)*#$&"2-*,"*#"
&-.,"1#%&"-1%"5(1%"'-*&)*"/-*.,(18"#1&C
9
:8L"EAU BE#.4/&1*"A;>&.*"U#%&'C
EAU"1#%&)",-<&"/&*,#%)"*#"/#%(57"*$&&")*$4.*4$&"#5"EAU"B&8L"
appendChild, removeChild, parentNodeC
○
9
GraphsB01&*+#$@)C
U#$&"-;)*$-.* $&2)"#5"*$&&)9
?)&%"5#$".#11&.*(18 22'"B-22'(.-*(#1)C="5#$"$#4*(18"-1%"1-<(89
K#1)()*(18"#5")&*)"-1%"1#%&)".#11&.*&%"*8*";7"&%8&)
:%8&)".-1";&"41%($&.*&%0%($&.*&%
E(55&$&1.&"'(&)"(1"-$$#+)"*,-*"(1%(.-*&"%($&.*(#1"#5"$&'-*(#1
§
○
9
Linked' list Array Dynamic'
array
Balanced'
tree
Random a
ccess' list
hashed'
array'tree
V1%&3(18 WBnC WBXC WBXC WB'#8"1C WB'#8"1CYZ[ WBXC
V1)&$*0%&'&*
&-*"
;&8(11(18
WBXC \06 WBnC WB'#8"1C WBXC WBnC
V1)&$*0%&'&*
&-*"&1%
WBXC"+,&1"
'-)* &'&/&1*"
()"@1#+1O
WBnC"+,&1"
'-)* &'&/&1*"
()"41@1#+1
\06 WBXC -/#
$*(]&%
WB'#8 nC WB'#8 nC"
42%-*(18
WBXC -/#
$*(]&%
V1)&$*0%&'&*
&(1"/(%%'&
)&-$.," *(/&"
^ WBXCY_[Y`[
Ya[
\06 WBnC WB'#8 nC WB'#8 nC"
42%-*(18
WBnC
b-)*&%"
)2-.& B-<&$
-8&C
WBnC c WBnCYd[ WBnC WBnC WBenC
f&2$&)&1*)"$&'-*(#1-'".#11&.*(#1)";&*+&&1"*,(18)
U-@&)"(*"&-)7"*#")&-$.,="2&$5#$/"$&)&-$.,="%&<&'#2
g-$"#;>X"!"h1-/&N"iij
g-$"#;>k"!"#;>XO
P
A;>XL1-/&"!"iJ*&<&i
P
QAGl"$&*4$1")-/&"*,(18)m":<&1"*,#48,"#1'7"A;>X".,-18&%m
Week$10:$Problem-Solving$w/$Algos$and$Data$Strucs
J-*4$%-7="`"U-7"kcXa
X`NZ`
Document Summary
Makes it easy to search, perform research, develop. Week 10: problem-solving w/ algos and data strucs. = ordered list where each item/node points to the next until the end of the chain. Elems can be added/removed to list in constant time, involves adjusting a single next value to point to new node. Objs are processed (and removed) frm front of queue, new objs only added to end. Used for file storage on disks where a large file wld be split into pieces and spread across disk. To get to a particular node, have to traverse next links sequentially frm beginning of list data property & next property (points to the next node via js ref or null) = data structures in which each node has an edge connecting it any number of child nodes. Can rep hierarchical info eg. organisational charts, reporting structure, family tree.
