南京大学：《计算机程序的构造和解释 Structure and Interpretation of Computer Programs》课程教学资源（PPT课件讲稿）16-Linked Lists & Mutable Trees

Lecture 17 Linked Lists Mutable Trees Chris Allsman

Lecture 17 - Linked Lists & Mutable Trees Chris Allsman

Announcements ●HW4 due Monday7/29 Proj3 Released o Phase 1 &2 due Friday o Phase 3&4 Due Wednesday,7/31 o Submit 24h early for 1 EC point MT Grades being finalized Advising appointment signups 3:00 today(see piazza)

Announcements ● HW4 due Monday 7/29 ● Proj3 Released ○ Phase 1 & 2 due Friday ○ Phase 3 & 4 Due Wednesday, 7/31 ○ Submit 24h early for 1 EC point ● MT Grades being finalized ● Advising appointment signups @ 3:00 today (see piazza)

Linked Lists

Linked Lists

Linked List Definition A Linked List is either: ● Empty Composed of a first element and the rest of the linked list Value of first is the 2 3 List terminated number 1 with an empty linked list first rest first rest first rest Linked lists are rest contains a pointer to a linked list sequences where each value is the first element of a pair

Linked List Definition A Linked List is either: ● Empty ● Composed of a first element and the rest of the linked list 1 2 3 first rest first rest first rest Value of first is the number 1 rest contains a pointer to a linked list List terminated with an empty linked list Linked lists are sequences where each value is the first element of a pair

Creating Linked Lists Demo We'll define a linked list recursively by making a constructor that takes in a first and rest value 7 2 first rest first rest first rest Link(1 Link(1,Link(2, Link(1,Link(2,Link(3,empty linked list))

Creating Linked Lists We’ll define a linked list recursively by making a constructor that takes in a first and rest value 1 2 3 first rest first rest first rest Link(1 , __________________________________) Link(1 , Link(2, _________________________)) Link(1 , Link(2, Link(3, empty linked list)) Demo

The Link Class class Link: You should not assume empty the representation here Rest defaults to def __init__(self,first,rest=empty): the empty list assert rest is Link.empty or isinstance(rest,Link) self.first first first->Ist[0] self.rest rest rest->Ist[1:] >>> Ink Link(5,Link(6,Link(7))) Ink is Link.empty->not Ist >>Ink.rest.rest.first first gives elements in the list,.rest traverses 7 >>> Ink.rest.rest.rest is Link.empty Compare to empty list True

The Link Class class Link: empty = () def __init__(self, first, rest=empty): assert rest is Link.empty or isinstance(rest, Link) self.first = first self.rest = rest >>> lnk = Link(5, Link(6, Link(7))) >>> lnk.rest.rest.first 7 >>> lnk.rest.rest.rest is Link.empty True Rest defaults to the empty list You should not assume the representation here Compare to empty list .first gives elements in the list, .rest traverses .first -> lst[0] .rest -> lst[1:] lnk is Link.empty -> not lst

You Try: class Link: >>> a Link(1,Link(2,Link(1))) empty ( >>> b Link(3,Link(2,Link(1))) >>> def __init__(self,first, combined Link(a,Link(b)) rest=empty): How would you retrieve the element 3? self.first first self.rest rest 1.combined.rest.first.rest 2.combined.rest.rest.first 3.combined.rest.first.first 4.combined.first.rest.rest 5.combined.first.rest.first

You Try: class Link: empty = () def __init__(self, first, rest=empty): self.first = first self.rest = rest >>> a = Link(1, Link(2, Link(1))) >>> b = Link(3, Link(2, Link(1))) >>> combined = Link(a, Link(b)) How would you retrieve the element 3? 1. combined.rest.first.rest 2. combined.rest.rest.first 3. combined.rest.first.first 4. combined.first.rest.rest 5. combined.first.rest.first

You Try: a Link(1,link(2,link(1))) 2 b Link(3,link(2,link(1))) 3 combined.rest is an arrow to the next link combined.rest.first is an arrow to b combined Link(a,: Link(b.)) combined.rest:first first

You Try: b = Link(3, link(2, link(1))) combined.rest is an arrow to the next link combined.rest.first is an arrow to b 3 2 1 combined = Link(a, Link(b)) 1 2 1 a = Link(1, link(2, link(1))) combined.rest.first.first

Processing Linked Lists

Processing Linked Lists

Sum Goal:Given a linked list,Ink,return the sum of all elements in the linked list 、2 3 6 十 5 6

Sum Goal: Given a linked list, lnk, return the sum of all elements in the linked list 1 2 3 6 1 + 5 6