Linked Lists & Mutable Trees

Linked Lists

Linked List Definition

A Linked List is either :

- Empty

- Composed of a first element and the rest of the linked list

Creating Linked Lists

: We’ll define a linked list recursively by making a constructor that takes in a first and rest value

The Link Class

Processing Linked Lists

- Sum

Goal : Given a linked list, lnk, return the sum of all elements in the linked list

- display_link

Goal : Given a linked list, lnk, return a string representing the elements in the linked list

- Map

Goal : Given a linked list, lnk, and a one argument function, f, return a new linked list obtained from applying f to each element of lnk

Mutating Linked Lists

- Map, V2

Goal : Given a linked list, lnk, and a one argument function, f, mutate the linked list by applying f to each element.

Goal : Given a linked list, lnk, and a one argument function, f, mutate the linked list by applying f to each element

Why Linked Lists?

-   Insert element at index 1

-   Total number of operations = 1 minus the length of the list

Tree Class

Tree Abstraction

-   Recursive Description ( wooden trees )

: A tree has a root and a list of branches

: Each branch is a tree

: A tree with zero branches is called a leaf

-   Relative Description ( family trees )

: Each location in a tree is called a node

: Each node has a label value

: One node can be the parent/child of another

Map, V3

Goal : Given a Tree, t, and a one argument function, f, mutate the tree by applying f to each label.

Pruning

Goal : Given a Tree, t, and a value x, remove each branch with label equal to x