Week Eight - LinkedList

Week Eight - LinkedList

We have been talking about linked list in the past two weeks of class. Two ways of implementing linked list is discussed and they both have a recursive structure. In the first way of implementing linked list, it contains a head (called item in the lab) and a rest. A head is a object (a value) and head is "linked" to rest which is either another linked list or None. The "rest" part makes this class a recursive structure, and we need to write some of the functions using recursion. I personally find this way of implement a bit confusing, it took me some time to fully understand this class and write functions for it. (recursion is required in some functions, which makes it harder and less straightforward to implement.) However, this data structure does have some advantages: i.e. in the lab we did last week, we re-implemented the Queue class using this structure, and some functions in Queue implemented this way turns out to be more effective than implementing using the list Object.

The second way of implementing Linked List is to use nodes, each nodes has a value and the reference to another node or None. This way of implementing is a way of using a wrapper class. I am still a bit confused about the structure of linked list this way. In my opinion, I think the class implemented in such a way that it is using the class LListNode to store all the informations. One thing I really like about this implement is that it keeps track of the size of the list. So, instead of writing a method and call it to compute the size, the size is automatically recorded, which save a lot work than compute it every time.

I found the lab this week is easier than last week, probably due to the fact that I am more familiar with LinkedList now. When I finished the lab this week I was able to go back and rework on the lab last week.