Linked Lists

        These two weeks focus on linked list, a recursive date structure, which is consisted of nodes and each node have a reference to the next.

        From the picture below, we can see the linked list has two parts: head, the first element of the liked list and rest, another LinkedList that has the same structure. N the class LinkedList, we need to check whether head or rest is None. If both of heaf and rest are None, the self is empty. If not, we give the value of head to self.head. Then we assign the rest is an empty LinkedList if the rest is None; otherwise, we put self.rest = rest. In addition, method prepend is for adding new item to the front of its self and ,ethod decapitate is for deleting item from self by using del. The method __getitem__ clearly shows the recursion. Using ind = ind – 1 to get the item by going deep into the rest.

       The importance of this type list is collection. For instance, the first node in the list can refer to the whole list.