Week #9: Linked Lists

Week #8 was about Linked Lists.

What is a Linked List?

A Linked List structure consists of nodes that have a value (object) and a reference to another object, therefore another node. When initializing a Linked List Node you pass the value as a parameter and have a default parameter for the reference, set to None.  Here is a more visual representation of the Linked List :

Linked Lists can be described as recursive structures because every node refers to a linked list.

But sometimes it is easier to approach this structure as one train of links. For this approach we implement the class Linked Lists as a "wrapper" representing the structure as a whole. We create variables to keep track of the front (head) and the back (tail) links as well as the size of the whole list. This is the approach we took when working on Lab 07.

One basic concept that we need to understand is how to traverse all the items in the Linked List. This bit of code is very useful for many functions that are used to manipulate the structure.

When traversing all the items, we need to call on the first node (front/head) and use the default parameter for the Linked List Node, nxt, that will return the next link. The python code (taken from class notes) is as follows:

cur_node = self.front

while <some condition here>:

     # do something here.....

     cur_node = cur_node.nxt

This code is only a basis that helps implement functions such as _contains_ or _get_item_. Knowing how to traverse the tree allows you to manipulate links and search for links as well.