Week 9: Impression Of Week 8

        This week we learn a new data structure ---- LinkList. A linked list is a linear sequence of nodes, where each node contains a reference to the next node in the list. When I first saw it, it just likes a single branch of a tree. However, there are still some between them. For example, an empty list is an instance of the class, with attribute values set to show it’s empty. Compared to binary tree implementation, an empty tree is represented as None. In BTnode, we have no wrapper class, while LinkList is a wrapper class of LLNode, which represents a single node.

l   LLNode & LinkList

    Different from BTnode, LLnode has a wrapper class, which named LinkList. At first, I cannot figure out what is wrapper class and what it used for. I don’t know why we put these two distinct classes into a same module. However, after doing the lab exercise and looking through the link professor gave us. This concept makes sense to me. LLNode, which represents a single node, is the basic object or element for LinkList. In other words, LinkList is the collection of organized LLNode. Similar to its structure name ---- wrapper class, LinkList "wraps" or "encapsulates" the functionality of LLnode. LLnode “wrapped” as value for LinkList, and they both track through the whole list implementation.

In LLnode, we initialize these 2 parameters:

1)   self.value: It demonstrates the data given to the node.

2)   self.nxt: It demonstrates the node next to this node in the linked list.

       (It plays an important role when we modify the LinkList structure.)

In LLnode, we initialize these 3 parameters:

1)   self.front: We initially set up it as None. It refers to the first linked list node after we add Linked list nodes into the linked list.

2)   self.back: We initially set up it as None. It refers to the last linked list node after we add Linked list nodes into the linked list.

3)   self.size = It represents the number of linked list nodes in the list(cannot be nagetive). We initially set up it as 0. It increases as we add linked list nodes into the list, and decreases as we remove linked list nodes out of the list.

l   Traversing a linked list

Compared to traversing the tree, it seems more easier for me to traverse the linked list.

  

* Just follow these pattern:

current = self.front

while <some condition holds>:

<Do something with the current node.>   

current = current.nxt       # Advance to the next node.

l   A challenge: Mutating a linked structure

Because the biggest advantage for LinkList is to insert or remove easily items without interrupting the other data in the list, it is crucial for us to master how to mutate this structure. However, when I do the exercise, I encountered the same problem as Adam Fong (http://1001516978.blogspot.ca). LinkList involves lots of variables (current_node, pre_node, head, tail, etc.), which confused me before I totally understand this. As a result, I was easy to lose track of the list. When I put them into while loop, it always produced none or infinite loop error. Afterwards, I found drawing a picture helps a lot. It stimulates me to think structurally and clearly. When the list showed as a diagram, I know how it runs and what I should do next. Just like the picture below:

         After this week’s learning, I learn a brand new concept: wrapper class and its applications. What’s more, I realized the importance of drawing a diagram. Nevertheless, I am still not quite capable of trace linked list quickly and precisely. I think I can improve this with more practice.