FIT1008 Lecture Notes - Lecture 6: Linked List, Iter, Init
18 Jun 2018
School
Department
Course
Professor
!"#$%&'#(&%)'*+)%&
,-.(//%.0"(#-(1-#(&%)
2+.3-#(&% .(#0+"#)4
5-6-&+0+-"0%7-8item9
:
5-6-/"#$-0(-+#(03%;-#(&%-8next9
:
<;()4
=+)0-"#)%;0"(#-+#&-&%/%0"(# (1-"0%7)>-)"#.%-#(-#%%&-1(;-;%)3?11/"#@
:
2+)"/A-;%)"B+*/% 'C?)0-.;%+0%D&%/%0%-#(&%
:
E%F%;-1?// 8?#/%))-(?0-(1-7%7(;A-0(-)0(;%-"09
:
!%))-7%7(;A-?)%&-03+#-+;;+A-'"1-+;;+A-")-;%/+0"F%/A-%7G0A
:
H(#)4
I(;%-7%7(;A-?)%&-03+#-+;;+A-'"1-+;;+A-")-;%/+0"F%/A-1?//>-)"#.%-%F%;A-&+0+-
"0%7-3+)-+#-+))(."+0%&-/"#$
:
=(;-)(7%-&+0+-0AG%)>-.%;0+"#-(G)-+;%-7(;%-0"7%'.(#)?7"#@ 8%@J-#(-;+#&(7-
+..%))9
:
!")0-)"B% ")-?#$#(K#>-1/%L"*"/"0A ;%M?";%&-8/(0)-(1-"#)%;0"(#)-+#&-&%/%0"(#)9
List ADT
NG)4
O+?L"/"+;A-7%03(&P
__init__(self)
self.head 8G("#0)-0(-1";)0-"0%7-"#-/")09
○
:
is_empty(self)
:
is_full(8+/K+A)-False9:
reset(self) 8%7G0"%)-/")09:
__len__(self)
return self.__length(self.head)
○
:
__contains__(self, item)
return self._contains_aux(self, current, item)
○
:
copy(self)
new_list = List()
○
self._copy_aux(self.head, new_list)
○
return new_list
○
:
_get_node(self, index)
:
insert(self, index, item)
:
delete(self, index)
:
__iter__(self)
return myLinkedListIterator(self.head)
○
:
Q%00%;-1(;-"#)%;0"#@D&%/%0"#@ .(7G+;%&-0(-+;;+A'*+)%&-F%;)"(#-'N8#9
R"7G/A-7(&"1A"#@-/"#$)>-#(0-7(F"#@-%F%;A03"#@-(#%-)0%G-*+.$
S1-"#&%L-")-T4
I+$%-3%+&-03%-#%L0-(1-(;"@-3%+&U
§
S1-"#&%L-#(0-T4
I+$%-/"#$-(1-G;%F"(?)-(#%-8(1-(;"@9-/"#$-0(-03%-#%L0-(#%-
8(1-(;"@9
U
§
○
:
Can+Linked+List+implementation+be+modified+to+achieve+constant+time+append+
to+the+end+ops?
V%)>-*A-$%%G"#@-+-;%1%;%#.% 0(-03%-/+)0-%/%7%#0-+GG%#&%& 0(-03%-%#&J
Stack ADT
NG)4
__init__(self)
self.top 8"#&".+0"#@-0(G-"0%7-"#-)0+.$9
○
self.count
○
:
is_empty(self)
:
push(self, item) 8+&&-"0%7-0(-0(G9
H;%+0%)-#%K-#(&%-K"03-#%K-"0%7-'#%L0-")-(/&-0(G-#(&%
○
!"#$)-"0-0(-.?;;%#0-0(G
○
I+$%)-#%K-#(&%-#%K-0(G
○
self.top = Node(item, self.top)
○
:
pop(self) 80+$%-"0%7-(11-0(G>-)"#.%-!S=N9:
reset(self) 8%7G0"%)-/")09:
Queue ADT
NG)4
__init__(self)
self.front 87+;$)-1;(#0-(1-M?%?%>-;%1%;)-0(-1";)0-%/%7-0(-*%-
)%;F%&9
○
self.rear = Node()
87+;$)-;%+;-(1-M?%?%>-;%1%;)-0(-1";)0-%7G0A-)/(0-+0-;%+;9
○
:
append(self) 8+&&)-"0%7-+0-;%+;9:
serve(self) 8;%7(F%)-"0%7-1;(7-1;(#09:
reset(self) 8%7G0"%)-/")09:
append(self, item)
S1-#(0-%7G0A
I+$%-"0%7-(1-;%+;-#%K-"0%7
§
I+$%-#%L0-(1-;%+;-G("#0-+-#%K-#(&%
§
I+$%-#%K-;%+;-03+0-#%K-#(&%
§
○
S1-%7G0A
H;%+0%-#%K-#(&%-K"03-"0%7-03+0-G("#0)-0(-;%+;
§
I+$%-#%K-#(&%-03%-1;(#0
§
I+$%-;%+;-03%-1;(#0W)-#%L0
§
○
:
serve(self)
H3%.$-8G;%.(#&"0"(#-?)"#@-+))%;09-03+0-/")0-")-#(0-%7G0A
○
H;%+0%-F+;"+*/%-1(;-"0%7-0(-)%;F%
○
I+$%-1;(#0-03%-#%L0-"0%7-(1-03%-G;%F"(?)-1;(#0
○
S#./?&%-.+)%-1(;-"1-03%;%-")-(#/A-6-%/%7%#0-"#-M?%?%-87+$%-;%+;-E(#%-
+/)(9
○
:
XX
!"#$%&'#(&%-/")0 Y;;+A'*+)%&-/")0
Z"7%-
.(7G/%L"0
A
8+&&"#@9
E-"0%7)-+;%-0;+F%;)%&-%F%;A-
0"7%>-+#&-.(#)0+#0-0"7%-(G-
G%;1(;7%&-87(&"1A"#@-/"#$)>-
+&&"#@-"0%79
8&%/%0"#@9
E%%&-0(-)3?11/%-)(7%-%/%7%#0)-%+.3-
#-0"7%)-K3%#-#-"0%7)-+;%-&%/%0%&
211"."%#.A [?"0%-%11"."%#0-'(#/A-7(&"1"%)-
/"#$-(#.%-%F%;A-\#
R/"@30/A-/%))-%11"."%#0-'#%%&)-0(-$%%G-
0;+.$-(1-.(?#0%;)-81";)0-#-%/%7)-03+0-
#%%&-0(-*%-)3?11/%&>-%/%7)-03+0-#%%&-
0(-*%-(F%;K;"00%#>]9
Week$6-7:$container$ADTS$(linked-nodes)
Z3?;)&+A>-6^-_?#%-\T6`
\a46a
Document Summary
Fast insertion and deletion of items, since no need for reshuffling. Never full (unless out of memory to store it) Less memory used than array - if array is relatively empty. More memory used than array - if array is relatively full, since every data item has an associated link. For some data types, certain ops are more time-consuming (eg. no random access) List size is unknown, flexibility required (lots of insertions and deletions) __init__(self) self. head (points to first item in list) self. head (points to first item in list) is_empty(self) is_full((always false) reset(self) (empties list) __contains__(self, item) return self. _contains_aux(self, current, item) copy(self) new_list = list() self. _copy_aux(self. head, new_list) return new_list. Better for inserting/deleting compared to array-based version - o(n) Simply modifying links, not moving everything one step back. Make link of previous one (of orig) link to the next one (of orig) Yes, by keeping a reference to the last element appended to the end.
