Warning

This book is new. If you'd like to go through it, then join the Learn Code Forum to get help while you attempt it. I'm also looking for feedback on the difficulty of the projects. If you don't like public forums, then email help@learncodethehardway.org to talk privately.

Exercise 14: Double Linked Lists

The previous exercise may have taken you quite a while to complete since you have to figure out how to make a single linked list work. Hopefully, the video gave you enough information to complete the exercise and also showed you exactly how to do an audit of your code. In this exercise you're going to implement the better version of linked lists called DoubleLinkedList.

In the SingleLinkedList you should have realized that any operation involving the end of the list has to travel through each node until it gets to the end. A SingleLinkedList is only efficient from the front of the list where you can easily change the next pointer. The shift and unshift operations are fast, but pop and push cost you as the list gets bigger. You might be able to speed this up by keeping a reference to the next-to-last element, but then what if you want to replace that element? Again, you'll have to go through all of the elements to find this one. You can get some speed improvements with a few minor changes like this, but a better solution is to simply change the structure to make it easier to work from any position.

The DoubleLinkedList is nearly the same as the SingleLinkedList except it also has a prev (for previous) link to the DoubleLinkedListNode that comes before it. One extra pointer per node and suddenly many of the operations become much easier. You can also easily add a pointer to the end in the DoubleLinkedList so you have direct access to both the beginning and the end. This makes push and pop efficient again since you can access the end directly and use the node.prev pointer to get the previous node.

With these changes in mind our node class looks like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class DoubleLinkedListNode(object):

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

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

All that's added is the self.prev = prev line and then handling that in the __repr__ function. Implementing the DoubleLinkedList class uses the same operations as the SingleLinkedList class, except you add one more variable for the end of the list:

1
2
3
4
5
class DoubleLinkedList(object):

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

Introducing Invariant Conditions

All of the operations to implement are the same, but now we have some additional considerations:

 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
    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):
        """Actually just another name for push."""

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

    def detach_node(self, node):
        """You'll need to use this operation sometimes, but mostly 
        inside remove().  It should take a node, and detach it from
        the list, whether the node is at the front, end, or in the middle."""

    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."""

With a prev pointer you now have to handle more conditions in each operation:

  1. Are there zero elements? Then self.begin and self.end need to be None.
  2. If there is one element, then self.begin and self.end have to be equal (point at same node).
  3. The first element must always have a prev that is None.
  4. The last element must always have a next that is None.

These truths have to hold during the life of the DoubleLinkedList, which makes them "invariant conditions" or just "invariants". The idea of an invariant is that, no matter what, these are base checks that show the structure is working correctly. A way to look at invariants is any tests or assert calls you seem to do repeatedly can be moved into a special function called _invariant which does these checks. You can then call this function in your tests or at the beginning and end of each function. Doing that will cut down on your defect rates since you are saying, "No matter what I do, these have to be true."

The only problem with invariant checks is they can cost time to run. If every function call also calls another function twice then you are adding a potentially significant burden to every function. If your invariant function also does something costly it gets worse. Imagine if you added the invariant: "All nodes have a next and prev except the first and last ones." That would mean every function call does a complete traversal through the list twice. When you have to make sure the class works all the time, this is worth it. If you don't, then it becomes a problem.

In this book you'll use invariant functions when you can, but keep in mind that they aren't something you always need to use. Finding ways to only activate them in test suites or debugging or using them during initial development is the key to using them effectively. I recommend that you only call invariants at the top of functions or only call them inside the test suite. This is a good compromise.

Exercise Challenge

In this exercise you'll implement the operations for the DoubleLinkedList, but this time you'll also use an _invariant function to check that it is working correctly before and after each operation. The best way to do this is to call the invariant at the top of each function and then in the test suite at key spots. Your test suite for the DoubleLinkedList is almost a copy-paste replica of the SingleLinkedList test, except you are adding _invariant calls at key points.

As with the SingleLinkedList you'll want to manually study this data structure on your own. You should draw out the node structures on paper and do some of the operations manually. Next, work the DoubleLinkedListNode manually in your dllist.py file. After that spend one or two 45-minute sessions trying to hack up a few operations to figure it out. I recommend push and pop. After that you can watch the video to see me work on it and how I use a combination of auditing my code and the _invariant function to check what I'm doing.

Study Drills

As with the previous exercise you'll want to implement this data structure again from memory. Put what you know about it in one room and your laptop in another room. You'll want to do this until you can implement the DoubleLinkedList from memory without reference.

Pre-order Learn More Python The Hard Way

When you pre-order Learn More Python The Hard Way, you'll receive the Python 3 Edition as it's being created. All files are DRM free and you can download them to your computer for offline viewing. Digital Download Only! You do not get a physical book.

$29.00

Buy the Online Course

Or, you can read Learn More Python the Hard Way for free right here, video lectures not included.

Other Buying Options

Other buying options coming soon.

No content available for this exercise. You can view all available downloads at your customer account page.