Week 8 -- Linked List Structures

Hello again, friends. :)

This week we did a lot of Linked List stuff again to help us understand and/or improve our understanding of linked lists. This makes me feel like linked lists are going to be on the exam definitely so self note right here to go back and study the heck out of it.

So there are technically two ways of thinking of linked lists. One way is to think of each of the items of the list that's closer to the front to wrap the next value that follows it until it has nothing to wrap any more. Literally think of a piece of candy with a billion wrappers around it, with the outermost wrapper being the first element of the linked list until it reaches the candy which indicates the end of the list (OM NOM NOM). The other way is to think of each node linking to the next one until it reaches an empty node like we've been doing since last week.

Speaking of wrappers, I have to write down what a wrapper class is. I keep on forgetting what it actually does (ugh!). A wrapper class is just something to keep track of information of the entire structure (as in make sense and link together the information provided by the class that encapsulates). For example, for a linked list, it keeps track of the position of the front of the list to make it easier to prepend to that position, as well as the size of the list (which makes counting the number of nodes a lot easier). It should also be where the functions go.

Now let's talk about the functions that can go into the Linked List wrapper class. Insertion is pretty straight forward, you literally just stitch together the old list onto the new node that you'd like the prepend. Reversing, though is a little bit confusing.

What the reversing function does is recurse the list until the very last node. Then it makes a new list and turns the very last node into the very first node and comes back out to the second last node. It then makes the new first node point to the old second last node, making it the second node of the new list. It does this by using the previous rest of the list be thing that the first node points to, then cutting off the rest of the list minus the old second last node by making that point to none, which makes the old second last node into the back of the list. It does this over and over again until it's up until the very first item of the list, in which case the very first item will point to None because there won't be another iteration of the code to allow it to point of the list. This will then be the new end of list.

Here's my ugly drawing masterpiece worthy of envy from even the great Picasso himself depicting the reverse process:

SEE YOU GUYS NEXT WEEK!