Kotlin Koan—Part 13

Kotlin has nice extensions on Collection classes. JDK has provided developers a way to sort collections for a long time now, but often times, it’s done with external classes such as Collections. This puts us in a odd position of using procedural programming when performing operations such as sorting a collection.

A more OOP approach would be to have a sort method directly on a Collection as opposed to passing a collection to an external class with a static method. Kotlin extends Java collections by using its extension feature to complement the collection classes found in JDK.

Here is an example that demonstrates how to sort an ArrayList in Java.

fun task12(): List {
    val lst =  arrayListOf(1, 5, 2)
    lst.sortDescending()
    return lst
}

If all fairness to Java, JDK 8 did address this issue. Here is the equivalent Java code that does the same thing.

public class CollectionSort {
    public List sortList(){
        List lst = Arrays.asList(1, 5, 2);
        lst.sort(Comparator.reverseOrder());
        return lst;
    }
}

I’m not going to complain too much about the Java 8 syntax, but I think sortDescending() and sortAcending() is more readable than Comparator.natualOrder() and Comparator.reverseOrder(). However, the Kotlin approach is much superior to JDK 7 and earlier.

You can read the previous post here.

Advertisements

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 7

This portion of the Kotlin Koans showed off a really boss feature of the language: Data Classes. These are special classes whose primary purpose is to hold data.

Here is a Java class that we start with that’s taken directly from the tutorial.

public class Person {
        private final String name;
        private final int age;

        public Person(String name, int age) {
            this.name = name;
            this.age = age;
        }

        public String getName() {
            return name;
        }

        public int getAge() {
            return age;
        }
    }

It’s not a special class. This is a class with a primary constructor, getters/setters and two private variables. It’s also one of my biggest complaints about the Java language. I can do the same thing in Python like this.

class Person:
    def __init__(self, name=None, age=None):
        self.name = name
        self.age = age

Four lines of code in Python. In all fairness to Java, would could just declare name and age to be public variables, but doing so is not only frowned upon, but many Java libraries look for getter/setter method to access a property of a Java bean. Basically speaking, even though we could allow for public access of a Java property, it’s not really practical at this point.

There is a Java library called Lombok that does a lot to solve this problem.

@Data
public class Person {
    private String name;
    private String age;
}

Lombok has been the solution I have used for most of my projects. It’s not perfect however. For example, I can’t use the @Data annotation to make a read only class. That forces me to use a mix of Lombok annotations or define a stereotype annotation. It’s not a huge problem, but it’s still something to think about.

Kotlin data classes take this to a whole other level. Here is the same class in Kotlin.

data class Person(val name: String, val age: Int)

That’s it! One line of code!!! With this single line of code, we get our two properties, it’s getter methods, hashcode, equals, toString() and a constructor. The class is immutable because the variables are declared with the val keyword. We can make the class mutable by using var instead of val. Finally, we aren’t losing our ability to work with existing Java libaries.

I really don’t see how it can get any better than this. I have used data classes countless times when working with ORM libraries such as hibernate. I’d say 95% of these classes are classes that just hold data and map to a table in the database. Although any IDE can generate constructors, getters/setters, equals, and hashcode, and toString, let’s face it, it’s even better to have this built directly into the language itself.

You can click here to see Part 6

Kotlin Spring MVC

Kotlin makes Spring MVC projects a total breeze. This is a simple web application that combines a few different Kotlin techniques into a Spring Boot project. Here are few screen shots of the finished example and then we will dive into the code that makes it possible.

 

package com.stonesoupprogramming.kotlinspringmvc

import org.springframework.boot.SpringApplication
import org.springframework.boot.autoconfigure.SpringBootApplication
import org.springframework.stereotype.Controller
import org.springframework.ui.Model
import org.springframework.web.bind.annotation.RequestMapping
import org.springframework.web.bind.annotation.RequestMethod

@SpringBootApplication //This performs magic under the hood to launch a spring web application
class KotlinSpringMvcHelloWorldApplication

//Entry point to the application
fun main(args: Array) {
    SpringApplication.run(KotlinSpringMvcHelloWorldApplication::class.java, *args)
}

//This is a class that we are using for our form
//Kotlin let's us one line it!
data class Registration(var firstName: String = "", var lastName: String = "")

@Controller //Tells Spring this is a controller class
@RequestMapping("/") //Tells Spring to handle web requests at the root
class Controller {

    //This function will handle HTTP Get Requests
    @RequestMapping(method = arrayOf(RequestMethod.GET))
    fun doIndexGet(model: Model): String{
        //Send a new instance of Registration back to the view
        model.addAttribute("registration", Registration())

        //Render the index.html page
        return "index"
    }

    //This method handles HTTP Post
    @RequestMapping(method = arrayOf(RequestMethod.POST))
    fun doIndexPost(formParams: Registration, model: Model): String {
        //Send a greeting message to the view
        model.addAttribute("greet", "Hello ${formParams.firstName} ${formParams.lastName}")

        //Render the greet.html page
        return "greet"
    }

    //This handles GET requests for /greet.html
    @RequestMapping(path = arrayOf("/greet"), method=arrayOf(RequestMethod.GET))
    fun doGreetGet(): String = "greet" //Just tell it to render the greet.html page
}

Initializing the Application

Many readers are no doubt familiar with Spring Boot. Our first class in this project appears on line 11 with this code.

@SpringBootApplication //This performs magic under the hood to launch a spring web application
class KotlinSpringMvcHelloWorldApplication

Kotlin focuses on begin concise and in this is literally an empty class that is annotated with @SpringBootApplication. The annotation performs some Spring magic that does the job of initializing the Spring environment for us. Our next segment of code is the entry point to the application.

//Entry point to the application
fun main(args: Array) {
    SpringApplication.run(KotlinSpringMvcHelloWorldApplication::class.java, *args)
}

Once again, there isn’t much code here, but a lot is happening under the hood that is invisible to us. We are calling the static SpringApplication.run function and passing into it the KotlinSpringMvcHelloWorldApplication class along with the supplied command line arguments. Once again, we will leave it up to Spring to prepare our environment.

Data Class

Many Java developers have no doubt made classes the are simply holders for properties along with a constructor, getters and setters, hashcode(), equals(), and toString(). Two common applications of such classes are ORM model classes and classes that can be passed back to the view. In this case we are making a class that gets passed to the view, but we are going to define it using Kotlin’s data class. The code for such a class is extremely brief.

data class Registration(var firstName: String = "", var lastName: String = "")

Using this single line of code, we make a Registration class with two properties, a default constructor, and an overloaded constructor. The class comes packed with hashcode(), equals(), toString() and when used in Java code, it will have getters and setters. We are going to pass this code back to the view in the controller class.

Controller

The Controller is another portion of Spring MVC. We use it to map HTTP requests to the appropriate methods in the class. Spring will also inject a Model class when needed so that we can pass data back to the view. Here is the controller class written in Kotlin.

@Controller //Tells Spring this is a controller class
@RequestMapping("/") //Tells Spring to handle web requests at the root
class Controller {

    //This function will handle HTTP Get Requests
    @RequestMapping(method = arrayOf(RequestMethod.GET))
    fun doIndexGet(model: Model): String{
        //Send a new instance of Registration back to the view
        model.addAttribute("registration", Registration())

        //Render the index.html page
        return "index"
    }

    //This method handles HTTP Post
    @RequestMapping(method = arrayOf(RequestMethod.POST))
    fun doIndexPost(formParams: Registration, model: Model): String {
        //Send a greeting message to the view
        model.addAttribute("greet", "Hello ${formParams.firstName} ${formParams.lastName}")

        //Render the greet.html page
        return "greet"
    }

    //This handles GET requests for /greet.html
    @RequestMapping(path = arrayOf("/greet"), method=arrayOf(RequestMethod.GET))
    fun doGreetGet(): String = "greet" //Just tell it to render the greet.html page
}

The first line is the @Controller annotation. Our Spring boot environment has component scanning enabled, so we only need to annotate our controller class to make Spring aware of it’s existence. On line 2, we have the @RequestMapping annotation that tells Spring that the default request mapping for this class is the root of the web application (‘/’). The class contains three functions: doIndexGet, doIndexPost, and doGreetGet. Let’s talk about each in detail.

doIndexGet

This method is annotated with @RequestMapping and it handles HTTP Get requests to the ‘/’ endpoint. The function has one parameter, model : Model, and it returns a String. The model parameter is injected by Spring.

On the first line of the function, we add a “registration” attribute to the model with a new instance of Registration. Notice that in Kotlin, we do not need the new keyword and since we define default arguments for our Regsitration class, we do not need to supply an parameters. The function ends by returning the String “index” which will tell Spring and Thymeleaf (which is our template engine) which page to render.

doIndexPost

This function handles HTTP post methods as indicated by @RequestMapping(method = arrayOf(RequestMethod.POST)). It’s two arguments, formParams: Registration, and model : Model, are injected into this method by Spring. In the view, we have the following http form.
form copy
Inside of this html code you will see things like ${registration}, th:field=”*{firstName}”, and th:field=”*{lastName}”. These special tags map these input fields to the properties our Registration object that we sent back to the view in the doIndexGet function. When we click on the submit button the setter methods of the registration object are called and the values of the input boxes in the form are inserted into Registration::firstName and Registration::lastName. Then the Registration object is sent back to the server and routed to our doIndexPost method.

Once we are inside of the doIndexPost method, we can add a String to our model class.

model.addAttribute("greet", "Hello ${formParams.firstName} ${formParams.lastName}")

The second argument is the portion that I wish to discuss. Kotlin has String templating which lets us build a String using inline variables. Thus the ${formParams.firstName} will get replaced with the first name entered by the user and ${formParams.lastName} gets replaced with the last name the user entered. Then the function returns with the String “greet” which tells the web application to show the greet page.

doGreetGet

This final function is the shortest. It’s simply a function that handles the request mapping for HTTP Get when the browser navigates to the greet page. However, Kotlin let’s us define functions inline, so it’s worth talking about.

@RequestMapping(path = arrayOf("/greet"), method=arrayOf(RequestMethod.GET))
fun doGreetGet(): String = "greet" //Just tell it to render the greet.html page

All this code does is return the string “greet” so that the web application knows to render the greet.html page. Since it’s literally just returning one value, we can legally write String = “greet” in Kotlin and omit the method body.

Web Pages

For reference purposes, I have included screen shots of the web pages (they don’t seem to render properly when I use the code formatter 😦 sorry readers)!

index.html

index copy
We have already discussed how the Registration object is bound to the html form on this page. However, it’s worth pointing out that this page uses Bootstrap for page layout. Most of the code in this page was auto-generated by Intellij also, which has world class support for Bootstrap.

greeting.html

greet_page copy
This is the other page that get’s returned by the controller after the user enters their name. We built a String in doPostIndex and mapped it to the key “greet” in the model. On this page, we can show that custom greeting by using th:text=”${greet}”. The template engine is smart enough to insert this greeting between the header tags.

Source

You can get the complete source code for this project from my Bitbucket page. Happy coding!

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.