Week8: Linked List Data Stucture

   
    In these two weeks lecture, we learned another data structure, linked list. Linked lists are made up of nodes, where each node contains a object and a reference to a linked list. So, linked list is a recursive definition. It is either empty or a node that contains an object and a reference of another linked list. Also if the reference is itself, we make a infinite list.
    We use linked list to implement some abstract data types. In theses two weeks' labs, We implement the ADT queue and stack using linked list instead of using Python built-in type list weeks ago. We found it hard to implement queue's 'enqueue' and 'dequeue' method without methods similar in list. The basic approach to the problem is to store two attributes: a reference to where you add new linked list elements, and a reference to where you remove the oldest linked list element. Stack is easier to implement because its methods, push and pop, deal with the very last item.
    Linked list methods. List have a lot of methods. So we can write these methods in class LinkedList. Recursion is greatly used in writing these methods to deal with indexes. Also in this process, I learned some equivalent ways to call these method. __contains__, __len__, __getitem__, __setitem__, __delitem__ have equivalent ways to call them in Python. See lab handout for more details. In addition to that, when I talked to TA, we know the methods 'prepend' and 'decapitate' have a problem that when we implement them, a piece of memories become 'garbage' without reference to it. For example, if we implement decapitate on a linked list, the rest becomes the new head and the rest.rest becomes the new rest. But the problem is that the previous head becomes 'garbage'. When I google it, I found they are called 'garbage collection' which has both advantages and disadvantages.

    Some useful reading materials:    http://openbookproject.net/thinkcs/python/english3e/linked_lists.html
http://en.wikipedia.org/wiki/Linked_list
http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)