Week 7: Recursion, Linked List, and Copy

I realized that I've already written the recursion topic on week 4, so I will write mainly on linked list this week.



This week we learned about linked lists, it is actually not an entirely new topic, it is a kind of tree.
A linked list contains a node and a pointer that links to the next linked list. The 'head' of the linked list is just called 'head', while the other linked lists behind it is called 'rest'. The end of the linked list is a special/empty node, which doesn't contain anything.

The class linked list contains a method called prepend, which add new object to the front . Below is the prof's slide with more detail describing how to write the function plus some of my notes:

based on the description above, we need to assign new values to the variables, the method should be something like:

def prepend(self, head):

    self.head, self.rest, self.empty = head, copy(self), False

A benefit of using a linked lists is that if we want to add or remove a value, we don't need to reorganized the entire lists. For example, assume a list L = [1, 2, 3, 4], which L[0] = 1, L[1] = 2 and so on. If we want to add '0' to the front of the list, we need to move the entire list one index back. So the list L= [0, 1, 2, 3, 4] and L[0] = [0], L[1] = 1...etc. Imagine the list is long, it will requires a lot more time to put an object at the front. In this case, a linked lists is a good choice, since the items don't need to be stored continuously. 

To see it more clearly, check out this paragraph I found that talks about linked lists.

------------------------------------------------------------

I've also looked up the difference between deep copy and shallow copy.

The shallow copy copies a new object with a different id, but not the 'detail' inside the object.

The deep copy copies copies everything.

Example:

a  = [1, 2, 3]

c = ['x', 'y']

- normal assignment statement:

d = c      

id(c) == id(d)               True

id(c[0]) == id(c[0])      True

(d = ['x', 'y'] has the same id as c)

- shallow copy:

d = c

id(c) == id(d)               False, d is a new list with id different from c now.

id(c[0]) == id(c[0])      True, d[0] has the same id as c[0]

- deep copy:

d = c

id(c) == id(d)               False, d is a new list with id different from c now.

id(c[0]) == id(c[0])      False, d[0] has id different from c[0] now.

a good explanation (graph) for difference between deep copy and shallow copy.