⬇️ This week's worksheet

mentor09.pdf

mentor09_sol.pdf

Linked List Pointer Demonstration

👀 example: lnk = Link(3, Link(4, Link(Link(9, Link(3)), Link(4, Link(2)))))

Code Writing Tips: Mutative vs. Non-Mutative

Mutative methods:

• assign link.rest = Link("something") or link.first = someting → reassign value of first or rest
• link.rest = f(link.rest)
• return none or link

Non Mutative methods

• Do not edit link.first or link.rest
• link = link.rest is okay. This just moves the pointer, doesn't mutate the LL
• calls the constructor: Link("sth", "sth") which results in a new linked list

Code Writing Tips: Recursive vs. Iterative

Recursive:

Base cases:

• if link is Link.empty
• if link.rest is Link.empty

Recursive call:

• f(link.rest)
• return Link(link.first, f(link.rest))

Iterative:

• while link is not Link.empty and link.rest is not Link.empty
• last line in while loop → link = link.rest to move the pointer (like x = x + 1)

Code Writing Practice: Merge two lists, return a sorted linked list

• Method 1: Non Mutative → return new list
• Method 2: Mutative → mutate list in-place