Functions—Python

All computer programming languages allow developers to seperate code into reuseable pieces of code called functions. Functions are critical because they allow us to generalize pieces of work into a block of code and reuse that code as many times as needed. When designed well, functions improve code readability by cutting down on the length of the code. We can also debug our code easier because we only have to look in on place for a bug rather than several places.

Demonstration

Let’s begin with a function demonstration.

# A function
def nested_func():
    print('Inside of nested_func()')
    return 'value'


# A function
def func():
    print('Inside of func()')

    val = nested_func()
    print('Back in func(). nest_func() returned {}'.format(val))


# Not a function
if __name__ == '__main__':
    print('Outside of all functions. Calling func()')
    func()
    print('Back from our functions')

This is a block of code that creates two functions. When we run the code, we get this output.

Outside of all functions. Calling func()
Inside of func()
Inside of nested_func()
Back in func(). nest_func() returned value
Back from our functions

Computer programs normally run from top to bottom one line at a time. In the case of this program, the program doesn’t start until we reach if __name__ == '__main__':. This is because Python runtime isn’t going to execute the code inside of nest_func() or func() until the functions are called.

When the code reaches 17, it executes the print statement. The next line, 18, is our first call to a function. We named our function func() in this case. Calling func() causes the program’s execution to jump up to line 9. Once we are at line 9, Python executes the print statement and then moves onto the next line in the function, line 11.

Line 11 creates a variable called val and then calls our next function, nested_func(). The nested_func() function is a function that returns a value. Program execution moves to line 3. Line 3 executes the print statement, and then line 4 returns a String value. The program execution returns back to line 11.

At this point, the variable val has a value stored in it. The program’s execution goes to line 12 and the print statement is executed. Now the program exits the func() function and control returns to line 19. The program executes the final print statement found on line 19 and then exits.

Defining a function

You create functions in Python by using the def keyword followed by the name of the function. After the name of the function, you have an opening parentheses ( followed by a closing parenthese ). You can place any number of variables inside of the parentheses. Here is an example

# Function with arguments
def func(val, val2):
    print(val)
    print(val2)

# Calling the function
func('Hello', 'World')

The name of this function is func. It has two arguments, val and val2. After the colon, you can include any number of statements you would like inside of the function. The function is now a seperate unit of code at this point. This function get’s called by func('Hello', 'World'). Anytime the Python interpreter something like this, it will execute all of the statements inside of func. We do not have to use ‘Hello’ or ‘World’ as the argument either. It’s perfectly ok to do something like func(47, 'Thunderbiscuit').

Optional Arguments

We can specify default values to our functions.

def some_func(arg1='Mickey'):
    print(arg1)

# Prints 'Mouse'
some_func('Mouse')

# Prints 'Mickey'
some_func()

Since this function has optional arguments, we can either pass it our own argument, or we can just use the default. The first call passes ‘Mouse’ to some_func, in which case arg1 = ‘Mouse’. The second call does not specify a value, so arg1 gets the default ‘Mickey’ value.

Lists—Python

Lists are a sequence type object that Python provides to us for grouping data together into a single variable. Let’s consider a common application of a list before we go into details.

names = ['Bob Belcher',
         'Linda Belcher',
         'Tina Belcher',
         'Gene Belcher',
         'Louise Belcher']
for name in names:
    print (name)

This code creates a list called names and populates it with five names. Then it prints the names to the console. We could accomplish the same output by using this code.

bob = 'Bob Belcher'
linda = 'Linda Belcher'
tina = 'Tina Belcher'
gene = 'Gene Belcher'
louise = 'Louise Belcher'

print(bob)
print(linda)
print(tina)
print(gene)
print(louise)

A quick comparison shows that the first example is not only much easier to read, but it is also more maintainable. If we want to print additional names, we only need to add them to the names list in the first example. However, in the second example, we need to add new name variable and another print statement. This may not seem like a big deal with six names, but obviously 6,000 is a much different case.

It’s for this reason that almost every programming language provides some sort of a collection object. List is one such data type that Python provides out of the box. Let’s look at common list operations.

Check if item is in the list

We may want to check if a list has a certain item.

names = ['Bob Belcher',
         'Linda Belcher',
         'Tina Belcher',
         'Gene Belcher',
         'Louise Belcher']
if 'Bob Belcher' in names:
    print('Found Bob')

This code prints ‘Found Bob’ because 'Bob Belcher' in names returns True.

Check if item is not in list

We can also check if a list does not have an item.

names = ['Bob Belcher',
         'Linda Belcher',
         'Tina Belcher',
         'Gene Belcher',
         'Louise Belcher']
if 'Teddy' not in names:
    print('No Teddy here!')

This code would print ‘No Teddy here!’ because 'Teddy' not in names is True. Our names list does not have ‘Teddy’

Combine lists

We can add two lists together (called concatenation) using the + operator.

belchers = ['Bob Belcher',
            'Linda Belcher',
            'Tina Belcher',
            'Gene Belcher',
            'Louise Belcher']

pestos = ['Jimmy Pesto',
          'Jimmy Pesto Jr.',
          'Andy Pesto',
          'Ollie Pesto']

family_frackus = belchers + pestos
print(family_frackus)

This code will print all of the names to standard out when run.

Accessing items

Lists use the index operator access items

belchers = ['Bob Belcher',
            'Linda Belcher',
            'Tina Belcher',
            'Gene Belcher',
            'Louise Belcher']
print(belchers[0])
print(belchers[3])

Keep in mind that lists are 0 based, so belchers[0] is ‘Bob Belcher’ while belchers[3] is ‘Gene Belcher’

Add item to list

We can add an item to a list using the append() method.

belchers = ['Bob Belcher',
            'Linda Belcher',
            'Tina Belcher',
            'Gene Belcher',
            'Louise Belcher']
belchers.append('Teddy')
print(belchers[5])

Remove item from a list

We use the del operator to remove an item from a list

belchers = ['Bob Belcher',
            'Linda Belcher',
            'Tina Belcher',
            'Gene Belcher',
            'Louise Belcher']
del belchers[0]

Using del belchers[0] removes ‘Bob Belcher’ from the list.

Replace item in a list

We can replace an item in a list by specifying the index and assigning a new value to it.

belchers = ['Bob Belcher',
            'Linda Belcher',
            'Tina Belcher',
            'Gene Belcher',
            'Louise Belcher']
belchers[0] = 'Mort'

The code belchers[0] = 'Mort' replaces ‘Bob Belcher’ with ‘Mort’

Length of the list

We get the length of the list using len.

belchers = ['Bob Belcher',
            'Linda Belcher',
            'Tina Belcher',
            'Gene Belcher',
            'Louise Belcher']
print(str(len(belchers))) 

The print(str(len(belchers))) prints 5 to the console.

Conclusion

We can do a lot more with lists than what was discussed in this post. Make sure you check out the Python documentation for a complete list of features!

9 Anti-Patterns Every Programmer Should Be Aware Of

I thought this was a worthwhile read for even experienced developers. It provides a good check list of what not to do!

A healthy dose of self-criticism is fundamental to professional and personal growth. When it comes to programming, this sense of self-criticism requires the ability to detect unproductive or counter-productive patterns in designs, code, processes, and behaviour. This is why a knowledge of anti-patterns is very useful for any programmer. This article is a discussion of anti-patterns that I have found to be recurring, ordered roughly based on how often I have come across them, and how long it took to undo the damage they caused.

Some of the anti-patterns discussed have elements in common with cognitive biases, or are directly caused by them. Links to relevant cognitive biases are provided as we go along in the article. Wikipedia also has a nice list of cognitive biases for your reference.

And before starting, let’s remember that dogmatic thinking stunts growth and innovation so consider the list as a set of guidelines…

View original post 3,169 more words

Strings—Python

Python has native support for Strings (which is basically text). Many computer programs need to process text data and Python’s string type has powerful features to make the lives of developers easy!

String Literals

Here are a few examples of how to create strings in Python using literals.

sq = 'String made with Single Quotes'
dq = "String made with double quotes"
tq = """String with triple quotes"""

Double quote strings let you embed an apostrope character without escaping it. So you can write “I’m a cat” as a string literal in Python. Triple quote strings allow white space and line breaks in the string.

Individual Characters

Python strings support the index operator, so you can access characters in a string using [n] where n is the position of the character you wish to access. Here are a few ways to process strings by individual characters.

kitties = 'I like kitties'

# Access by index
for i in range(0, len(kitties)):
    print(kitties[i])

# Access with iteration
for c in kitties:
    print (c)

Useful Methods

The Python string class has many useful methods. You can view them all at Python documentation. Here are some of the ones I use the most.

islower()

This checks if a string is all lower case characters.

kitties = 'i like kitties'
if kitties.islower():
    print(kitties, ' is lower case')
else:
    print(kitties, ' is not lower case')

lower()

Python Strings are immutable, but you can use lower to convert a string to all lower case.

kitties = 'I like kitties'

if not kitties.islower():
    kittens = kitties.lower()
    print(kittens) 

isupper()

This method tests if a string is all upper case.

kitties = 'I LIKE KITTIES'

if kitties.isupper():
    print(kitties, ' is upper case')
else:
    print(kitties, ' is not upper case')

upper()

This method converts the string to upper case.

kitties = 'i like kitties'

if not kitties.isupper():
    cat = kitties.upper()
    print(cat)

isnumeric()

Checks if the strings is a numbers. This is useful if you want to convert a string to an int.

number_str = '3'

if number_str.isnumeric():
    number = int(number_str)

format()

This is useful for using a generic string that allows you to replace {} with values.

fm = 'I have {} kitties'
print(fm.format(3')
# Prints: I have 3 kitties

Numbers—Python

Computer programs need to track numberic data every single day. You may want to track balances in bank accounts, scientific numbers, or just counters. Python gives us a wide variety of numeric processing types. Here are some of the more common ones:

  • Integers
  • Floats
  • Boolean
  • Decimals
  • Fractions

Integers

Integers are whole numbers that are either positive or negatives. Unlike langues such as Java or C++ (or Python 2.x) Python does not distinguish between regular and long integers. Here are some examples of declaring integers

positiveNumber = 123456
negativeNumber = -111

Floating Point Numbers

Floating point numbers are numbers that have decimal points or numbers in scientific notations. They can be positive or negative.

dollar = 3.15
pi = 3.14159
sci = 8.2e10

Octal, hex, binary

Here are examples of numbers in octal, hexadecimal, and binary numbers.

oct = 0o237
hex = Ox9F
binary = Ob10011111

Decimals and Fractions

Python provides us with Decimal and Fraction data types which maintainer percision with decimal points. A loss of percision may not get noticed in trival programs, but when working with big datasets, the loss of percision can introduce major bugs in the program.

d = Decimal('1.59')
f = Fraction(1, 3) # Numerator / denominator

Boolean

Booleans hold true and false values.

b = True
f = False

For more information

You can learn more by visiting the python documentation.

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.

Kotlin Koans—Part 1

I read that Android is going to officially support Kotlin now. Last year, I bought the IntelliJ IDE and one of the first things I noticed was that the IDE offered to make Kotlin classes. I had never done anything with Kotlin but I often wondered about it. It looked interesting to me, but now that Google has thrown in with Kotlin, I decided to give it try for myself.

This is the first in a series of posts where I’m going to work through the tutorials provided on kotlinlang.org. This first post was on the very first tutorial, which is the classical ‘Hello World’ style problem.

I started by cloning the github project that they give you. Here is what I got presented with.

package i_introduction._0_Hello_World

import util.TODO
import util.doc0

fun todoTask0(): Nothing = TODO(
    """
        Introduction.

        Kotlin Koans project consists of 42 small tasks for you to solve.
        Typically you'll have to replace the function invocation 'todoTaskN()', which throws an exception,
        with the correct code according to the problem.

        Using 'documentation =' below the task description you can open the related part of the online documentation.
            Press 'Ctrl+Q'(Windows) or 'F1'(Mac OS) on 'doc0()' to call the "Quick Documentation" action;
            "See also" section gives you a link.
            You can see the shortcut for the "Quick Documentation" action used in your IntelliJ IDEA
            by choosing "Help -> Find Action..." (in the top menu), and typing the action name ("Quick Documentation").
            The shortcut in use will be written next to the action name.

        Using 'references =' you can navigate to the code mentioned in the task description.

        Let's start! Make the function 'task0' return "OK".
    """,
    documentation = doc0(),
    references = { task0(); "OK" }
)

fun task0(): String {
    return todoTask0()
}

My job was to make the function task0 was to make it return “OK”. It wasn’t too painful. I just had to update task0

fun task0(): String {
    return "OK"
}

Once I did this, I ran the unit test that they give you to check if you did the task properly. This was easy to do in IntelliJ. The IDE provides you with a button to click on to run the test.
run_test
After I ran the test, I got the output the test was expecting.

Recursion Example — Walking a file tree

Many developers use Python as a platform independent scripting language to perform file system operations. Sometimes it’s necessary to walk through a file system. Here is one way to navigate a file system recusively. (Of course, Python has libaries that do this!)

import os

def walk_fs(start_dir):
    # Get a list of everything in start_dir
    contents = os.listdir(start_dir)

    # This stores the output
    output = []

    # Loop through every item in contents
    for f in contents:
        # Use os.path.join to reassmble the path
        f_path = os.path.join(start_dir, f)

    # check if f_path is directory (or folder)
    if os.path.isdir(f_path):
        # Make recusive call to walk_fs
        output = output + walk_fs(f_path)
    else:
        # Add the file to output
        output.append(f_path)

    # Return a list of files in the directory
    return output

if __name__ == '__main__':
    try:
        result = walk_fs(input('Enter starting folder => '))
        for r in result:
            print(r)
    except FileNotFoundError:
    print('Not a valid folder! Try again!')

The key to this is to begin by using os.listdir, which returns a list of every item in a directory. Then we can loop through each item in contents. As we loop through contents, we need to reassemble the full path because f is only the name of the file or directory. We use os.path.join because it will insert either / (unix-like systems) or \ (windows) between each part of the path.

The next statement checks if f_path is a file or directory. The os.path.isdir function is True if the item is a directory, false otherwise. If f_path is a folder, we can make a recursive call to walk_fs starting with f_path. It will return a list of files that we can concat to output.

If f_path is a file, we just add it to output. When we have finished iterating through contents, we can return output. The output file will hold all of the files in start_dir and it’s subdirectorys.

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.

%d bloggers like this: