Week 8: More Linked Structures

This week we went over more linked structures (and hence, more opportunities to use recursion), specifically linked lists and binary trees. These ADTs made sense to me, and were somewhat similar to regular trees. The idea of wrapper classes and the difference between __str__ and __repr__ methods was also discussed. A linked list has a node (with a value) which points to another object (another linked list, until the end, where the value is None), and we made a wrapper class to keep track of the size and the front of the list. As seen in last weeks lab, adopting these ADTs and wrapper classes can be used to cut down on runtime and make programs more organized.

A binary tree (and the binary search tree wrapper class) is a tree with only two children, so the children are represented as left and right. In this instance, a __str__ method that is different from __repr__ is useful for the programmer to visualize the structure. I think I'll do a similar thing for the second part of the second assignment. A traversal was used for the _str method, and recursion for the _insert method. Binary trees are another way which runtime can be reduced.

I was pleased with my result on the term test, and I finished and understand the first part of the assignment. I've already done some code for the next part.

A graphic of a linked list

http://www.cs.usfca.edu/~srollins/courses/cs112-f07/web/notes/linkedlists/ll2.gif