EECS 111 Lecture Notes - Lecture 6: Linked List, London Academy Of Music And Dramatic Art, Mymusic
21 views6 pages
8 Mar 2018
School
Course
Professor
Lists%are%sequences%of%data%objects
Any%length%
○
Any%type%of%data%object
○
Different%types%can%be%mixed%in%the%same%list%
○
•
Sceme%and%Racket%use%a%particular%type%of%list%called%a%linked%list%
•
Example:%A%music%collection%
A%list%of%album%objects
○
•
!"!#$%&"'$()"*'+#$'","-(.%#/'0000000'
123'42567'89:;'72'<;<2=>?;'@A;B>C>B'A=2B;43=;@
○
•
Simple%list%constructors%
(list%item1,%item%2,%…itemX)
Creates%a%list%containing%the%specified%items,%in%order%
§
○
(append%%item1,%item%2,%…itemX)
Creates%a%new%list%with%all%the%items%from%the%input%list,%in%order
§
○
•
Simple%list%accessors%
(C>=@7list),%(second%list),%…%(tenth%list)
Extracts%the%@A;B>C>;4';D;<;57 of%list
§
○
(=;@7 list)%
Returns%E))'F(. the%first%element%of%list
§
○
(D>@7G=;C list%index)
Extracts%the%element%at%position%index%(a%number)
Index%counts%from%zero%
□
§
○
(D;5H78 list)
○
•
(define%my-list%(list%1%2%3))
(list%1%2%3)
○
•
(append%my-list%(list%4%5%6))
(list%1%2%3%4%5%6)
○
•
(rest%(append%%my-list%(list%4%5%6)))
(list%2%3%4%5%6)
○
•
Empty%list%
empty
○
(list)
○
•
Examples
Lists%can%
Be%empty:%(list)
§
Mix%different%types%of%data:%(list%"a"%"b"%"c"%1%2%3)
§
Have%other%lists%inside%them%(list%"a"%(list%"b"%"c"))
§
○
•
The%length%of%a%list%is%the%number%of%elements%in%it%•
When%a%list%has%a%list%I>78>5'>7,%the%sublist%only%counts%as%one%element•
Lists%are%numbered%from%0%(first%item%=%item%0,%second%item%=%item%1)•
Asking%for%an%element%past%the%end%of%the%list%gives%an%IdexOutOfRangeException•
/"J'K$#-"L($"M'+%)."$'
(filter%predicate%list)
○
;;filter:%(X%->%Boolean)%(listofX)%->%(listofX)
○
Returns%ALL%THE%ITEMS%satisfying%predicate%(so%all%items%that%would%be%"true")
○
Examples:
(filter%odd?%(list%1%2%3%4%5%6))
(list%1%3%5)□
§
(filter%number?%(list%1%2%"three))
(list%1%2)□
§
○
•
Finding%all%the%Beatles%albums%
(filter%Beatles?%Mymusic)
(list%(make-album%"The%White%Album"
"The%Beatles"%"Rock")
(Make-album%"Name"
"The%Beatles"%"Rock"))
○
(filter%(lamda%(album)
(string=?%(album-artist%album)
"The%Beatles"))
mymusic)
○
•
Beatles?%Is%just%a%variable,%so%we%can%just%type%its%value%rather%than%the%name%•
Filter%returns%a%list%of%equal%or%smaller%length%than%original%list%•
#=<9A:%are%there%any%items%in%this%this%that%pass%the%Boolean?
Takes%a%predicate%and%a%list
○
•
E54<9A:%do%all%items%in%this%list%pass%the%Boolean?
Takes%a%predicate%and%a%list
○
•
!EKK%/N
(map%procedure%list)
○
;;%map:%(In%->%Out)%%(listofln)%->%(listofOut)
○
Runs%procedure on%;:;=O';D;<;57
○
Outputs%their%return%values%as%a%new%list%
Ex.%(map%proc%(list%a%b%c))%is%equivalent%to%(list%(proc%a)%(proc%b)%(proc%c))
§
○
Example
(map%-(list%1%2%3%4))%------->>>>>%%%%(list%-1%-2%-3%-4)
§
○
Input%list%and%list%of%results%are%the%same%length%
○
•
$;<2:;G43AD>B97;@ takes%a%list%and%returns%a%new%copy%of%it%with%duplicate%elements%removed•
+#)L%/N
(foldl%proc%start-value%list)
○
(foldr%proc%start-value%list)
L%and%r%are%left%and%right
§
○
;;%foldl/foldr%:%(X%X%->%X)%X%(listofX)%->%X
○
Aggregates%all%values%of%list%together%using%procedure%proc%
○
Summing%or%multiplying%elements%of%a%list%
○
(foldl%proc%start%(list%a%b%c))%is%equivalent%to%(proc%c%(proc%b%(proc%a%start)))%%%%(starts%with%leftmost%item)
○
(foldr%proc%start%(list%a%b%c))%is%equivalent%to%(proc%a%(proc%b%(proc%c%start)))%%%(starts%with%rightmost%item)
○
•
Averaging%
;;sum:%(list%of%number)%->%number
○
;;%(define%sum%
(lambda%(lst)%(foldl%+%0%lst)))
○
Mean:%(listof%number)%->%number
○
•
Iterating%
(build-list%count%proc)
○
;;build-list:%number%(number%->%X)%->%(listofX)
○
Runs%proc%repeatedly%
○
•
These%are%the%same%thing
Lists
Monday,%January%29,%2018
12:02%PM
Lists%are%sequences%of%data%objects
Any%length%
○
Any%type%of%data%object
○
Different%types%can%be%mixed%in%the%same%list%
○
•
Sceme%and%Racket%use%a%particular%type%of%list%called%a%linked%list%•
Example:%A%music%collection%
A%list%of%album%objects
○
•
!"!#$%&"'$()"*'+#$'","-(.%#/'0000000'
123'42567'89:;'72'<;<2=>?;'@A;B>C>B'A=2B;43=;@
○
•
Simple%list%constructors%
(list%item1,%item%2,%…itemX)
Creates%a%list%containing%the%specified%items,%in%order%
§
○
(append%%item1,%item%2,%…itemX)
Creates%a%new%list%with%all%the%items%from%the%input%list,%in%order
§
○
•
Simple%list%accessors%
(C>=@7list),%(second%list),%…%(tenth%list)
Extracts%the%@A;B>C>;4';D;<;57 of%list
§
○
(=;@7 list)%
Returns%E))'F(. the%first%element%of%list
§
○
(D>@7G=;C list%index)
Extracts%the%element%at%position%index%(a%number)
Index%counts%from%zero%□
§
○
(D;5H78 list)
○
•
(define%my-list%(list%1%2%3))
(list%1%2%3)
○
•
(append%my-list%(list%4%5%6))
(list%1%2%3%4%5%6)
○
•
(rest%(append%%my-list%(list%4%5%6)))
(list%2%3%4%5%6)
○
•
Empty%list%
empty
○
(list)
○
•
Examples
Lists%can%
Be%empty:%(list)
§
Mix%different%types%of%data:%(list%"a"%"b"%"c"%1%2%3)
§
Have%other%lists%inside%them%(list%"a"%(list%"b"%"c"))
§
○
•
The%length%of%a%list%is%the%number%of%elements%in%it%•
When%a%list%has%a%list%I>78>5'>7,%the%sublist%only%counts%as%one%element•
Lists%are%numbered%from%0%(first%item%=%item%0,%second%item%=%item%1)•
Asking%for%an%element%past%the%end%of%the%list%gives%an%IdexOutOfRangeException•
/"J'K$#-"L($"M'+%)."$'
(filter%predicate%list)
○
;;filter:%(X%->%Boolean)%(listofX)%->%(listofX)
○
Returns%ALL%THE%ITEMS%satisfying%predicate%(so%all%items%that%would%be%"true")
○
Examples:
(filter%odd?%(list%1%2%3%4%5%6))
(list%1%3%5)□
§
(filter%number?%(list%1%2%"three))
(list%1%2)□
§
○
•
Finding%all%the%Beatles%albums%
(filter%Beatles?%Mymusic)
(list%(make-album%"The%White%Album"
"The%Beatles"%"Rock")
(Make-album%"Name"
"The%Beatles"%"Rock"))
○
(filter%(lamda%(album)
(string=?%(album-artist%album)
"The%Beatles"))
mymusic)
○
•
Beatles?%Is%just%a%variable,%so%we%can%just%type%its%value%rather%than%the%name%•
Filter%returns%a%list%of%equal%or%smaller%length%than%original%list%•
#=<9A:%are%there%any%items%in%this%this%that%pass%the%Boolean?
Takes%a%predicate%and%a%list
○
•
E54<9A:%do%all%items%in%this%list%pass%the%Boolean?
Takes%a%predicate%and%a%list
○
•
!EKK%/N
(map%procedure%list)
○
;;%map:%(In%->%Out)%%(listofln)%->%(listofOut)
○
Runs%procedure on%;:;=O';D;<;57
○
Outputs%their%return%values%as%a%new%list%
Ex.%(map%proc%(list%a%b%c))%is%equivalent%to%(list%(proc%a)%(proc%b)%(proc%c))
§
○
Example
(map%-(list%1%2%3%4))%------->>>>>%%%%(list%-1%-2%-3%-4)
§
○
Input%list%and%list%of%results%are%the%same%length%
○
•
$;<2:;G43AD>B97;@ takes%a%list%and%returns%a%new%copy%of%it%with%duplicate%elements%removed•
+#)L%/N
(foldl%proc%start-value%list)
○
(foldr%proc%start-value%list)
L%and%r%are%left%and%right
§
○
;;%foldl/foldr%:%(X%X%->%X)%X%(listofX)%->%X
○
Aggregates%all%values%of%list%together%using%procedure%proc%
○
Summing%or%multiplying%elements%of%a%list%
○
(foldl%proc%start%(list%a%b%c))%is%equivalent%to%(proc%c%(proc%b%(proc%a%start)))%%%%(starts%with%leftmost%item)
○
(foldr%proc%start%(list%a%b%c))%is%equivalent%to%(proc%a%(proc%b%(proc%c%start)))%%%(starts%with%rightmost%item)
○
•
Averaging%
;;sum:%(list%of%number)%->%number
○
;;%(define%sum%
(lambda%(lst)%(foldl%+%0%lst)))
○
Mean:%(listof%number)%->%number
○
•
Iterating%
(build-list%count%proc)
○
;;build-list:%number%(number%->%X)%->%(listofX)
○
Runs%proc%repeatedly%
○
•
These%are%the%same%thing
Lists
Monday,%January%29,%2018 12:02%PM