csc148: Slog Week 8: Impression of week 7: Linked list and Tree Traversal

Impression of week 7: Linked list and Tree Traversal

There are two different ways of thinking linked list structure:

1) as list made up of an item(value) and a sub-list(rest)

2) as objects(nodes) with a value and a reference to other similar objects

The second concept is used most in lecture. When the class LinkedList is initialized, it has front (first item in the list), back (last item in the list) and size (length or total number of items in the list).

Most of the time when implementing methods of this class we need to walk through the list, this is how we can do it:

Make a reference to (at least one) node, and move it along the list:

cur_node = self.front

while <some conditions>:

do something

cur_node = cur_node.nxt

So each time we move from one node to the next, we change the object that the cur_node’s reference. If we want to implement a method that will do something with one of the node in the list, we can write a condition that fits all the nodes in the list except the one we want to do something with it. So the while loop condition will be met and the cur_node will keep referring the next node until the node we want is found. When this happens, the while loop condition will not be met and the function will stop walking through the list, then we can have some code on what we want to do with that node out of the while loop.

At the time the function is walking through a list, the class LLNode is also used.

It has two variables: nxt (next node, None if at the end of the list) and value (data of the current node)

With this concept, we can implement different method with these two classes.

On the other hand, the different orders of traversing tree are introduced with recursive definition.

Pre-order: F, B, A, D, C, E, G, I, H