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