Week 8: Linkedlists and More Trees

This week focused on the dualism of linked lists, which can be regarded as both a nested set of lists and also as chain of nodes that refer to the next. 

The former type of linked list is of the sort I was already familiar with - it is not too different after all, from a list with only two elements.  The latter of type list was a novel concept.  Linked lists are chains of nodes which contains two pieces of information - a value and a reference to the next node in the chain.  This way of looking at linked lists is useful as it allows the nodes to be treated as disparate elements that can be added or removed as needed.  But all good things come with caveats, it seems, because there is no way of telling where the linked list begins - without a wrapper class that is.  A wrapper class denotes the starting node of the linked list, as well as some other details such as size.

During the lab this week, I realized, upon being prompted by a question, that linked lists are a remarkably efficient way to emulate queues. Creating 3 mutable linked lists, one which refers to all items, one which refers to the front of the queue, and one which refers to the back of the queue, allow the queue's prepend and decapitate options to have constant run time.  The trick to working with linked list methods, I realized, involves using recursion and decreasing the index that you are working with each time (as the passed argument falls in size).