Kotlin Spring Data Delegation

Kotlin provides many features that can be really useful when working with Spring. I was doing a website for my fiancee where I found an excellent use case of Kotlin’s Delegation and Extension function that I am going to share with readers today.

Code

KotlinDelegationApplication.kt

package com.stonesoupprogramming.delegation.kotlindelegation

import org.hibernate.validator.constraints.NotBlank
import org.springframework.beans.factory.annotation.Autowired
import org.springframework.boot.SpringApplication
import org.springframework.boot.autoconfigure.SpringBootApplication
import org.springframework.data.jpa.repository.JpaRepository
import org.springframework.stereotype.Controller
import org.springframework.stereotype.Service
import org.springframework.ui.Model
import org.springframework.validation.BindingResult
import org.springframework.web.bind.annotation.GetMapping
import org.springframework.web.bind.annotation.ModelAttribute
import org.springframework.web.bind.annotation.PostMapping
import org.springframework.web.bind.annotation.RequestMapping
import javax.persistence.Entity
import javax.persistence.GeneratedValue
import javax.persistence.Id
import javax.transaction.Transactional
import javax.validation.Valid
import javax.validation.constraints.NotNull

@SpringBootApplication
class KotlinDelegationApplication

enum class FamilyMemberType {Father, Mother, Daughter, Son}

//Basic entity class
@Entity
data class Belchers(
        @field: Id
        @field: GeneratedValue
        var id : Long? = null,

        @field: NotBlank(message = "Need a name!")
        var name : String = "",

        @field: NotNull(message = "Assign to a family type")
        var familyMemberType: FamilyMemberType? = null
)

//Now we are going to define a JpaRepository to handle persistence
interface BelchersRepository : JpaRepository

//Here is a service class that contains our business logic
@Service
@Transactional
class BelchersService(
        //Inject an instance of BelchersRepository
        @field : Autowired
        val belchersRepository: BelchersRepository) : BelchersRepository by belchersRepository {
    /**
     * The above line demonstrates Kotlin's delegation syntax. It works by specifying a variable whose type
     * is an interface (no concrete or abstract classes). After the colon, we specify the name of the interface
     * and the variable that provides the object we are using for delegation. The Kotlin compiler builds out all of
     * methods included in the interface and routes calls to those method to the delegate object.
     *
     * In this example, BelcherService gets all of the methods included in BelchersRepository and the belcherRepository
     * object handles the implementation of all BelcherRepository method unless we override them.
     */

    /**
     * Here is an example of where we override only one method of BelchersRepository
     *  so that we can customize the behavior.
     */
    override fun <s> save(entity: S): S {
        val formattedName = entity?.name?.split(" ")?.map { it.toLowerCase().capitalize() }?.joinToString(" ")
        if(formattedName != null){
            entity.name = formattedName
        }
        return belchersRepository.save(entity)
    }
}

//Example MVC controller
@Controller
@RequestMapping("/")
class IndexController (
        @field: Autowired
        val belchersService: BelchersService) {

    @ModelAttribute("belcherFamily")
    fun fetchFamily() = belchersService.findAll()

    @ModelAttribute("belcher")
    fun fetchBelcher() = Belchers()

    @GetMapping
    fun doGet() = "index"

    @PostMapping
    fun doPost(@Valid belcher : Belchers, bindingResult: BindingResult, model: Model) : String {
        var entity = belcher

        if(!bindingResult.hasErrors()){
            belchersService.save(belcher)
            entity = Belchers()
        }

        //Notice the use of extension functions to keep the code concise
        model.addBelcher(entity)
        model.addBelcherFamily()

        return "index"
    }

    //Some private extension functions which tend to be really useful in Spring MVC
    private fun Model.addBelcherFamily(){
        addAttribute("belcherFamily", belchersService.findAll())
    }

    private fun Model.addBelcher(belcher: Belchers = Belchers()){
        addAttribute("belcher", belcher)
    }
}

fun main(args: Array) {
    SpringApplication.run(KotlinDelegationApplication::class.java, *args)
}

index.html

<!DOCTYPE html>
<html lang="en" xmlns="http://www.w3.org/1999/xhtml"
      xmlns:th="http://www.thymeleaf.org">
<head>
    <meta charset="UTF-8">
    <title>Kotlin Delegation Example</title>

    <script src="http://code.jquery.com/jquery-3.2.1.js"
            integrity="sha256-DZAnKJ/6XZ9si04Hgrsxu/8s717jcIzLy3oi35EouyE="
            crossorigin="anonymous"></script>

    <!-- Latest compiled and minified CSS & JS -->
    <link rel="stylesheet" media="screen" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css">
    <script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/js/bootstrap.min.js"></script>

    <style>
        button {
            margin-top: 10px;
        }
    </style>
</head>
<body>
<div class="jumbotron">
    <div class="container">
        <h1>Kotlin Delegation</h1>
        <p>Web demonstration showing how Kotlin's delegation features pairs with Spring Data</p>
    </div>
</div>

<div class="container">
    <div class="row" th:if="${belcherFamily.size() > 0}">
        <div class="col-xs-12 col-sm-12 col-md-12 col-lg-12">
            <table class="table table-striped table-hover">
                <thead>
                <tr>
                    <th>ID</th>
                    <th>Name</th>
                    <th>Family Member Type</th>
                </tr>
                </thead>
                <tbody>
                <tr th:each="belcher : ${belcherFamily}">
                    <td th:text="${belcher.id}"></td>
                    <td th:text="${belcher.name}"></td>
                    <td th:text="${belcher.familyMemberType}"></td>
                </tr>
                </tbody>
            </table>
        </div>
    </div>

    <div class="row">
        <div class="col-xs-12 col-sm-12 col-md-12 col-lg-12">
            <form th:action="@{/}" method="post" th:object="${belcher}">
                <legend>Add a Family Member</legend>

                <div th:class="${#fields.hasErrors('name') ? 'form-group has-error' : 'form-group'}">
                    <label for="name">Name</label>
                    <input class="form-control" name="name" id="name" th:field="*{name}" />
                    <span th:if="${#fields.hasErrors('name')}" th:errors="*{name}" class="help-block"></span>
                </div>

                <select name="type" id="type" class="form-control" th:field="*{familyMemberType}">
                    <option th:each="value : ${T(com.stonesoupprogramming.delegation.kotlindelegation.FamilyMemberType).values()}"
                            th:value="${value}" th:text="${value}" />
                </select>

                <button class="btn btn-primary">Submit</button>
            </form>
        </div>
    </div>
</div>
</body>
</html>

pom.xml

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 	xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
	<modelVersion>4.0.0</modelVersion>

	<groupId>com.stonesoupprogramming.delegation</groupId>
	<artifactId>kotlin-delegation</artifactId>
	<version>0.0.1-SNAPSHOT</version>
	<packaging>jar</packaging>

	<name>kotlin-delegation</name>
	<description>Demo project for Spring Boot</description>

	<parent>
		<groupId>org.springframework.boot</groupId>
		<artifactId>spring-boot-starter-parent</artifactId>
		<version>1.5.6.RELEASE</version>
		<relativePath/> <!-- lookup parent from repository -->
	</parent>

	<properties>
		<kotlin.compiler.incremental>true</kotlin.compiler.incremental>
		<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
		<project.reporting.outputEncoding>UTF-8</project.reporting.outputEncoding>
		<java.version>1.8</java.version>
		<kotlin.version>1.1.3-2</kotlin.version>
		<thymeleaf.version>3.0.2.RELEASE</thymeleaf.version>
		<thymeleaf-layout-dialect.version>2.1.1</thymeleaf-layout-dialect.version>
	</properties>

	<dependencies>
		<dependency>
			<groupId>org.springframework.boot</groupId>
			<artifactId>spring-boot-starter-data-jpa</artifactId>
		</dependency>
		<dependency>
			<groupId>org.springframework.boot</groupId>
			<artifactId>spring-boot-starter-thymeleaf</artifactId>
		</dependency>
		<dependency>
			<groupId>org.springframework.boot</groupId>
			<artifactId>spring-boot-starter-web</artifactId>
		</dependency>
		<dependency>
			<groupId>org.springframework.boot</groupId>
			<artifactId>spring-boot-devtools</artifactId>
			<scope>runtime</scope>
		</dependency>
		<dependency>
			<groupId>org.hsqldb</groupId>
			<artifactId>hsqldb</artifactId>
			<scope>runtime</scope>
		</dependency>
		<dependency>
			<groupId>org.jetbrains.kotlin</groupId>
			<artifactId>kotlin-stdlib-jre8</artifactId>
			<version>${kotlin.version}</version>
		</dependency>
		<dependency>
			<groupId>org.jetbrains.kotlin</groupId>
			<artifactId>kotlin-reflect</artifactId>
			<version>${kotlin.version}</version>
		</dependency>

		<dependency>
			<groupId>org.springframework.boot</groupId>
			<artifactId>spring-boot-starter-test</artifactId>
			<scope>test</scope>
		</dependency>
	</dependencies>

	<build>
		<sourceDirectory>${project.basedir}/src/main/kotlin</sourceDirectory>
		<testSourceDirectory>${project.basedir}/src/test/kotlin</testSourceDirectory>
		<plugins>
			<plugin>
				<groupId>org.springframework.boot</groupId>
				<artifactId>spring-boot-maven-plugin</artifactId>
			</plugin>
			<plugin>
				<artifactId>kotlin-maven-plugin</artifactId>
				<groupId>org.jetbrains.kotlin</groupId>
				<version>${kotlin.version}</version>
				<configuration>
					<compilerPlugins>
						<plugin>spring</plugin>
					</compilerPlugins>
					<jvmTarget>1.8</jvmTarget>
				</configuration>
				<executions>
					<execution>
						<id>compile</id>
						<phase>compile</phase>
						<goals>
							<goal>compile</goal>
						</goals>
					</execution>
					<execution>
						<id>test-compile</id>
						<phase>test-compile</phase>
						<goals>
							<goal>test-compile</goal>
						</goals>
					</execution>
				</executions>
				<dependencies>
					<dependency>
						<groupId>org.jetbrains.kotlin</groupId>
						<artifactId>kotlin-maven-allopen</artifactId>
						<version>${kotlin.version}</version>
					</dependency>
				</dependencies>
			</plugin>
		</plugins>
	</build>

</project>

application.properties

spring.thymeleaf.mode= HTML
spring.thymeleaf.cache=false

Project Structure

structures copy

Explanation

Most developers are familiar with the delegation pattern. Delegation provides many of the same benefits as inheritence, but helps reduce issues such as fragile base classes or tight coupling to the base class. Kotlin’s delegation features go further by requiring developers to use an interface which helps promote loose coupling and programming to an interface. Since delegate objects aren’t part of an inheritance chain, we are free to use mutliple objects with delegation.

One of the huge drawbacks of using the delegation pattern in Java is the amount of work involved to use the pattern. Java requires developers to actually declare and implement each method of the delegate object. Although most IDE’s are happy to generate delegate methods, such methods require maintaince later on should an interface add or remove methods. This makes inheritence more attractive since the Java compiler adds or removes methods in child classes as they are added or removed in the base class without additional work from the developer.

The Kotlin compiler address the problems associated with developing delegate objects by generating the delegate methods for the developer. The Kotlin delegation syntax is found in KotlinDelegationApplication.kt on lines 48-51. As mentioned above, Kotlin requires the usage of interfaces when using delegation. This works nicely with Spring Data’s JPA template, since developers simply declare an interface that extends JpaRepository anyway. The delegation pattern is used in the BelchersService class, which takes an instance of BelchersRepository in its constructor and then uses the object to build out delegate methods.

At this point, BelcherService has the same methods as BelcherRepository without the need to generate boilerplate declarations and implementations to the delegate object. Since the code is loosely coupled, we are free to swap out different implementations of BelcherRepository as required. The code is easier to read because we are spared the boilerplate code required to implement the delegation pattern.

You may view the source at https://github.com/archer920/KotlinDelegation

Kotlin Koans—Part 11

This portion of the Kotlin Koans tutorial focuses on Object Expressions. Practically speaking, Object Expressions serve the same role as anonymous innner classes in Java. They let us make modifications on a class in one particular case without having to create an entirely new class.

This portion of the tutorial has developers creating a dynamic Comparator class that sorts numbers in descending order.

fun task10(): List {
    val arrayList = arrayListOf(1, 5, 2)
    Collections.sort(arrayList, object: Comparator {
        override fun compare(o1: Int?, o2: Int?): Int {
            return o2?.compareTo(o1 ?: 0) ?: 0
        }
    })
    return arrayList
}

We could have used a lambda in this case, but that would miss the point of what the tutorial is trying to teach. In this code snippet, the second paramter of Collections.sort is an Object Expression that defines a custom Comparator class.

You’ll notice that the definition of compare is full of null safe expressions as indicated the by ? and ?: opeartors. As a side note, I really like how Kotlin has an arrayListOf() function that let’s you create an ArrayList. Sure it does the same thing as Arrays.asList, but again, it’s more concise.

You can view part 10 here

Kotlin Koans—Part 9

Java and Kotlin are strongly typed languages. It’s not necessary to cast types when working up an object graph. For example

public void sort(Collection col){
    //todo
}

sort(new ArrayList());
sort(new HashSet());

This is an example of polymorphism in Java. ArrayList and HashSet are both Collections so it’s acceptable to pass either types to the example sort method.

Keep in mind this is not a two way street. This code would not compile.

public void sort(List list){
    //todo
}

Collection col = new ArrayList();
sort(col); //Compile error!
sort((List) col); //OK

Even though col points at an ArrayList and ArrayList implements List, Java forbids you to pass col to sort without a cast. This is because the compiler has no idea that col is pointing at an ArrayList. Keep in mind this is true of Kotlin also.

Although we can get our code to compile with a cast, it’s still dangerous code. Let’s tweak it a little big and have col point at a HashSet instead of ArrayList.

public void sort(List list){
    //todo
}

Collection col = new HashSet();

//Compiles but throws
//ClassCastException
sort((List) col);

Now the code compiles, but it will fail at run time. There is no way to cast HashSet to a List. HashSet does not implement List in anyway so when the code attempts to make the cast, the code will fail. We have to use the instanceof operator to make sure the cast is safe first.

public void sort(List list){
    //todo
}

Collection col = new HashSet();

if (col instanceof List){
    //Now it's safe
    sort((List) col);
}

This code is now safe. It will check if the runtime type of col is a List first. If the object is a List, it will make the cast. Otherwise, the cast will not get made.

Tutorial

This portion of the Kotlin Koans tutorial shows off how Kotlin handles casting compared to Java. Here is the Java code that needs to get rewrote in Kotlin.

public class JavaCode8 extends JavaCode {
    public int eval(Expr expr) {
        if (expr instanceof Num) {
            return ((Num) expr).getValue();
        }
        if (expr instanceof Sum) {
            Sum sum = (Sum) expr;
            return eval(sum.getLeft()) + eval(sum.getRight());
        }
        throw new IllegalArgumentException("Unknown expression");
    }
}

Kotlin has a when keyword that is used for casting. Here is the equivalent Kotlin code.

fun todoTask8(expr: Expr): Int {
    when (expr) {
        is Num -> return expr.value
        is Sum -> return todoTask8(expr.left) + todoTask8(expr.right)
        else -> throw IllegalArgumentException("Unknown expression")
    }
}

As usual, Kotlin is more concise than Java. The when block starts with the when followed by the variable in question. You can have any number of is clauses in this statement followed by the type. The variable is automatically cast to the specified type on the right hand side of the -> operator.

You can click here to see Part 8

Python Unit Testing

Unit testing is a critical portion of any significant software project. Althougth adding unit tests increases the size of your project’s code base, well written unit tests let us maintain confidence in our code base.

Well designed code should work well as stand alone or mostly stand alone software components. This is true of both procedural code and OOP. Unit tests test these components to make sure they continue to work as expected. It helps development because if a software components breaks an expected interface or starts behaving in an expected fashion, we will know about the issue prior to building or deploying our application.

Many developers (including myself) prefer to know about bugs before users see them. Writing good units are one of many tools that help us catch bugs before they make it out into production code. This post will walk us through Python’s unit testing framework.

Example Test Class and Unit Test

Let’s start by creating a class that we are going to unit test. We are going to make a Greeter class that takes a Gender enumeration and a Greeter class.

from enum import Enum


class Gender(Enum):
    MALE = "m"
    FEMALE = "f"


class Greeter:
    def __init__(self, name, gender):
        self.name = name
        self.gender = gender

    def greet(self):
        if self.gender == Gender.MALE:
            return 'Hello Mr. {}'.format(self.name)
        elif self.gender == Gender.FEMALE:
            return 'Hello Ms. {}'.format(self.name)

What we are expecting the Greeter.greet method to do is print a greeting that contains either Mr or Ms depending on the gender. Let’s make a test that makes sure we are getting the correct output.

import unittest


class TestGreeter(unittest.TestCase):
    def test_greet(self):
        # Create a Greeter Object to test
        greeter_male = Greeter('Jonny', Gender.MALE)

        # Now check it is working properly
        self.assertTrue('Mr' in greeter_male.greet(), 'Expected Mr')

        # Now check female
        greeter_female = Greeter('Jane', Gender.FEMALE)
        self.assertTrue('Ms.' in greeter_female.greet(), 'Expected Ms')

if __name__ == '__main__':
    # This invokes all unit tests
    unittest.main()

We get the following output in the console. It’s pretty boring.

Ran 1 test in 0.002s

OK

Catching Bugs

Our first test is what we see if we have a working class and unit test. It’s very boring and we want boring. In many software projects, we tend to change things as we add new features, fix bugs, or improve code. If our changes break things in our code base, we want our unit tests to tell us about the issue.

Let’s make a small change in our Greeter class

class Greeter:
    def __init__(self, name, gender):
        self.name = name
        self.gender = gender

    def greet(self):
        if self.gender == Gender.MALE:
            return 'Hello Mr. {}'.format(self.name)
        elif self.gender == Gender.FEMALE:
            # Changed Ms. to Mrs.
            return 'Hello Mrs. {}'.format(self.name)

Now let’s run our test and see what happens

Failure
Traceback (most recent call last):
  File "/usr/local/Cellar/python3/3.6.1/Frameworks/Python.framework/Versions/3.6/lib/python3.6/unittest/case.py", line 59, in testPartExecutor
    yield
  File "/usr/local/Cellar/python3/3.6.1/Frameworks/Python.framework/Versions/3.6/lib/python3.6/unittest/case.py", line 601, in run
    testMethod()
  File "/Users/stonesoup/PycharmProjects/stonesoupprogramming/unit_test_demo.py", line 35, in test_greet
    self.assertTrue('Ms.' in greeter_female.greet(), 'Expected Ms')
  File "/usr/local/Cellar/python3/3.6.1/Frameworks/Python.framework/Versions/3.6/lib/python3.6/unittest/case.py", line 678, in assertTrue
    raise self.failureException(msg)
AssertionError: False is not true : Expected Ms


Ran 1 test in 0.013s

FAILED (failures=1)

If you are looking closely, we changed Ms. to Mrs. in our greeting. Given how small the change, it’s really easy for our human eyes to overlook the change and anyone can image how easy it would be for this bug to make it into production. Since our unit test is well written, we know about this bug right away!

If we did want our message to print Mrs rather than Ms, we need to update our unit test. That’s a good thing because it makes us think about how changes to our code impact the code base in general. Unit tests are so helpful that many developers have even adopted to “Test Driven Development” programming discipline.

You can learn more about Python’s unit testing framework at here.

Enumerations—Python

Enumerations are a way to group constants together and improve code readibility and type checking. Here is an example of an enumeration in Python.

from enum import Enum
from random import randint


class Color(Enum):
    RED = 1
    BLUE = 2
    GREEN = 3


def pick_color():
    pick = randint(1, 3)
    if pick == Color.RED.value:
        return Color.RED
    elif pick == Color.BLUE.value:
        return Color.BLUE
    elif pick == Color.GREEN.value:
        return Color.GREEN


def print_color(color):
    if color == Color.RED:
        print('Red')
    elif color == Color.GREEN:
        print('Green')
    elif color == Color.BLUE:
        print('Blue')


if __name__ == '__main__':
    color = pick_color()
    print_color(color)

Python enumeration extend the enum class. After inheriting from enum, we just list out the values in our enumeration and assign them constants.

The pick_color() function returns a randomly picked enumeration. We then pass that value to print_color().

You’ll notice that print_color accepts a color object and does comparisons against the values of the Color enumeration. You can see that the code is much more readible (and also more robust) than using literals such as 1, 2, or 3 in our code. The other nice aspect of using an enumeration is that we can change the values of our constants without breaking code and we can add more constants if needed.

Circular Linked List—Python

The circular linked list a variant of the singly linked list where the last Node links to the head rather than None. Since the list contains a circular reference to the Head, we can navigate a circular linked list starting at any index rather than starting at the head node.

Here is the code for a circular linked list implementation with unit tests. We won’t dicuss the unit tests in this post, but we will go over the linked list implementation.

from enum import Enum


class NodeConstants(Enum):
    FRONT_NODE = 1


class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node

    def __str__(self):
        if self.element:
            return self.element.__str__()
        else:
            return 'Empty Node'

    def __repr__(self):
        return self.__str__()


class CircularLinkedList:
    def __init__(self):
        self.head = Node(element=NodeConstants.FRONT_NODE)

        self.head.next_node = self.head

    def size(self):
        count = 0
        current = self.head.next_node

        while current != self.head:
            count += 1
            current = current.next_node

        return count

    def insert_front(self, data):
        node = Node(element=data, next_node=self.head.next_node)
        self.head.next_node = node

    def insert_last(self, data):
        current_node = self.head.next_node

        while current_node.next_node != self.head:
            current_node = current_node.next_node

        node = Node(element=data, next_node=current_node.next_node)
        current_node.next_node = node

    def insert(self, data, position):
        if position == 0:
            self.insert_front(data)
        elif position == self.size():
            self.insert_last(data)
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                current_pos = 0

                while current_pos < position - 1:
                    current_pos += 1
                    current_node = current_node.next_node

                node = Node(data, current_node.next_node)
                current_node.next_node = node
            else:
                raise IndexError

    def remove_first(self):
        self.head.next_node = self.head.next_node.next_node

    def remove_last(self):
        current_node = self.head.next_node

        while current_node.next_node.next_node != self.head:
            current_node = current_node.next_node

        current_node.next_node = self.head

    def remove(self, position):
        if position == 0:
            self.remove_first()
        elif position == self.size():
            self.remove_last()
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                current_pos = 0

                while current_pos < position - 1:
                    current_node = current_node.next_node
                    current_pos += 1

                current_node.next_node = current_node.next_node.next_node
            else:
                raise IndexError

    def fetch(self, position):
        if 0 <= position < self.size():
            current_node = self.head.next_node
            current_pos = 0

            while current_pos < position:
                current_node = current_node.next_node
                current_pos += 1

            return current_node.element
        else:
            raise IndexError


import unittest
from random import randint


class TestCircularLinkedList(unittest.TestCase):
    names = ['Bob Belcher',
             'Linda Belcher',
             'Tina Belcher',
             'Gene Belcher',
             'Louise Belcher']

    def test_init(self):
        dll = CircularLinkedList()
        self.assertIsNotNone(dll.head)
        self.assertEqual(dll.size(), 0)

    def test_insert_front(self):
        dll = CircularLinkedList()
        for name in TestCircularLinkedList.names:
            dll.insert_front(name)

        self.assertEqual(dll.fetch(0), TestCircularLinkedList.names[4])
        self.assertEqual(dll.fetch(1), TestCircularLinkedList.names[3])
        self.assertEqual(dll.fetch(2), TestCircularLinkedList.names[2])
        self.assertEqual(dll.fetch(3), TestCircularLinkedList.names[1])
        self.assertEqual(dll.fetch(4), TestCircularLinkedList.names[0])

    def test_insert_last(self):
        dll = CircularLinkedList()
        for name in TestCircularLinkedList.names:
            dll.insert_last(name)

        for i in range(len(TestCircularLinkedList.names) - 1):
            self.assertEqual(dll.fetch(i), TestCircularLinkedList.names[i])

    def test_insert(self):
        dll = CircularLinkedList()
        for name in TestCircularLinkedList.names:
            dll.insert_last(name)

        pos = randint(0, len(TestCircularLinkedList.names) - 1)

        dll.insert('Teddy', pos)
        self.assertEqual(dll.fetch(pos), 'Teddy')

    def test_remove_first(self):
        dll = CircularLinkedList()
        for name in TestCircularLinkedList.names:
            dll.insert_last(name)

        for i in range(dll.size(), 0, -1):
            self.assertEqual(dll.size(), i)
            dll.remove_first()

    def test_remove_last(self):
        dll = CircularLinkedList()
        for name in TestCircularLinkedList.names:
            dll.insert_last(name)

        for i in range(dll.size(), 0, -1):
            self.assertEqual(dll.size(), i)
            dll.remove_last()

    def test_remove(self):
        dll = CircularLinkedList()
        for name in TestCircularLinkedList.names:
            dll.insert_last(name)

        dll.remove(1)

        self.assertEqual(dll.fetch(0), 'Bob Belcher')
        self.assertEqual(dll.fetch(1), 'Tina Belcher')
        self.assertEqual(dll.fetch(2), 'Gene Belcher')
        self.assertEqual(dll.fetch(3), 'Louise Belcher')


if __name__ == '__main__':
    unittest.main()

NodeContants

NodeConstants is an example of Python’s enumeration. A circular linked list requires a distinct head node that the client code can easily identify. Without a distinct head node, we could easily introduce an infinate loop when traversing the linked list. We are going to use NodeContants to help identify the head node.

from enum import Enum


class NodeConstants(Enum):
    FRONT_NODE = 1

There are other ways to indentify the head node, so using enumerations isn’t required. It does give us a way to show off how to do enumerations in Python for those readers who are interested.

Node

We can use the same Node class that we used in singular linked list. Like all linked lists, the Node class holds the data stored in the list and a reference to the next Node in the list.

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node

    def __str__(self):
        if self.element:
            return self.element.__str__()
        else:
            return 'Empty Node'

    def __repr__(self):
        return self.__str__()

CircularLinkedList

This class is the work house of this module and provides us with the linked list implementation. It’s not very different than the singular linked list implementation.

class CircularLinkedList:
    def __init__(self):
        self.head = Node(element=NodeConstants.FRONT_NODE)
        self.head.next_node = self.head

    def size(self):
        count = 0
        current = self.head.next_node

        while current != self.head:
            count += 1
            current = current.next_node

        return count

    def insert_front(self, data):
        node = Node(element=data, next_node=self.head.next_node)
        self.head.next_node = node

    def insert_last(self, data):
        current_node = self.head.next_node

        while current_node.next_node != self.head:
            current_node = current_node.next_node

        node = Node(element=data, next_node=current_node.next_node)
        current_node.next_node = node

    def insert(self, data, position):
        if position == 0:
            self.insert_front(data)
        elif position == self.size():
            self.insert_last(data)
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                current_pos = 0

                while current_pos < position - 1:
                    current_pos += 1
                    current_node = current_node.next_node

                node = Node(data, current_node.next_node)
                current_node.next_node = node
            else:
                raise IndexError

    def remove_first(self):
        self.head.next_node = self.head.next_node.next_node

    def remove_last(self):
        current_node = self.head.next_node

        while current_node.next_node.next_node != self.head:
            current_node = current_node.next_node

        current_node.next_node = self.head

    def remove(self, position):
        if position == 0:
            self.remove_first()
        elif position == self.size():
            self.remove_last()
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                current_pos = 0

                while current_pos < position - 1:
                    current_node = current_node.next_node
                    current_pos += 1

                current_node.next_node = current_node.next_node.next_node
            else:
                raise IndexError

    def fetch(self, position):
        if 0 <= position < self.size():
            current_node = self.head.next_node
            current_pos = 0

            while current_pos < position:
                current_node = current_node.next_node
                current_pos += 1

            return current_node.element
        else:
            raise IndexError

__init__

We initialize the linked list by creating a head Node and then pointing it’s next_node at itself.

def __init__(self):
    self.head = Node(element=NodeConstants.FRONT_NODE)
    self.head.next_node = self.head

In this case, we will use our NodeConstants.FRONT_NODE to help us indentify the head of the list in the debugger. We don’t actually need this but it does help make the code more clear.

size

This method returns the number of elements contained in the linked list.

def size(self):
    count = 0
    current = self.head.next_node

    while current != self.head:
        count += 1
        current = current.next_node

    return count

We begin by making a count variable and a current variable. Current points at self.head.next_node because we aren’t counting self.head. Now we are going to loop until current == self.head. We don’t need to check for None in this case because we don’t have any such Nodes in this implementation.

As we loop, we increment count by one and then advance current to the next node in the list. Eventually, current points at self.head and we terminate the loop at this point. We then return the count.

insert_front

There isn’t much work to do to insert a Node at the beginning of the list.

def insert_front(self, data):
    node = Node(element=data, next_node=self.head.next_node)
    self.head.next_node = node

We create a new Node and point it’s next node at self.head.next_node. Then we just need to point self.head.next_node at the new Node.

insert_last

To insert a Node at the end of the list, we need to tranverse the list to right before self.head.

def insert_last(self, data):
    current_node = self.head.next_node

    while current_node.next_node != self.head:
        current_node = current_node.next_node

    node = Node(element=data, next_node=current_node.next_node)
    current_node.next_node = node

Once again, we have a current_node that requires us to start at self.head.next_node. We then enter a loop that terminates when current_node.next_node == self.head to avoid an infinate loop.

Once we find our insertion point, we create a new Node and point it’s next_node to current_node.next_node (which happens to be self.head). Then current_node.next_node is updated to point at Node.

insert

The insert method let’s us support insertions in the middle of the list. It works by traversing the list to right before the desired position and performing an insertion.
Keep in mind this method has four possible scenerios it must take into account.

  1. Position is 0 -> insert at the front
  2. Position == size() -> insert the end
  3. Position size() -> throw exception
  4. Position > 0 and Position Perform insertion
def insert(self, data, position):
    if position == 0:
        # Case 1
        self.insert_front(data)
    elif position == self.size():
        # Case 2
        self.insert_last(data)
    else:
        if 0 < position < self.size():
            # Case 4
            current_node = self.head.next_node
            current_pos = 0

            while current_pos < position - 1:
                current_pos += 1
                current_node = current_node.next_node

            node = Node(data, current_node.next_node)
            current_node.next_node = node
        else:
            # Case 3
            raise IndexError

The cases have been identified with the comments. In cases one and two, we are simply going to reuse code by calling self.insert_front or self.insert_last respectively. We handle case three by raising IndexError to indicate a programming error.

Case four works similar to other other insertions. We start with current_node at self.head.next_node and current_pos at 0. Then we iterate through the list until we reach the node right before the specified position (position – 1).

After exiting the while loop, we create a new Node and point it's next_node at current_node.next_node. The we update current_node.next_node to point at our new Node which now resides at our position.

remove_first

When removing nodes from the front of the list, we reassign self.head.next_node rather than self.head.

def remove_first(self):
    self.head.next_node = self.head.next_node.next_node

Remember that the last Node in this linked list always points at self.head. If we accidently reassigned self.head rather than self.head.next_node, we would break our linked list. However, when we update self.head.next_node to point at self.head.next_node.next_node, we are removing the Node currently located at self.head.next_node.

The removed Node gets garbage collected by the Python runtime environment and the linked list is shrunk by one element.

remove_last

It’s a fairly painless process to remove elements from the end of a circular linked list. We simply need to advance to the element located two positions before self.head and then point that Node’s next_node at self.head.

def remove_last(self):
    current_node = self.head.next_node

    while current_node.next_node.next_node != self.head:
        current_node = current_node.next_node

    current_node.next_node = self.head

We begin with current_node pointing at self.head.next_node and then enter a while loop. Notice that the condition on the while loop is current_node_next_node.next_node != self.head. We want to advance to the second to last element in this list.

Once we have positioned current_node to the proper index in the list, we remove the last node by pointing current_node.next_node at self.head. The removed Node ends up getting grabage collected by Python’s runtime.

remove

The remove method supports removing items from the middle of the list. It has to account for the same cases as insert.

def remove(self, position):
    if position == 0:
        # Case 1
        self.remove_first()
    elif position == self.size():
        # Case 2
        self.remove_last()
    else:
        if 0 < position < self.size():
            # Case 3
            current_node = self.head.next_node
            current_pos = 0

            while current_pos < position - 1:
                current_node = current_node.next_node
                current_pos += 1

            current_node.next_node = current_node.next_node.next_node
        else:
            # Case 4
            raise IndexError

Once again, we are going to dicuss case 3. We start with current_node pointing at self.head.next_node and current_pos = 0. We traverse the list until we arrive at the Node located before position. Now we nust point current_node.next_node at current_node.next_node.next_node. The removed Node gets garbage collected by the Python runtime.

fetch

This method let’s us get data out of the list.

def fetch(self, position):
    if 0 <= position < self.size():
        current_node = self.head.next_node
        current_pos = 0

        while current_pos < position:
            current_node = current_node.next_node
            current_pos += 1

        return current_node.element
    else:
        raise IndexError

After checking position to make sure it's valid, we traverse the list until we arrive at the position. Then we return current_node.element. If position isn't valid, we raise an exception.

Conclusion

This code shows an example a circular linked list, but it’s a simple implementation that we could optimize. This implementation always starts at self.head and traverse the list to a required position, but it could operate by tracking the most recently accessed Node and starting traversals from that point rather than always starting at the front of the list.

Stack—Python

Implementing a Stack is a common problem that computer science students are asked to do while learning about data structures. Stacks are a data structure that implemenet the LIFO (last in, first out) principle. We can implement stacks using a linked list methodology or an array backed list.

In the real world, Python’s built in list object is one of many production tested objects that can and should be used for stacks. Our stack is a linked list implementation of a simple stack.

Here is the example code that we will work with followed by an explanation about how it works.

import unittest

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node

    def __str__(self):
        if self.element:
            return self.element.__str__()
        else:
            return 'Empty Node'

    def __repr__(self):
        return self.__str__()

class EmptyStackException(Exception):
    pass

class Stack:
    def __init__(self):
        self.top = None
        self.size = 0

    def push(self, data):
        self.top = Node(data, self.top)
        self.size += 1

    def pop(self):
        if self.top:
            val = self.top.element
            self.top = self.top.next_node
            self.size -= 1
            return val
        else:
            raise EmptyStackException

    def peek(self):
        if self.top:
            return self.top.element
        else:
            raise EmptyStackException

    def empty(self):
        return self.size == 0

    def __str__(self):
        elements = []
        curr = self.top
        while curr is not None:
            elements.append(curr.element)
            curr = curr.next_node
        return elements.__str__()

    def __repr__(self):
        return self.__str__()

class TestStack(unittest.TestCase):
    def __init__(self, method_name='runTest'):
        super().__init__(method_name)
        self.names = ['Bob Belcher',
                      'Linda Belcher',
                      'Tina Belcher',
                      'Gene Belcher',
                      'Louise Belcher']

    def test_init(self):
        stack = Stack()
        self.assertIsNone(stack.top)
        self.assertEqual(stack.size, 0)

    def test_push(self):
        stack = Stack()
        for name in self.names:
            stack.push(name)

        names = list(self.names)
        names.reverse()

        self.assertEqual(names.__str__(), stack.__str__())
        self.assertEqual(len(names), stack.size)

    def test_pop(self):
        stack = Stack()
        for name in self.names:
            stack.push(name)

        self.assertEqual(stack.pop(), 'Louise Belcher')
        self.assertEqual(stack.size, 4)

        self.assertEqual(stack.pop(), 'Gene Belcher')
        self.assertEqual(stack.size, 3)

        self.assertEqual(stack.pop(), 'Tina Belcher')
        self.assertEqual(stack.size, 2)

        self.assertEqual(stack.pop(), 'Linda Belcher')
        self.assertEqual(stack.size, 1)

        self.assertEqual(stack.pop(), 'Bob Belcher')
        self.assertEqual(stack.size, 0)

        with self.assertRaises(EmptyStackException):
            stack.pop()

    def test_peek(self):
        stack = Stack()
        for name in self.names:
            stack.push(name)

        self.assertEqual(stack.peek(), 'Louise Belcher')
        self.assertEqual(stack.size, 5)

        stack = Stack()
        with self.assertRaises(EmptyStackException):
            stack.peek()

    def test_empty(self):
        stack = Stack()
        self.assertTrue(stack.empty())

        for name in self.names:
            stack.push(name)

        self.assertFalse(stack.empty())

if __name__ == '__main__':
    unittest.main()

Node

Since this is a linked list implementation of a stack, we are going to begin with the Node class. The Node does the work of holding the data in the stack and contains a reference to the next item in the stack.

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node

    def __str__(self):
        if self.element:
            return self.element.__str__()
        else:
            return 'Empty Node'

    def __repr__(self):
        return self.__str__()

There isn’t a lot going on in this class in terms of methods. It has an __init__ method which takes optional element and next_node parameters that default to None. This class also implements __str__ and __repr__ so that debuggers such as PyCharm print out user readable information.

EmptyStackException

The EmptyStackException class is a custom exception that gets raised when client code attempts to remove items from an empty stack.

class EmptyStackException(Exception):
    pass

This class doesn’t do anything other than subclass the Exception base class. For this reason, it’s implemented with a pass statement.

Stack

Stack is our main class the implements a Stack. We begin with the code for this class followed by an explanation about how it works.

class Stack:
    def __init__(self):
        self.top = None
        self.size = 0

    def push(self, data):
        self.top = Node(data, self.top)
        self.size += 1

    def pop(self):
        if self.top:
            val = self.top.element
            self.top = self.top.next_node
            self.size -= 1
            return val
        else:
            raise EmptyStackException

    def peek(self):
        if self.top:
            return self.top.element
        else:
            raise EmptyStackException

    def empty(self):
        return self.size == 0

    def __str__(self):
        elements = []
        curr = self.top
        while curr is not None:
            elements.append(curr.element)
            curr = curr.next_node
        return elements.__str__()

    def __repr__(self):
        return self.__str__()

__init__

The __init__ method intializes the data structure to an empty stack.

def __init__(self):
    self.top = None
    self.size = 0

We have two class variables in our stack. The first variable, self.top, is a Node that represents the last item inserted into the Stack. It’s next_node property points to the next item in the stack, and so one. The other class variable is self.size, which represents the number of items that are placed in the stack.

push

The push method is used to add items to the stack.

def push(self, data):
    self.top = Node(data, self.top)
    self.size += 1

Whenever we add items to a Stack, the newest Node becomes the top of the stack. If you remember back from our Node class, it’s __init__ method has an optional next_node argument we can use to initialize the new Node with it’s next_node. This works well for us here because we can pass self.top as the next_node of the new Node and then immediatly assign the new Node to self.top. In this way, the last item in the Stack get’s shifted right and the new item becomes the top of the Stack. The next line of code simply increments the size of the stack by one, thus completing the operation of adding (or pushing) an item onto the Stack.

pop

The pop method is opposite operation to the push method. This method removes an item from the Stack.

def pop(self):
    if self.top:
        val = self.top.element
        self.top = self.top.next_node
        self.size -= 1
        return val
    else:
        raise EmptyStackException

The pop method needs to consider two possible cases. The fist case involves a Stack that has items on it and needs an item removed. The other case involves an empty stack. Let’s begin with the first case.

We start by checking if the stack has items. If the stack is empty, self.top is None. Assuming that self.top is not None, we begin by storing the data contained in self.top.element in a variable called val. Our next job is to delete that Node from the Stack by changing self.top to point at self.top.next_node. The original Node will get garbage collected by the Python runtime. Now that we have removed the Node, we need to shrink the size of the stack by one. After we decrease self.size, we can return val to the caller thus completing the pop operation.

If it turns our that the stack is empty, we need to notify the caller. I think it would be a very bad practice to simply return None, since calling pop() on an empty Stack would indicate a programming error. Thus, we raise EmptyStackException. The client code will either need to handle the Exception or allow the program to crash.

peek

The peek operation lets client code take a look at the first element in the Stack without removing the item.

def peek(self):
    if self.top:
        return self.top.element
    else:
        raise EmptyStackException

In this case, we just just need to return self.top.element if the stack has an item, or raise an EmptyStackException if the stack is empty.

empty

Clients of this class need to check if the Stack is empty prior to calling pop() or peek()

def empty(self):
    return self.size == 0

This method simply returns True if self.size == 0 or False if self.size is non-zero.

__str__ and __repr__

We don’t need these methods to represent a Stack, but if you choose to implement them, debuggers such as the on found in PyCharm will use these methods to print more user friendly data to the debugger window.

def __str__(self):
    elements = []
    curr = self.top
    while curr is not None:
        elements.append(curr.element)
        curr = curr.next_node
    return elements.__str__()

def __repr__(self):
    return self.__str__()

We are going to leverage Python’s list object to get a reader friendly String representation of our Stack. We start by making an empty list called elements. Then we create a curr variable that points at self.stop. Now, we are going to loop until the end of the Stack by checking if curr is None.

During each iteration of the while loop, we add curr.element to elements. Then we advance to the next node by assigning curr = curr.next_node. When we are done, we will return elements.__str__() which creates a String for us. The __repr__ method works by calling self.__str__().

Conclusion

This article is a simple linked list implementation of a Stack. Stacks are useful in cases where you need a LIFO data structure to track the order of which items are added to the stack. As you can see, a Stack is a much simplier data structure to implement than a linked list.

Doubly Linked List—Python

We saw in Singly Linked List the benefits of using a linked list over an array. Linked lists are data structures that grow and expand as needed. Not only is it easy to add an element at the beginning or end of a linked list, but it is also easy to insert elements at arbitrary positions within the list. We can also easily remove elements from the linked list when they are no longer needed.

The doubly linked list is a varient of the singly linked list. The main complaint about a singly linked list is that it can only traverse the list in one direction starting at the head and working until it reaches the end of the list. Clients may not notice a performance hit when operating on small lists, but large lists will almost certainly have a performance hit.

Doubly linked lists work by tracking both the next node and previous nodes in the list. Tracking both nodes creates more overhead when inserting or removing from the list, but it allows the list to work in a bi-directional fashion. That can allow for a major performance boost when operating on large lists.

Here is the entire code followed by an explanation as to how it works. Note that the topic is the Doubly Linked List so I won’t be covering the unit testing code in this module, but I did include for those who are interested.

class Node:
    def __init__(self, element=None, next_node=None, prev_node=None):
        self.element = element
        self.next_node = next_node
        self.prev_node = prev_node

    def __str__(self):
        if self.element:
            return self.element.__str__()
        else:
            return 'Empty Node'

    def __repr__(self):
        return self.__str__()


class DoublyLinkedList:
    def __init__(self):
        self.head = Node(element='Head')
        self.tail = Node(element='Tail')

        self.head.next_node = self.tail
        self.tail.prev_node = self.head

    def size(self):
        count = 0
        current = self.head.next_node

        while current is not None and current != self.tail:
            count += 1
            current = current.next_node

        return count

    def insert_front(self, data):
        node = Node(element=data, next_node=self.head.next_node, prev_node=self.head)
        self.head.next_node.prev_node = node
        self.head.next_node = node

    def insert_last(self, data):
        node = Node(element=data, next_node=self.tail, prev_node=self.tail.prev_node)
        self.tail.prev_node.next_node = node
        self.tail.prev_node = node

    def insert(self, data, position):
        if position == 0:
            self.insert_front(data)
        elif position == self.size():
            self.insert_last(data)
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                count = 0
                while count < (position - 1):
                    current_node = current_node.next_node
                    count += 1

                node = Node(element=data, next_node=current_node.next_node, prev_node=current_node)
                current_node.next_node.prev_node = node
                current_node.next_node = node
            else:
                raise IndexError

    def remove_first(self):
        self.head = self.head.next_node
        self.head.prev_node = None

    def remove_last(self):
        self.tail = self.tail.prev_node
        self.tail.next_node = None

    def remove(self, position):
        if position == 0:
            self.remove_first()
        elif position == self.size():
            self.remove_last()
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                current_pos = 0

                while current_pos < position:
                    current_node = current_node.next_node
                    current_pos += 1

                next_node = current_node.next_node
                prev_node = current_node.prev_node

                next_node.prev_node = prev_node
                prev_node.next_node = next_node
            else:
                raise IndexError

    def fetch(self, position):
        if 0 <= position < self.size():
            current_node = self.head.next_node
            current_pos = 0

            while current_pos < position:
                current_node = current_node.next_node
                current_pos += 1

            return current_node.element
        else:
            raise IndexError


import unittest
from random import randint


class TestDoublyLinkedList(unittest.TestCase):
    names = ['Bob Belcher',
             'Linda Belcher',
             'Tina Belcher',
             'Gene Belcher',
             'Louise Belcher']

    def test_init(self):
        dll = DoublyLinkedList()
        self.assertIsNotNone(dll.head)
        self.assertIsNotNone(dll.tail)
        self.assertEqual(dll.size(), 0)

    def test_insert_front(self):
        dll = DoublyLinkedList()
        for name in TestDoublyLinkedList.names:
            dll.insert_front(name)

        self.assertEqual(dll.fetch(0), TestDoublyLinkedList.names[4])
        self.assertEqual(dll.fetch(1), TestDoublyLinkedList.names[3])
        self.assertEqual(dll.fetch(2), TestDoublyLinkedList.names[2])
        self.assertEqual(dll.fetch(3), TestDoublyLinkedList.names[1])
        self.assertEqual(dll.fetch(4), TestDoublyLinkedList.names[0])

    def test_insert_last(self):
        dll = DoublyLinkedList()
        for name in TestDoublyLinkedList.names:
            dll.insert_last(name)

        for i in range(len(TestDoublyLinkedList.names) - 1):
            self.assertEqual(dll.fetch(i), TestDoublyLinkedList.names[i])

    def test_insert(self):
        dll = DoublyLinkedList()
        for name in TestDoublyLinkedList.names:
            dll.insert_last(name)

        pos = randint(0, len(TestDoublyLinkedList.names) - 1)

        dll.insert('Teddy', pos)
        self.assertEqual(dll.fetch(pos), 'Teddy')

    def test_remove_first(self):
        dll = DoublyLinkedList()
        for name in TestDoublyLinkedList.names:
            dll.insert_last(name)

        for i in range(dll.size(), 0, -1):
            self.assertEqual(dll.size(), i)
            dll.remove_first()

    def test_remove_last(self):
        dll = DoublyLinkedList()
        for name in TestDoublyLinkedList.names:
            dll.insert_last(name)

        for i in range(dll.size(), 0, -1):
            self.assertEqual(dll.size(), i)
            dll.remove_last()

    def test_remove(self):
        dll = DoublyLinkedList()
        for name in TestDoublyLinkedList.names:
            dll.insert_last(name)

        dll.remove(1)

        self.assertEqual(dll.fetch(0), 'Bob Belcher')
        self.assertEqual(dll.fetch(1), 'Tina Belcher')
        self.assertEqual(dll.fetch(2), 'Gene Belcher')
        self.assertEqual(dll.fetch(3), 'Louise Belcher')


if __name__ == '__main__':
    unittest.main()

Node

Like the singly linked list, the doubly linked list begins with a Node class that holds the data contained in the list and references to the previous and next nodes. Here is the code for the Node.

class Node:
    def __init__(self, element=None, next_node=None, prev_node=None):
        self.element = element
        self.next_node = next_node
        self.prev_node = prev_node

    def __str__(self):
        if self.element:
            return self.element.__str__()
        else:
            return 'Empty Node'

    def __repr__(self):
        return self.__str__()

Here is a break down of each methods in the Node class.

__init__

The __init__ method creates the node. All three of its parameters are optional, but basically we are setting the data contained in the node, and building refrences to next_node and previous_node.

def __init__(self, element=None, next_node=None, prev_node=None):
    self.element = element
    self.next_node = next_node
    self.prev_node = prev_node

__str__ and __repr__

I found that there was more work invloved with debugging doubly linked list, so in this version of the Node class, I chose to implement __str__ and __repr__ so that I could easily identify each Node in my debugger.

def __str__(self):
    # Check if self.element is null
    if self.element:
        # Just return the string representation
        # of self.element
        return self.element.__str__()
    else:
        # Otherwise return Empty Node
        # to indicate the node does not
        # hold data
        return 'Empty Node'

# We are just going to reuse the
# code in __str__ here
def __repr__(self):
    return self.__str__()

Doubly Linked List

This is an example of a doubly linked list. It’s not opitmized for the simply fact that we are learning. If you need an optimized list structure, you Python’s list object.

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(element='Head')
        self.tail = Node(element='Tail')

        self.head.next_node = self.tail
        self.tail.prev_node = self.head

    def size(self):
        count = 0
        current = self.head.next_node

        while current is not None and current != self.tail:
            count += 1
            current = current.next_node

        return count

    def insert_front(self, data):
        node = Node(element=data, next_node=self.head.next_node, prev_node=self.head)
        self.head.next_node.prev_node = node
        self.head.next_node = node

    def insert_last(self, data):
        node = Node(element=data, next_node=self.tail, prev_node=self.tail.prev_node)
        self.tail.prev_node.next_node = node
        self.tail.prev_node = node

    def insert(self, data, position):
        if position == 0:
            self.insert_front(data)
        elif position == self.size():
            self.insert_last(data)
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                count = 0
                while count < (position - 1):
                    current_node = current_node.next_node
                    count += 1

                node = Node(element=data, next_node=current_node.next_node, prev_node=current_node)
                current_node.next_node.prev_node = node
                current_node.next_node = node
            else:
                raise IndexError

    def remove_first(self):
        self.head = self.head.next_node
        self.head.prev_node = None

    def remove_last(self):
        self.tail = self.tail.prev_node
        self.tail.next_node = None

    def remove(self, position):
        if position == 0:
            self.remove_first()
        elif position == self.size():
            self.remove_last()
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                current_pos = 0

                while current_pos < position:
                    current_node = current_node.next_node
                    current_pos += 1

                next_node = current_node.next_node
                prev_node = current_node.prev_node

                next_node.prev_node = prev_node
                prev_node.next_node = next_node
            else:
                raise IndexError

    def fetch(self, position):
        if 0 <= position < self.size():
            current_node = self.head.next_node
            current_pos = 0

            while current_pos < position:
                current_node = current_node.next_node
                current_pos += 1

            return current_node.element
        else:
            raise IndexError

__init__

This doubly linked list implementation makes use of a head and a tail node. We traversing the list, the code will look for either head or tail as a means to detect if we are at the end of the list.

def __init__(self):
    self.head = Node(element='Head')
    self.tail = Node(element='Tail')

    self.head.next_node = self.tail
    self.tail.prev_node = self.head

We pass the strings “Head” and “Tail” as the element data for each of these nodes for debugging purpose. Since Node implements __str__ and __repr__, we will see Heads and Tail in the debugger (at least when using PyCharm).

The next two lines do the work of pointing head and tail at each other. When the list is created, head.next_node is tail. Conversly, tail.prev_node is head. This indicates an empty list.

size

This code inefficient on purpose. A better implementation would use a length varaible and increment or decrment it as Nodes are added and removed. However, in this case, I wanted to show how to traverse a list without the clutter of adding or removing Nodes.

def size(self):
    count = 0
    current = self.head.next_node

    while current is not None and current != self.tail:
        count += 1
        current = current.next_node

    return count

We start by making a count variable and a current variable that points at self.head.next_node. It’s really important that we use self.head.next_node instead of self.head because self.head’s purpose is to mark the beginning of the list, not contain data. If we failed to make this distinction, the size of the list will be off by one.

Now, we are going to traverse the list increment count by one an each iteration of the loop. We should check for None for defensive programming purposes, but the critical part of the loop condition is if current != self.tail. The self.tail Node marks the end of the list and so we do not wish to include it in the size of our list.

insert_front

This method inserts a new Node at the front of the Linked List.

def insert_front(self, data):
    node = Node(element=data, next_node=self.head.next_node, prev_node=self.head)
    self.head.next_node.prev_node = node
    self.head.next_node = node

Nodes inserted at the front of the list need their prev_node to point at self.head and their next_node to point at the Node located at self.head.next_node.

To complete the insertion, we now need to update self.head.next_node.prev_node to point back at the new Node that we created (otherwise, it would still point at self.head). Likewise, we need to update self.head.next_node to point at our new Node.

insert_last

The code for this is almost identical to insert_head with the main difference being that we are working on the tail Node rather than the head Node.

def insert_last(self, data):
    node = Node(element=data, next_node=self.tail, prev_node=self.tail.prev_node)
    self.tail.prev_node.next_node = node
    self.tail.prev_node = node

Once again, we create a new Node. It’s next_node has to point at self.tail and it’s prev_node needs to point at self.tail.prev_node.

To complete the insertion, we need to update self.tail.prev_node.next_node to point at our new Node (otherwise it will continue to point at self.tail). We also need to point self.tail.prev_node at our new Node.

insert

This method handles the insertion of a Node into the middle of the list. Keep in mind that it has to handle four possible cases.

  • Position could be 0 (front of list)
  • Position could be equal to size() (end of list)
  • Position is in the middle of the list
  • Position is size() (out of bounds)
def insert(self, data, position):
    if position == 0:
        # First case, we insert at front
        self.insert_front(data)
    elif position == self.size():
        # Second case, we insert at end
        self.insert_last(data)
    else:
        if 0 < position < self.size():
            # Third case, insert in middle
            current_node = self.head.next_node
            count = 0
            while count < (position - 1):
                current_node = current_node.next_node
                count += 1

            node = Node(element=data, next_node=current_node.next_node, prev_node=current_node)
            current_node.next_node.prev_node = node
            current_node.next_node = node
        else:
            # Fourth case, index out of bounds
            raise IndexError

The comments point out how this code handles each of the possible cases. Let's focus on the insertion. We begin by creating a count variable and current_node variable. Now, we need to traverse the list until we arrive at the node right before the desired position. Each interation of the loop requires us to point current_node at current_node.next_node.

Once we arrive at our destination, we create a new Node. We will point it's next_node at current_node.next_node and its prev_node at current_node. Doing the insertion at this point in the list causes the new node to appear at the position index specified in the method parameters.

To complete the insertion, we point current_node.next_node.prev_node at the new Node (otherwise it would still point at current_node). Likewise, we point current_node.next_node at our new Node.

Again, I should mention that this code is inefficient again. Normally we would make use of the bidirectional capabilities of the list and decide if we want to traverse the list in forward (like we do here) or in reverse. For example, if we are trying insert into a list at size() – 2, it doesn't make sense to start at the head node and traverse forward to find our insertion point when we could start at tail and move backwards.

remove_first

It’s really simple to remove nodes from the head of a doubly linked list.

def remove_first(self):
     self.head = self.head.next_node
     self.head.prev_node = None

You will notice that all we need to do is point self.head at self.head.next_node. Then we just set self.head.prev_node to None so that it doesn’t continue to point at the old self.head. The old Node will get garbage collected by the Python runtime.

remove_last

Removing the tail from the list is just as easy as removing the head.

def remove_last(self):
    self.tail = self.tail.prev_node
    self.tail.next_node = None

In this case, we just point self.tail at self.tail.prev_node. To remove the old Node, we next poitn self.tail.next_node to None. The old Node will get garbage collected by the Python runtime.

remove

Remove needs to handle the same cases that insert has to handle. Otherwise it works by traversing the list of the position to remove and deletes the Node.

def remove(self, position):
    if position == 0:
        # First case, remove at front
        self.remove_first()
    elif position == self.size():
        # Second case, remove from end
        self.remove_last()
    else:
        if 0 < position < self.size():
            # 3rd case, remove at middle
            current_node = self.head.next_node
            current_pos = 0

            while current_pos < position:
                current_node = current_node.next_node
                current_pos += 1

            next_node = current_node.next_node
            prev_node = current_node.prev_node

            next_node.prev_node = prev_node
            prev_node.next_node = next_node
        else:
            # 4th case, invalid position
            raise IndexError

Again, we will focus on the removal part of this code. We begin by traversing the list to find our desired position. This time, we stop at the actual position rather than the position before it. Once we arrive at our desired position, we store current_node.next_node and current_node.prev_node into their respective variables. To remove current_node, we simply need to point next_node.prev_node at prev_node and likewise point prev_node.next_node to next_node. Since there are no longer any references to current_node, it is garbage collected by the Python runtime.

fetch

Our final method is the fetch method, which let’s use retreive items from the Linked List.

def fetch(self, position):
    if 0 <= position < self.size():
        current_node = self.head.next_node
        current_pos = 0

        while current_pos < position:
             current_node = current_node.next_node
             current_pos += 1

        return current_node.element
    else:
        raise IndexError

By now readers should be familiar with how the list is traversed. We simply traverse the list to the desired position and return the Node.element to the caller.

Conclusion

Doubly linked list are a more advance form of linked list that supports bi-directional traversals. Bi-directional navigation is possible because each Node in the linked list stores a refrence to both the next and previous Node in the list.

Our linked list implementation only utilizes forward direction traversal to help keep the implementation simple. However, it would only require a small amount of work to make use of reverse traversals.

Singly Linked List—Python

Many of my programming students get asked to implement Linked Lists as a way to learn about data structures in programming. Now I am going to be very honest about this topic when it comes to Python. Python does not use fixed sized arrays list Java or C++ use. Instead, Python has a list object as a built in data type that grows and shrinks as needed.

For this reason, I can’t see any practical purpose to implementing a Linked List in Python other than for learning purposes (of course, that said, Java and C++ libraries have data structures that shrink and grow as needed also, so again, not sure why we would ever need to write our own linked list). That being said, I think there is value in learning about data structures such as Linked Lists.

Arrays

Many programming languages have a data structure called an array. Arrays are a lot like an egg carton. There are x number of slots in which you can place an egg. Here is an example of an array in Java.

String [] phoneNumbers = new String[12];
phoneNumbers[0] = "867-5309";
phoneNumbers[1] = "978-6410";
//and so on...

We use arrays for the same reason that we use lists in Python. They allow us to group common data together into a single variable. So we could iterate through this example array like this…

for (String num : phoneNumbers){
    System.out.println(num);
}

Arrays are extremely efficient in that you can easy create an array, fill it with data, and process that data. Nevertheless, Array’s have a major limitation. They are a fixed size. We are not able to grow or shrink and Array.

Linked List

Linked Lists are a data structure that give us the convience that is offered by an Array, but also allows us to grow and shrink the data structure as needed. We even get the added bonus of being able to insert elements into random positions in the array.

Linked list work on the idea that inside of the Linked List we have a Node object that contains the data for that particular node and a reference to the next node in the list. By manipulating where the node points, we can expand or shrink the list as needed. We can also insert items into the middle of the list by pointing the node at different Node objects within the list.

The Linked List itself is a container class for the Nodes. It does the work of creating Nodes, removing Nodes, and updating Nodes. Before we get into complete detail, here is the code for a simple Singly Linked List written in Python.

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node


class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def size(self):
        count = 0
        current = self.head

        while current is not None:
            count += 1
            current = current.next_node

        return count

    def insert_front(self, data):
        node = Node(element=data, next_node=self.head)
        self.head = node

    def insert_last(self, data):
        if not self.head:
            self.head = Node(element=data)
        else:
            current_node = self.head
            while current_node.next_node is not None:
                current_node = current_node.next_node
            current_node.next_node = Node(element=data)

    def insert(self, data, position):
        if self.head is None:
            self.head = Node(element=data)
        else:
            if position > self.size() or position < 0:
                raise IndexError
            else:
                if position == 0:
                    self.insert_front(data)
                elif position == self.size():
                    self.insert_last(data)
                else:
                    temp = self.head
                    pos = 0
                    while pos < (position - 1):
                        temp = temp.next_node
                        pos += 1

                    next_node = temp.next_node
                    temp.next_node = Node(element=data, next_node=next_node)

    def remove_first(self):
        if self.head is not None:
            self.head = self.head.next_node

    def remove_last(self):
        if self.head is not None:
            current_node = self.head
            prev = None

            while current_node.next_node is not None:
                prev = current_node
                current_node = current_node.next_node

            if prev is None:
                self.head = None
            else:
                prev.next_node = None

    def remove(self, position):
        if self.head is not None and position == 0:
            self.remove_first()
        elif self.head is not None and position == self.size():
            self.remove_last()
        else:
            if position  self.size():
                raise IndexError
            pos = 0
            current_node = self.head
            next_node = self.head.next_node
            while pos < (position - 1):
                pos += 1
                current_node = next_node
                next_node = current_node.next_node

            current_node.next_node = next_node.next_node

    def fetch(self, position):
        if self.head is None:
            return None
        elif position  self.size():
            raise IndexError
        else:
            current_node = self.head
            pos = 0
            while pos != position:
                pos += 1
                current_node = current_node.next_node

            return current_node.element


import unittest
from random import randint


class TestSinglyLinkedList(unittest.TestCase):
    names = ['Bob Belcher',
             'Linda Belcher',
             'Tina Belcher',
             'Gene Belcher',
             'Louise Belcher']

    def test_init(self):
        sll = SinglyLinkedList()
        self.assertIsNone(sll.head)

    def test_insert_front(self):
        sll = SinglyLinkedList()
        for name in TestSinglyLinkedList.names:
            sll.insert_front(name)

        self.assertEqual(sll.fetch(0), TestSinglyLinkedList.names[4])
        self.assertEqual(sll.fetch(1), TestSinglyLinkedList.names[3])
        self.assertEqual(sll.fetch(2), TestSinglyLinkedList.names[2])
        self.assertEqual(sll.fetch(3), TestSinglyLinkedList.names[1])
        self.assertEqual(sll.fetch(4), TestSinglyLinkedList.names[0])

    def test_insert_last(self):
        sll = SinglyLinkedList()
        for name in TestSinglyLinkedList.names:
            sll.insert_last(name)

        for i in range(len(TestSinglyLinkedList.names) - 1):
            self.assertEqual(sll.fetch(i), TestSinglyLinkedList.names[i])

    def test_insert(self):
        sll = SinglyLinkedList()
        for name in TestSinglyLinkedList.names:
            sll.insert_last(name)

        pos = randint(0, len(TestSinglyLinkedList.names) - 1)

        sll.insert('Teddy', pos)
        self.assertEqual(sll.fetch(pos), 'Teddy')

    def test_remove_first(self):
        sll = SinglyLinkedList()
        for name in TestSinglyLinkedList.names:
            sll.insert_last(name)

        for i in range(sll.size(), 0, -1):
            self.assertEqual(sll.size(), i)
            sll.remove_first()

    def test_remove_last(self):
        sll = SinglyLinkedList()
        for name in TestSinglyLinkedList.names:
            sll.insert_last(name)

        for i in range(sll.size(), 0, -1):
            self.assertEqual(sll.size(), i)
            sll.remove_last()

    def test_remove(self):
        sll = SinglyLinkedList()
        for name in TestSinglyLinkedList.names:
            sll.insert_last(name)

        sll.remove(1)

        self.assertEqual(sll.fetch(0), 'Bob Belcher')
        self.assertEqual(sll.fetch(1), 'Tina Belcher')
        self.assertEqual(sll.fetch(2), 'Gene Belcher')
        self.assertEqual(sll.fetch(3), 'Louise Belcher')

if __name__ == '__main__':
    unittest.main()

Implementation Details

As you can see, we are using Python’s OOP features to implement this linked list. That being said, this could have been down procedurally also. There is nothing that says linked lists have to be implemented in terms of classes and objects.

Node

The Node is the most basic element in the linked list. It has the responsibility to contain the data and point to the next node. That’s all it does. Here is the code for our Node class

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node

SinglyLinkedList

The SinglyLinkedList class is the actualy linked list implementation. This is called SinglyLinkedList because each of the Nodes only link in a single direction (as opposed to a doubly linked list, which is bi-directional).

Here is the code for SinglyLinkedList followed by an explanation of each method.

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def size(self):
        count = 0
        current = self.head

        while current is not None:
            count += 1
            current = current.next_node

        return count

    def insert_front(self, data):
        node = Node(element=data, next_node=self.head)
        self.head = node

    def insert_last(self, data):
        if not self.head:
            self.head = Node(element=data)
        else:
            current_node = self.head
            while current_node.next_node is not None:
                current_node = current_node.next_node
            current_node.next_node = Node(element=data)

    def insert(self, data, position):
        if self.head is None:
            self.head = Node(element=data)
        else:
            if position > self.size() or position < 0:
                raise IndexError
            else:
                if position == 0:
                    self.insert_front(data)
                elif position == self.size():
                    self.insert_last(data)
                else:
                    temp = self.head
                    pos = 0
                    while pos < (position - 1):
                        temp = temp.next_node
                        pos += 1

                    next_node = temp.next_node
                    temp.next_node = Node(element=data, next_node=next_node)

    def remove_first(self):
        if self.head is not None:
            self.head = self.head.next_node

    def remove_last(self):
        if self.head is not None:
            current_node = self.head
            prev = None

            while current_node.next_node is not None:
                prev = current_node
                current_node = current_node.next_node

            if prev is None:
                self.head = None
            else:
                prev.next_node = None

    def remove(self, position):
        if self.head is not None and position == 0:
            self.remove_first()
        elif self.head is not None and position == self.size():
            self.remove_last()
        else:
            if position  self.size():
                raise IndexError
            pos = 0
            current_node = self.head
            next_node = self.head.next_node
            while pos < (position - 1):
                pos += 1
                current_node = next_node
                next_node = current_node.next_node

            current_node.next_node = next_node.next_node

    def fetch(self, position):
        if self.head is None:
            return None
        elif position  self.size():
            raise IndexError
        else:
            current_node = self.head
            pos = 0
            while pos != position:
                pos += 1
                current_node = current_node.next_node

            return current_node.element

__init__

The __init__ method in SinglyLinkedList is small but important. This method creates the self.head variable, which is the first Node in the list. You will notice that we set it to None to indicate an empty list.

def __init__(self):
    self.head = None

size

The size method is used to calculate the size of the linked list. It works by traversing every single node in the list and keeping a count of each node it passes.

def size(self):
    count = 0
    current = self.head

    while current is not None:
        count += 1
        # Advance to the next node by setting
        # current to the next node
        current = current.next_node

    return count

This is a good method to help us understand the mechanics of the linked list. You will notice how each node has a next_node object attached to it. That next_node is either a Node or it is None. None is used to indicate that we have reached the end of the list.

We begin by creating a varaible current and referring it to self.head. Next we start a loop that terminates when current is None. Inside of the loop, we increment count by one, then advance to the next node. When current is None, we are at the end of the list and we can return the count as the size of the list.

insert_front

This method let’s us quickly add an item to the beginning of the linked list.

def insert_front(self, data):
    node = Node(element=data, next_node=self.head)
    self.head = node

We create a new node and set it’s next_node to self.head. Then we just update self.head to refer to the new node. Since the new node is now the head of the list, we have added the item to the front of the list.

insert_last

This method let’s us add an item to the end of the list really quickly.

def insert_last(self, data):
    if not self.head:
        # If this is the first insertion,
        # then we can just make it the head
        self.head = Node(element=data)
    else:
        # We need to advance to the 
        # end of the list
        current_node = self.head
        while current_node.next_node is not None:
            current_node = current_node.next_node
        
        # Now we can grow the list by adding
        # a new node and pointing current_node.next_node at it
        current_node.next_node = Node(element=data)

The first thing to do is check if the list if empty. We know it’s empty if self.head is None. If that’s the case, then just make self.head point at a brand new node.

If the list isn’t empty, then we need to advance to the end of the list and insert the new new node there. It’s not hard to do this. We start by creating a current_node variable and referring it to self.head. Then we just loop until current_node.next_node is None. In each iteration of the loop, we point current_node at current_node.next_node.

Finally we just set current_node.next_node to a new Node object. At this point, current_node referring to the last node in our list, so pointing it’s next_node at the new node is what adds to the list.

insert

The insert method is a little more complicated than the other two inserts. In this case, we are trying to insert a new Node into the middle of the list at an arbitrary position. The mechanics of this isn’t that difficult. What we need to do is find the node at the specified position and store it’s next_node in a variable. Then we create a new Node and set current_node.next_node to the new Node. The new Node’s next_node becomes the old curent_node.next_node.

However, we have a couple of conditions to check for first. For one thing, the list may be empty. The client may try to insert an item at a negative position or a position that is beyond the list’s size. They may also pass in a position that is 0, which means they are inserting in the front of the list. They could also specify a position that is equal to size, which means they could be trying to add to the end of the list. Therefore, our insert method needs to consider all of these cases.

def insert(self, data, position):
    if self.head is None:
        # This is the empty list case
        # Once again, we can just insert at head
        self.head = Node(element=data)
    else:
        if position > self.size() or position < 0:
            # This is the case where they are
            # trying to insert at a negative index
            # or beyond the size of the list.
            # Just raise an exception since that's a
            # programming error on the client's part
            raise IndexError
        else:
            if position == 0:
                # If they are trying to insert at 0, we
                # can use self.insert_front to do the work
                # for us.
                self.insert_front(data)
            elif position == self.size():
                # Likewise, we can just use
                # self.insert_last to handle cases
                # where position is the size() of the list
                self.insert_last(data)
            else:
                # Start with a temp variable
                # to hold the current node
                temp = self.head
                pos = 0 # track the position

                # We actually want to stop at right before
                # the position so that the new node is
                # inserted at the specified position
                while pos < (position - 1):
                    # Advance to the next node
                    temp = temp.next_node
                    # Update position
                    pos += 1

                # Store the next node into a tempory variable
                next_node = temp.next_node
                
                # Now set temp.next_node to a new Node object (and set the
                # now node's next_node to the old next_node)
                temp.next_node = Node(element=data, next_node=next_node)

You'll want to read through the comments of this code to get a better understanding of what is happening. Most of the code here we have seen already and we are just reusing code when possible. The important part to understand is when we do the insertion. We need to traverse the linked list to one node before where we want to insert the node.

Now keep in mind, that the current node, temp, has a next_node variable. We need to store that so that we don't lose the last half of the list. So we store it in a next_node variable. Now to actually perform the insertion, we point temp.next_node to a new Node object. Since the Node's __init__ method can take an option next_node argument, we just pass the next_node that we saved to the __init__ method. Thus, we insert a new node at the expected position.

remove_first

When we want to remove the first element in a linked list, we just need to set head to the next node in the list.

def remove_first(self):
    if self.head is not None:
        self.head = self.head.next_node

The only real thing we need to watch out for is if the list is empty. As long as the list isn’t empty, we just set self.head to self.head.next_node and the first item will get garbage collected by the Python runtime.

remove_last

In the case of removing the last item from the list, we can just traverse to the end of the linked list and set the 2nd to last Node’s next_node to None.

def remove_last(self):
    if self.head is not None:
        # Start at the head
        current_node = self.head
        prev = None

        # Loop 
        while current_node.next_node is not None:
            prev = current_node
            current_node = current_node.next_node

        if prev is None:
            self.head = None
        else:
            prev.next_node = None

Once again, we need to make sure the list isn’t empty. Then we go through the list until we get to the end of the list. While we traverse the list, we keep a reference to the node that is before current_node. It is this node’s next_node that we are setting to None, rather than current_node.next_node. The result will be that current_node is disconnected from the linked list and garbage collected.

We do have to account for the possibility that we are removing all items in the linked list. If prev is none, then we need to set self.head to None, which results in an empty linked list.

remove

This method let’s us remove a node at a specified position. It has the same special cases as it’s insert counter part so we aren’t going to cover them here. The idea is that we are taking a Node out of the list by taking the previous nodes next_node and pointing it at the deleted node’s next_node. The deleted Node gets garbage collected by the runtime.

def remove(self, position):
    if self.head is not None and position == 0:
        # Just use remove_first() remove the first item
        self.remove_first()
    elif self.head is not None and position == self.size():
        # or remove_last() to get rid of the last item
        self.remove_last()
    else:
        # Throw an exception if we are out of bounds
        if position  self.size():
            raise IndexError
        # Track the current position
        pos = 0
        
        # Track the current and next_nodes
        current_node = self.head
        next_node = self.head.next_node

        # Traverse through the list but stop at the node
        # right before the one we are deleting
        while pos < (position - 1):
            pos += 1
            current_node = next_node
            next_node = current_node.next_node
        
        # Now, make current_node.next_node point to
        # next_node.next_node. This removes next_node
        current_node.next_node = next_node.next_node

Once again, the comments will be helpful here. The idea is that we want to remove the node that is in between current_node and next_node.next_node. We can do that very easily by pointing current_node.next_node to next_node.next_node. The next_node object in between the two is severed from the list and garbage collected.

fetch

Our final method is used to retreive items from the list. By now, you have seen plenty of examples on how to traverse the list. In this case, we just traverse the list to the specified position and then return Node.element

def fetch(self, position):
    if self.head is None:
        return None
    elif position  self.size():
        raise IndexError
    else:
        current_node = self.head
        pos = 0
        while pos != position:
            pos += 1
            current_node = current_node.next_node

       return current_node.element

Of course, we need to check for empty lists and perform bounds checking. Otherwise, it’s simple enough to look up the value at the specified position.

Unit Testing

We aren’t going to cover unit testing in detail here, but I did provide an example class that tests this linked list implementation. Not only does it provide an example of Python’s unit testing framework, but it also shows how this class could be used. However, don’t use this class in production code. Python’s list object is a much better choice.

Conclusion

Linked lists are a way to create dynamically expanding collections of data. This tutorial demonstrated how to create a singly linked list. The key to understanding linked lists is to understand how the lists makes use of it’s Nodes. Once you have a solid understanding of how the nodes work, it’s relatively straight forward to make a linked list.

Hangman—PyQt5 (Part 5)

This is the part in a serious of tutorials that describe how to make a Hangman game using Python and PyQt5. You can view the other parts of this series at the following links:

Putting it all together

So far, we have been making panels that inherit from QWidget. Although we tested each of those panels in isolation, the intended use of these panels is to group them together into a main application window. The other job we have to do is wire up our controls. Right now, none of our QPushButtons do anything when they are clicked. This section of the tutorial will demonstrate how to connect click events to functions that handle the event.

For reference, here is the module code

import sys

from PyQt5.QtCore import QCoreApplication
from PyQt5.QtGui import QPixmap
from PyQt5.QtWidgets import (QWidget, QPushButton, QGridLayout, QApplication, QLabel, QHBoxLayout, QVBoxLayout,
                             QMainWindow, QInputDialog)

from hangman import Hangman


class HangmanPanel(QWidget):
    def __init__(self, hangman, frames):
        super().__init__()
        self.hangman = hangman
        self.frame_index = 0
        self.frames = self.create_frames(frames)
        self.label = QLabel(self)
        self.layout = QHBoxLayout(self)
        self.layout.addWidget(self.label)
        self.advance_frame()

    def create_frames(self, frames):
        frm = []
        for f in frames:
            frm.append(QPixmap(f))
        return tuple(frm)

    def advance_frame(self):
        self.label.setPixmap(self.frames[self.frame_index])
        self.frame_index += 1

        if self.frame_index >= len(self.frames):
            self.frame_index = 0

    def reset_hangman(self):
        self.frame_index = 0
        self.advance_frame()


class LetterPanel(QWidget):
    def __init__(self, hangman):
        super().__init__()
        self.hangman = hangman
        self.create_buttons()
        self.grid = QGridLayout(self)
        self.position_buttons()

    def create_buttons(self):
        letters = ('A', 'B', 'C', 'D', 'E',
                   'F', 'G', 'H', 'I', 'J',
                   'K', 'L', 'M', 'N', 'O',
                   'P', 'Q', 'R', 'S', 'T',
                   'U', 'V', 'W', 'X', 'Y', 'Z')
        buttons = []
        for l in letters:
            buttons.append(QPushButton(l, self))
        self.buttons = tuple(buttons)

    def position_buttons(self):
        positions = [(i, j) for i in range(7) for j in range(4)]
        buttons = list(self.buttons)
        buttons.reverse()

        for pos in positions:
            if buttons:
                self.grid.addWidget(buttons.pop(), *pos)

    def activate_all(self):
        for button in self.buttons:
            button.setEnabled(True)


class WinsPanel(QWidget):
    def __init__(self, hangman):
        super().__init__()
        self.hangman = hangman

        self.label = QLabel(self)
        self.label.setText('Wins')

        self.win_label = QLabel(self)
        self.win_label.setText('0')

        self.layout = QHBoxLayout(self)
        self.layout.addWidget(self.label)
        self.layout.addWidget(self.win_label)

    def update_wins(self):
        self.win_label.setText(str(hangman.wins))


class DisplayPanel(QWidget):
    def __init__(self, hangman):
        super().__init__()
        self.hangman = hangman

        self.label = QLabel(self)
        self.word_label = QLabel(self)

        self.layout = QVBoxLayout(self)
        self.layout.addWidget(self.label)
        self.layout.addWidget(self.word_label)


class WordPanel(DisplayPanel):
    def __init__(self, hangman):
        super().__init__(hangman)

        self.label.setText('Current Word')
        self.update_word()

    def update_word(self):
        self.word_label.setText(' '.join(self.hangman.display_letters))


class GuessedLetterPanel(DisplayPanel):
    def __init__(self, hangman):
        super().__init__(hangman)

        self.label.setText("Letters Already Guessed")
        self.update_letters()

    def update_letters(self):
        self.word_label.setText(', '.join(self.hangman.guessed_letters))


class HangmanWindow(QMainWindow):
    def __init__(self, hangman):
        super().__init__()
        self.hangman = hangman

        self.wins_panel = WinsPanel(hangman)
        self.hangman_panel = HangmanPanel(hangman, ['hangman_0.png',
                                                    'hangman_1.png',
                                                    'hangman_2.png',
                                                    'hangman_3.png',
                                                    'hangman_4.png',
                                                    'hangman_5.png',
                                                    'hangman_6.png',
                                                    'hangman_7.png'])
        self.word_panel = WordPanel(hangman)
        self.guessed_letter_panel = GuessedLetterPanel(hangman)
        self.letter_panel = LetterPanel(hangman)

        central_widget = QWidget()
        central_layout = QHBoxLayout(central_widget)

        left_widget = QWidget()
        left_layout = QVBoxLayout(left_widget)
        left_layout.addWidget(self.wins_panel)
        left_layout.addWidget(self.hangman_panel)
        left_layout.addWidget(self.word_panel)
        left_layout.addWidget(self.guessed_letter_panel)

        right_widget = QWidget()
        right_layout = QHBoxLayout(right_widget)
        right_layout.addWidget(self.letter_panel)

        central_layout.addWidget(left_widget)
        central_layout.addWidget(right_widget)

        self.connect_listeners()
        self.setCentralWidget(central_widget)
        self.setWindowTitle('Hangman')
        self.show()

    def connect_listeners(self):
        for button in self.letter_panel.buttons:
            button.clicked.connect(self.on_letter_button_click)

    def on_letter_button_click(self):
        sender = self.sender()

        letter = sender.text()
        sender.setEnabled(False)

        current_guess = hangman.guesses

        self.hangman.guess_letter(letter)
        self.guessed_letter_panel.update_letters()
        self.word_panel.update_word()

        if current_guess < hangman.guesses:
            self.hangman_panel.advance_frame()

        if hangman.check_win():
            self.wins_panel.update_wins()
            self.show_win()
        elif hangman.check_lose():
            self.show_lose()

    def show_win(self):
        items = ('Yes', 'No')
        item, ok = QInputDialog.getItem(self, 'You Win! Play again?', 'Choice:', items, 0, False)
        if ok and item == 'Yes':
            self.reset_game()
        else:
            QCoreApplication.instance().quit()

    def show_lose(self):
        items = ('Yes', 'No')
        item, ok = QInputDialog.getItem(self, 'You Lost! Play again?', 'Choice:', items, 0, False)
        if ok and item == 'Yes':
            self.reset_game()
        else:
            QCoreApplication.instance().quit()

    def reset_game(self):
        hangman.start_game()
        self.wins_panel.update_wins()
        self.hangman_panel.reset_hangman()
        self.word_panel.update_word()
        self.guessed_letter_panel.update_letters()
        self.letter_panel.activate_all()


if __name__ == '__main__':
    app = QApplication(sys.argv)
    hangman = Hangman('words.txt', 6)
    win = HangmanWindow(hangman)
    sys.exit(app.exec_())

HangmanWindow

HangmanWindow is our main application window. One difference you will notice right off of the bat is that this class inherits from QMainWindow instead of QWidget.

class HangmanWindow(QMainWindow):
    def __init__(self, hangman):
        super().__init__()
        self.hangman = hangman

        self.wins_panel = WinsPanel(hangman)
        self.hangman_panel = HangmanPanel(hangman, ['hangman_0.png',
                                                    'hangman_1.png',
                                                    'hangman_2.png',
                                                    'hangman_3.png',
                                                    'hangman_4.png',
                                                    'hangman_5.png',
                                                    'hangman_6.png',
                                                    'hangman_7.png'])
        self.word_panel = WordPanel(hangman)
        self.guessed_letter_panel = GuessedLetterPanel(hangman)
        self.letter_panel = LetterPanel(hangman)

        central_widget = QWidget()
        central_layout = QHBoxLayout(central_widget)

        left_widget = QWidget()
        left_layout = QVBoxLayout(left_widget)
        left_layout.addWidget(self.wins_panel)
        left_layout.addWidget(self.hangman_panel)
        left_layout.addWidget(self.word_panel)
        left_layout.addWidget(self.guessed_letter_panel)

        right_widget = QWidget()
        right_layout = QHBoxLayout(right_widget)
        right_layout.addWidget(self.letter_panel)

        central_layout.addWidget(left_widget)
        central_layout.addWidget(right_widget)

        self.connect_listeners()
        self.setCentralWidget(central_widget)
        self.setWindowTitle('Hangman')
        self.show()

    def connect_listeners(self):
        for button in self.letter_panel.buttons:
            button.clicked.connect(self.on_letter_button_click)

    def on_letter_button_click(self):
        sender = self.sender()

        letter = sender.text()
        sender.setEnabled(False)

        current_guess = hangman.guesses

        self.hangman.guess_letter(letter)
        self.guessed_letter_panel.update_letters()
        self.word_panel.update_word()

        if current_guess < hangman.guesses:
            self.hangman_panel.advance_frame()

        if hangman.check_win():
            self.wins_panel.update_wins()
            self.show_win()
        elif hangman.check_lose():
            self.show_lose()

    def show_win(self):
        items = ('Yes', 'No')
        item, ok = QInputDialog.getItem(self, 'You Win! Play again?', 'Choice:', items, 0, False)
        if ok and item == 'Yes':
            self.reset_game()
        else:
            QCoreApplication.instance().quit()

    def show_lose(self):
        items = ('Yes', 'No')
        item, ok = QInputDialog.getItem(self, 'You Lost! Play again?', 'Choice:', items, 0, False)
        if ok and item == 'Yes':
            self.reset_game()
        else:
            QCoreApplication.instance().quit()

    def reset_game(self):
        hangman.start_game()
        self.wins_panel.update_wins()
        self.hangman_panel.reset_hangman()
        self.word_panel.update_word()
        self.guessed_letter_panel.update_letters()
        self.letter_panel.activate_all()

This class is much larger than our other panel classes for the simple reason that it creates all of our panels and then connects the controls to event handler functions.

__init__

We begin with the __init__ method. There is a lot going on in this method so we are going to take it a little bit at a time.

def __init__(self, hangman):
    super().__init__()
    self.hangman = hangman

    self.wins_panel = WinsPanel(hangman)
    self.hangman_panel = HangmanPanel(hangman, ['hangman_0.png',
                                                'hangman_1.png',
                                                'hangman_2.png',
                                                'hangman_3.png',
                                                'hangman_4.png',
                                                'hangman_5.png',
                                                'hangman_6.png',
                                                'hangman_7.png'])
    self.word_panel = WordPanel(hangman)
    self.guessed_letter_panel = GuessedLetterPanel(hangman)
    self.letter_panel = LetterPanel(hangman)

    central_widget = QWidget()
    central_layout = QHBoxLayout(central_widget)

    left_widget = QWidget()
    left_layout = QVBoxLayout(left_widget)
    left_layout.addWidget(self.wins_panel)
    left_layout.addWidget(self.hangman_panel)
    left_layout.addWidget(self.word_panel)
    left_layout.addWidget(self.guessed_letter_panel)

    right_widget = QWidget()
    right_layout = QHBoxLayout(right_widget)
    right_layout.addWidget(self.letter_panel)

    central_layout.addWidget(left_widget)
    central_layout.addWidget(right_widget)

    self.connect_listeners()
    self.setCentralWidget(central_widget)
    self.setWindowTitle('Hangman')
    self.show()

As always, we start with calling super().__init__() to intialize the Qt window. Our next job is to assign the hangman variable to self.hangman. Doing this allows use to use the Hangman class to control the application’s logic.

Our next job is create our panels. We create a WinPanel (TODO: Link) (self.win_panel) and then we create a HangmanPanel (TODO: Link) (assign it to self.hangman_panel) and supply it with the file names of our frames. Then we create a WordPanel (TODO: Link) (assign it to self.word_panel), then a GuessedLetterPanel (self.guessed_letter_panel), and a LetterPanel (TODO: Link) (self.letter_panel).

Now, we can’t simply add these widgets to our window. QMainWindow uses a centeral widget that contains all of our widgets. We create a central_widget object and then on the following line assign a QHBoxLayout to this widget. Next we create two more nested QWidgets. The first widget is left_widget. This widget gets a QVBoxLayout and then we add self.win_panel (WinPanel), self.hangman_panel (HangmanPanel), self.word_panel (WordPanel), and self.guessed_letter_panel (GuessedLetterPanel) to this widget. That makes everything but the letter buttons appear on the left hand side of the screen.

Now we make another QWidget called right_widget. This widget gets a QHBoxLayout and then we added self.letter_panel (LetterPanel) to this widget. Now that we have our left_widget and right_widget, we can add them both to central_widget. The two widgets will stack up left to right.

Now that we have layed our screen, we call self.connect_listeners() to wire up the buttons to their event handling code. We then call setCentralWidget and pass central_widget to it. This places all of the controls on the QMainWindow. The next line of code sets the title of the window to “Hangman”. Finally, we call self.show() to actually show the window.

connect_listeners

Right now we have 26 QPushButtons on our window that don’t do anything. We are going to address that issue in this method.

def connect_listeners(self):
    for button in self.letter_panel.buttons:
        button.clicked.connect(self.on_letter_button_click)

If you remember from LetterPanel (TODO: Link), LetterPanel has a tuple of 26 buttons. QPushButton maintains a clicked object that has a connect method. The clicked is the name of the event (which fires when the user clicks on the button). The connect is a method that takes a Callable, (functions for the most part, but can be lambdas or classes that implement Callable). In our case, we are going to connect a click to our class’s on_letter_button_click method.

on_letter_button_click

This function gets called anytime we we click on a button. We connected this function to QPushButton’s clicked event in the connect_listeners function.

def on_letter_button_click(self):
    sender = self.sender()

    letter = sender.text()
    sender.setEnabled(False)

    current_guess = hangman.guesses

    self.hangman.guess_letter(letter)
    self.guessed_letter_panel.update_letters()
    self.word_panel.update_word()

    if current_guess < hangman.guesses:
        self.hangman_panel.advance_frame()

    if hangman.check_win():
        self.wins_panel.update_wins()
        self.show_win()
    elif hangman.check_lose():
        self.show_lose()

The first thing we need to do is get the source of the click event. We can get this using QMainWindow's sender() method. The next thing to do is get the letter. Remember that we set the label of each QPushButton to a letter in the alphabit. Therefore, we can get the guessed letter but using the text() method on QPushButton. Next we call sender.setEnabled to false so that they can't guess the same letter twice.

Now it's time for our HangmanObject to do some work. We start by grabbing the current number of wrong guesses but accessing hangman.guesses. On the next line, we pass the guessed letter to hangman.guess_letter. It's going to do the work of making a determination if the letter was a correct guess or not.

After guessing a letter, we call self.guessed_letter_panel.update_letters() to update the guessed letter portion of the UI. Then we call self.word_panel.update_word() to update the current word portion of the UI.

Next we need to see if we need to show the man in hangman getting hanged. We compare the current_guess against hangman.guesses. If they guessed wrong, then hangman.guessess will be larger than current_guess. Otherwise the are equal. If they guessed wrong, we update the HangmanPanel of the UI by calling self.hangman_panel.advance_frame()

Finally we need to check if the user has won or lost the game. We use hangman.check_win to see if they have won. If they have won, we need to update the WinsPanel by calling self.wins_panel.update_wins() and then call self.show_win() to notify the user that they have won.

Alternatively, the user may have lost the game. If that's the case, we call self.show_lose()

show_win

If the user wins, we want to show a dialog window that tells them they have won. It looks like this screen shot
wins copy.png
Here is the code for this function

def show_win(self):
    items = ('Yes', 'No')
    item, ok = QInputDialog.getItem(self, 'You Win! Play again?', 'Choice:', items, 0, False)
    if ok and item == 'Yes':
        self.reset_game()
    else:
        QCoreApplication.instance().quit()

This function starts out by creating a tuple that contains the two choices we are presenting to the user. Then we call QInputDialog.getItem to get the users choice. This creates a dialog box that is populated with the choices ‘Yes’ or ‘No’. It returns a tuple that we unpack into the variables item and ok. Item is the users choice and ok if if they clicked the Ok button rather than cancel.

If they clicked ok and selected Yes, we call self.reset_game() to start a new game. Otherwise we use QCoreApplication.instance().quit() to exit the application.

show_lose

This code does the exact same thing as show_win but it shows a different error message. Here is the code, but there isn’t anything new to explain.

def show_lose(self):
    items = ('Yes', 'No')
    item, ok = QInputDialog.getItem(self, 'You Lost! Play again?', 'Choice:', items, 0, False)
    if ok and item == 'Yes':
        self.reset_game()
    else:
        QCoreApplication.instance().quit()

reset_game

The final function in this class is the reset_game function. It does the job of reseting the UI and Hangman to their default states so that we can play a new game.

def reset_game(self):
    hangman.start_game()
    self.wins_panel.update_wins()
    self.hangman_panel.reset_hangman()
    self.word_panel.update_word()
    self.guessed_letter_panel.update_letters()
    self.letter_panel.activate_all()

We call hangman.start_game to reset Hangman. We also update the WinsPanel portion of the UI. Next we need to update the HangmanPanel to it’s first frame by calling reset_hangman().

Since Hangman has picked a new word at this point, we need to call WordPanel.update_word() to replace the word with dashes again. We also need to clear out the guessed letters so we call GuessedLetterPanel.update_letters() to erase all of the guessed letters. Finally we have to enable all of the QPushButtons so use LetterPanel.activate_all() to re-enable all of our QPushButtons.

Run the program

We run the program like this

if __name__ == '__main__':
    app = QApplication(sys.argv)
    hangman = Hangman('words.txt', 6)
    win = HangmanWindow(hangman)
    sys.exit(app.exec_())

We begin by initializing Qt by creating a QApplication object and passing the command line arguments to it. Next we create a Hangman object and pass the files with our word bank and the number of allowed guesses to it. The next line creates our HangmanWindow. Finally we call sys.exit and pass the QApplication.exec_() function to it so that the application exits properly.

Conclusion

We came a long way in this tutorial. We had a lot of practice with object orientated programming (OOP) and we got a tour of PyQt5. This program read a file line by line, joined strings, and even handled GUI event programming. Here is alink to the complete project! Enjoy playing Hangman!