Linked Lists (and some wrappers and helpers insight...)

A linked list is a particular recursive data structure made up of nodes where each node contains some data and a reference to the next node in the linked list.

We can distinguish the head from the rest in a linked list. The head is the first element in this structure and the rest is simply the remaining elements of it.

This is what a linked list looks like:

There’s two important things that we should consider when dealing with linked lists:

-The reason why separating the head from the rest is so useful is because the head has a reference to the first node in the rest. So the head is indirectly connected to every element in the list. We can define methods that traverse the full length of the linked list by calling them on the head.

-When we create a new node, if we don’t define its next value, this will be set to None by default. So the last element in every linked list has always a reference to None.

This week, we have also learned that, in order to define methods in a given class, we can use wrapper methods that will inherit helper methods from another class during their implementation.

For example, we have seen how we can create two separate classes for nodes and linked lists. This will allow us to implement the insert method for linked lists (inserting new nodes at the head of the linked list) by using the references that nodes have to next nodes (defined in the node class). We would have to say that the new node has a reference to the current head of the linked list.

We can also use this approach in binary search trees. In this case, we would define an insert method in the node class to determine where should a new node be created according to a specific data (left or right?) depending on the data of another node. When we inherit this method in the binary search tree class it will automatically place new nodes in their corresponding location.

Recursion

Recursion is definitely the most important concept that we have seen so far in this course. This feature allows us to implement a function by calling the function in its own implementation. But how is this possible? Well, it's as simple (and as complex) as including some code within the implementation of our function that will indicate the program how to work on some base case, so the recursive step will be executed by means of the base case with the indications that we will give to the code. This might sound a bit confusing, so let's define an example and trace it to see how recursion works.

In class, we've seen the function rec_max(L) which returns the maximum number in a possibly nested list of numbers. This is what it looks like:

As we can see, we are using rec_max() inside the function implementation. This is the recursive step. The base case is the bit of code following the 'else' statement. This tells our program to return the biggest element of a non-nested list considering every element in the list. So, our computer now knows that rec_max() works the same way, but only if the element of the list is a nested list. So if an element in L is a nested list, we will get its maximum separately by using the recursive step.
We will get a non nested list with the maximum of every nested list in L and the maximum of the non nested part of L. Finally, the function will return the maximum of this list comprehension.
And this is how recursion works!

As we can see, we could also implement rec_max() without using recursion by considering every element in L separately using if statements and for loops. But this will make our code much longer and slower. This is why, I can say with confidence that, we should always use recursion when it's possible.