Exercise 13: Single Linked Lists

The first data structure you will implement is the Single Linked List. I will describe the data structure, list out all the operations you should implement, and give you a single test for your implementation that needs to pass. You should attempt this data structure on your own at first but then watch the video of my implementation and the audit after so you can understand the process.

WARNING: These are not efficiently implemented data structures at all! They are purposefully naive and slow so that we can cover measuring and optimizing data code in Exercises 18 and 19. If you are attempting to use these data structures in professional work, then you will have performance problems.

Description

When dealing with many data structures in an object-oriented language such as Python, you have three common concepts to understand:

• A "node", which is usually a container or memory location for the data structure. Your values go in here.

• An "edge", but we'll say "pointer" or "link", that points at other nodes. These are placed inside each node, usually as instance variables.

• A "controller", which is some class that knows how to use the pointers in a node to structure the data correctly.

In Python we will map these concepts like this:

• Nodes are just objects defined by a class.

• Pointers (edges) are just instance variables in the node objects.

• The Controller is simply another class that uses the nodes to store everything and structure the data. This is where all of your operations go (push, pop, list, etc.), and usually the user of the controller never really deals with the Nodes or pointers.

In some books on algorithms you'll see implementations that combine the node and controller into one single class or structure, but this is very confusing and also violates separation of concerns in your design. It's better to separate the nodes from the controlling class so that one thing does one thing well and you know where the bugs are.

Imagine we want to store a list of cars in order. We have a first car, which leads to a second, and so on until the end. Imagining this list we can begin to conceive of a node/pointers/controller design for it:

• Nodes contain each car's description. Maybe it's just a node.value variable to a Car class. We can call this SingleLinkedListNode or SLLNode if you're lazy.

• Each SLLNode then has a next link to the next node in the chain. Doing node.next gets you the next car in the line.

• A Controller simply called SingleLinkedList then has operations like push, pop, first, or count, which take a Car and uses nodes to store them internally. When you push a car onto the SingleLinkedList controller, it works an internal list of linked nodes to store it at the end.

NOTE: Why would we do this when Python has a perfectly good and very fast list type? Mostly to learn about data structures is all. In the real world you would just use Python's list and move on.

To implement this SingleLinkedListNode we'd need a simple class like this: