🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of DanielNoord

DanielNoord's solution

to Simple Linked List in the Python Track

Published at Sep 21 2020 · 0 comments
Test suite

Write a simple linked list implementation that uses Elements and a List.

The linked list is a fundamental data structure in computer science, often used in the implementation of other data structures. They're pervasive in functional programming languages, such as Clojure, Erlang, or Haskell, but far less common in imperative languages such as Ruby or Python.

The simplest kind of linked list is a singly linked list. Each element in the list contains data and a "next" field pointing to the next element in the list of elements.

This variant of linked lists is often used to represent sequences or push-down stacks (also called a LIFO stack; Last In, First Out).

As a first take, lets create a singly linked list to contain the range (1..10), and provide functions to reverse a linked list and convert to and from arrays.

When implementing this in a language with built-in linked lists, implement your own abstract data type.


To support list(), see implementing an iterator for a class.

Additionally, note that Python2's next() has been replaced by __next__() in Python3. For dual compatibility, next() can be implemented as:

def next(self):
    return self.__next__()

Exception messages

Sometimes it is necessary to raise an exception. When you do this, you should include a meaningful error message to indicate what the source of the error is. This makes your code more readable and helps significantly with debugging. Not every exercise will require you to raise an exception, but for those that do, the tests will only pass if you include a message.

To raise a message with an exception, just write it as an argument to the exception type. For example, instead of raise Exception, you should write:

raise Exception("Meaningful message indicating the source of the error")

Running the tests

To run the tests, run pytest simple_linked_list_test.py

Alternatively, you can tell Python to run the pytest module: python -m pytest simple_linked_list_test.py

Common pytest options

  • -v : enable verbose output
  • -x : stop running tests on first failure
  • --ff : run failures from previous test before running other test cases

For other options, see python -m pytest -h

Submitting Exercises

Note that, when trying to submit an exercise, make sure the solution is in the $EXERCISM_WORKSPACE/python/simple-linked-list directory.

You can find your Exercism workspace by running exercism debug and looking for the line that starts with Workspace.

For more detailed information about running tests, code style and linting, please see Running the Tests.


Inspired by 'Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby', singly linked-lists. http://www.brpreiss.com/books/opus8/html/page96.html#SECTION004300000000000000000

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.


import unittest

from simple_linked_list import LinkedList, EmptyListException

# No canonical data available for this exercise

class SimpleLinkedListTest(unittest.TestCase):
    def test_empty_list_has_len_zero(self):
        sut = LinkedList()
        self.assertEqual(len(sut), 0)

    def test_singleton_list_has_len_one(self):
        sut = LinkedList([1])
        self.assertEqual(len(sut), 1)

    def test_non_empty_list_has_correct_len(self):
        sut = LinkedList([1, 2, 3])
        self.assertEqual(len(sut), 3)

    def test_error_on_empty_list_head(self):
        sut = LinkedList()
        with self.assertRaisesWithMessage(EmptyListException):

    def test_singleton_list_has_head(self):
        sut = LinkedList([1])
        self.assertEqual(sut.head().value(), 1)

    def test_non_empty_list_has_correct_head(self):
        sut = LinkedList([1, 2])
        self.assertEqual(sut.head().value(), 2)

    def test_can_push_to_non_empty_list(self):
        sut = LinkedList([1, 2, 3])
        self.assertEqual(len(sut), 4)

    def test_pushing_to_empty_list_changes_head(self):
        sut = LinkedList()
        self.assertEqual(len(sut), 1)
        self.assertEqual(sut.head().value(), 5)

    def test_can_pop_from_non_empty_list(self):
        sut = LinkedList([3, 4, 5])
        self.assertEqual(sut.pop(), 5)
        self.assertEqual(len(sut), 2)
        self.assertEqual(sut.head().value(), 4)

    def test_pop_from_singleton_list_removes_head(self):
        sut = LinkedList([1])
        self.assertEqual(sut.pop(), 1)
        with self.assertRaisesWithMessage(EmptyListException):

    def test_error_on_empty_list_pop(self):
        sut = LinkedList()
        with self.assertRaisesWithMessage(EmptyListException):

    def test_push_and_pop(self):
        sut = LinkedList([1, 2])
        self.assertEqual(len(sut), 3)
        self.assertEqual(sut.pop(), 3)
        self.assertEqual(sut.pop(), 2)
        self.assertEqual(sut.pop(), 1)
        self.assertEqual(len(sut), 0)
        self.assertEqual(len(sut), 1)
        self.assertEqual(sut.head().value(), 4)

    def test_singleton_list_head_has_no_next(self):
        sut = LinkedList([1])

    def test_non_empty_list_traverse(self):
        sut = LinkedList(range(10))
        current = sut.head()
        for i in range(10):
            self.assertEqual(current.value(), 9 - i)
            current = current.next()

    def test_empty_linked_list_to_list_is_empty(self):
        sut = LinkedList()
        self.assertEqual(list(sut), [])

    def test_singleton_linked_list_to_list_list_with_singular_element(self):
        sut = LinkedList([1])
        self.assertEqual(list(sut), [1])

    def test_non_empty_linked_list_to_list_is_list_with_all_elements(self):
        sut = LinkedList([1, 2, 3])
        self.assertEqual(list(sut), [3, 2, 1])

    def test_reversed_empty_list_is_empty_list(self):
        sut = LinkedList([])
        self.assertEqual(list(sut.reversed()), [])

    def test_reversed_singleton_list_is_same_list(self):
        sut = LinkedList([1])
        self.assertEqual(list(sut.reversed()), [1])

    def test_reverse_non_empty_list(self):
        sut = LinkedList([1, 2, 3])
        self.assertEqual(list(sut.reversed()), [1, 2, 3])

    # Utility functions
    def assertRaisesWithMessage(self, exception):
        return self.assertRaisesRegex(exception, r".+")

if __name__ == '__main__':
class Node:
    def __init__(self, value, previous=None):
        self.own_value = value
        self.prev_node = previous

    def value(self):
        return self.own_value

    def next(self):
        return self.prev_node

class LinkedList:
    def __init__(self, values=[]):
        self.header = None
        self.length = 0
        for value in values:

    def __len__(self):
        return self.length

    def __iter__(self):
        self.index = self.header
        return self

    def __next__(self):
        if self.index is None:
            raise StopIteration
        ret = self.index.value()
        self.index = self.index.prev_node
        return ret

    def head(self):
        if self.header:
            return self.header
            raise EmptyListException("The list is empty!")

    def push(self, value):
        self.header = Node(value, self.header)
        self.length += 1

    def pop(self):
            ret = self.head().value()
            self.header = self.header.prev_node
            self.length -= 1
            return ret
        except ValueError:
            raise EmptyListException("List is empty!")

    def reversed(self):
        return list(self)[::-1]

class EmptyListException(Exception):

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?