Description

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

1. A "node", which is usually a container or memory location for the data structure. Your values go in here.
2. An "edge", but we'll say "pointer" or "link", that points at other nodes. These are placed inside each node, usually as instance variables.
3. 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:

1. Nodes are just objects defined by a class.
2. Pointers (edges) are just instance variables in the node objects.
3. 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:

1. 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.
2. 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.
3. 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.

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

1
2
3
4
5
6
7
8
9

class SingleLinkedListNode(object):

    def __init__(self, value, nxt):
        self.value = value
        self.next = nxt

    def __repr__(self):
        nval = self.next and self.next.value or None
        return f"[{self.value}:{repr(nval)}]"

We have to use the word nxt since next is a reserved word in Python. Other than that this is a very simple class. The most complicated thing is the __repr__ function. That just prints debugging output when you use the "%r" format, or when you call repr() on the node. It should return a string.

Controller

Once we have our nodes defined in the SingleLinkedListNode class we can figure out exactly what the controller should do. Every data structure has a list of common operations you'd need for them to be useful. Different operations take different amounts of memory (space) and time, with some being expensive and others being fast. The structure of the SingleLinkedListNode makes some operations very quick but many others very slow. You'll be figuring this out as you work on the implementation.

The easiest way to see the operations is to look at a skeleton version of the SingleLinkedList class:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class SingleLinkedList(object):

    def __init__(self):
        self.begin = None
        self.end = None

    def push(self, obj):
        """Appends a new value on the end of the list."""

    def pop(self):
        """Removes the last item and returns it."""

    def shift(self, obj):
        """Another name for push."""

    def unshift(self):
        """Removes the first item and returns it."""

    def remove(self, obj):
        """Finds a matching item and removes it from the list."""

    def first(self):
        """Returns a *reference* to the first item, does not remove."""

    def last(self):
        """Returns a reference to the last item, does not remove."""

    def count(self):
        """Counts the number of elements in the list."""

    def get(self, index):
        """Get the value at index."""

    def dump(self, mark):
        """Debugging function that dumps the contents of the list."""

In other exercises I'll only tell you the operations and leave it for you to figure out, but for this one I'm giving you guidance on implementation. Look through the list of functions in SingleLinkedList to see each operation and the comment for how it should work.

Test

I am now going to give you the test that you have to make work when implementing this class. You'll see that I've gone through every operation and tried to cover most of the edge cases, but when I do the audit you'll find out that actually I may have missed a few. It's common that people don't test for cases such as "zero elements" and "one element".

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

from sllist import *

def test_push():
    colors = SingleLinkedList()
    colors.push("Pthalo Blue")
    assert colors.count() == 1
    colors.push("Ultramarine Blue")
    assert colors.count() == 2

def test_pop():
    colors = SingleLinkedList()
    colors.push("Magenta")
    colors.push("Alizarin")
    assert colors.pop() == "Alizarin"
    assert colors.pop() == "Magenta"
    assert colors.pop() == None

def test_unshift():
    colors = SingleLinkedList()
    colors.push("Viridian")
    colors.push("Sap Green")
    colors.push("Van Dyke")
    assert colors.unshift() == "Viridian"
    assert colors.unshift() == "Sap Green"
    assert colors.unshift() == "Van Dyke"
    assert colors.unshift() == None

def test_shift():
    colors = SingleLinkedList()
    colors.shift("Cadmium Orange")
    assert colors.count() == 1

    colors.shift("Carbazole Violet")
    assert colors.count() == 2

    assert colors.pop() == "Cadmium Orange"
    assert colors.count() == 1
    assert colors.pop() == "Carbazole Violet"
    assert colors.count() == 0

def test_remove():
    colors = SingleLinkedList()
    colors.push("Cobalt")
    colors.push("Zinc White")
    colors.push("Nickle Yellow")
    colors.push("Perinone")
    assert colors.remove("Cobalt") == 0
    colors.dump("before perinone")
    assert colors.remove("Perinone") == 2
    colors.dump("after perinone")
    assert colors.remove("Nickle Yellow") == 1
    assert colors.remove("Zinc White") == 0

def test_first():
    colors = SingleLinkedList()
    colors.push("Cadmium Red Light")
    assert colors.first() == "Cadmium Red Light"
    colors.push("Hansa Yellow")
    assert colors.first() == "Cadmium Red Light"
    colors.shift("Pthalo Green")
    assert colors.first() == "Pthalo Green"

def test_last():
    colors = SingleLinkedList()
    colors.push("Cadmium Red Light")
    assert colors.last() == "Cadmium Red Light"
    colors.push("Hansa Yellow")
    assert colors.last() == "Hansa Yellow"
    colors.shift("Pthalo Green")
    assert colors.last() == "Hansa Yellow"

def test_get():
    colors = SingleLinkedList()
    colors.push("Vermillion")
    assert colors.get(0) == "Vermillion"
    colors.push("Sap Green")
    assert colors.get(0) == "Vermillion"
    assert colors.get(1) == "Sap Green"
    colors.push("Cadmium Yellow Light")
    assert colors.get(0) == "Vermillion"
    assert colors.get(1) == "Sap Green"
    assert colors.get(2) == "Cadmium Yellow Light"
    assert colors.pop() == "Cadmium Yellow Light"
    assert colors.get(0) == "Vermillion"
    assert colors.get(1) == "Sap Green"
    assert colors.get(2) == None
    colors.pop()
    assert colors.get(0) == "Vermillion"
    colors.pop()
    assert colors.get(0) == None

Study this test carefully so that you have a good idea of how each operation should work before trying to implement it. I wouldn't write all of this code into a file at once. Instead it's better to do just one test at a time and make it work in small chunks.

Introductory Auditing

As you make each test run you will conduct an audit of your code to find defects. Eventually you will track the number of defects you find with your audits, but for now you're going to just practice auditing code after you write it. An "audit" is similar to what a tax agent does when the government thinks you are cheating on your taxes. They go through each transaction, each amount of money coming in, all money going out, and why you spent it the way you did. A code audit is similar as you go through each function, and analyze all parameters coming in, and all values going out.

To conduct a basic audit you will do this:

1. Start at the top of your test case. Let's do test_push in this example.
2. Look at the first code line and determine what is being called and what is being created. In this case it's colors = SingleLinkeList(). That means we are creating a colors variable, and calling the SingleLinkeList.__init__ function.
3. Jump to the top of this __init__ function, keeping your test case and the target function (__init__) side-by-side. Confirm that you have done so. You then confirm that you called it with the correct number and type of function arguments. In this case __init__ only takes self, and it should be the right type.
4. You then go into __init__ and go line-by-line, confirming each function call and variable in the same way. Does it have the right number of arguments? The right types?
5. At each branch (if-statement, for-loop, while-loop) you confirm that the logic is correct and that it handles any possible conditions in the logic. Do if-statements have else clauses with errors? Do while loops end? Then dive into each branch and track the functions the same way, diving in, checking variables, and coming back, checking returns.
6. When you get to the end of a function or any return, you jump back to the test_push caller to check that what is returned matches what you expect when you called it. Remember, though, that you do this for each call in __ini__ as well.
7. Finally you are done when you reach the end of the test_push function and you've done this recursive checking into and out of each function it calls.

This process seems tedious at first, and yes it is, but you'll get quicker at it the more often you do it. In the video you'll see me do this before I run each test (or at least I try really hard to do it). I follow a process of:

1. Write some test code.
2. Write the code to make the test work.
3. Audit both.
4. Run the test to see if I was right.

Exercise Challenge

We now reach the part where you're ready to try this. First, read through the test and study what it does, and study the code in sllist.py to figure out what you need to do. I suggest that when you attempt to implement a function in SingleLinkeList you first write the comments describing what it does, then fill in the Python code to make those comments work. You'll see me do this in the video.

When you have spent one or two 45-minute sessions hacking on this and trying to make it work, it's time to watch the video. You'll want to attempt it first so that you have a better idea of what I'm trying to do, which makes the video easier to understand. The video will be me just coding and not talking, but I'll do a voice-over to discuss what's going on. The video will also be faster to save time, and I'll edit out any boring mistakes or wasted time.

Once you see how I do it, and you've taken notes (right?), then go and attempt your more serious tries and perform the code auditing process as carefully as you can.

Auditing

Once you have written your code, make sure you do the auditing process I describe in Part III. I will also be doing it in the video for this exercise if you aren't quite sure how it's done.

Study Drills

Your study drill for this exercise is to try to implement this algorithm again, completely from memory the way I describe in the introduction to Part III. You should also try to think through what operations in this data structure are most likely painfully slow. When you are done, perform your auditing process on what you created.