This was my first attempt at a Python script. Actually, I lie. I’ve tried before, but lost interest after a little bit. Not sure why, because Python is fun, fun, fun! I did have to think a little bit before getting into it, but once I got going, it was smooth sailing. As with my Java Linked List, I used a Unit Testing framework, thanks to Python’sunittest package. It’s easy peasy. Oh, and of course, I used Eclipse with the great PyDev plugin for Python scripting.

One of the things that caught my eye with the Python linked list is that I did not need to declare the member variables for the class. I can simply set them, and the class magically knows about them. That’s pretty cool. In addition, what I would call a coding style of indentation has semantic meaning in Python: instead of blocks being enclosed in braces, they’re indented. Otherwise, no massive issues to report.

So, as you would expect, the linked list implementation has O(1) insert (because we insert at the end of the list) and O(n) delete (because we need to iterate the entire list to find the right node to delete). The other operations I’ve provided are add, remove, get_size, index_of, contains and to_string.

Note: I’ve only tested this implementation with strings. Python doesn’t have the same capability as Java with something like the equals() method. The rules for object comparison may make containing objects of arbitrary types in the list a little tricky. An excerpt from the Python documentation: “Most other types compare unequal unless they are the same object; the choice whether one object is considered smaller or larger than another one is made arbitrarily but consistently within one execution of a program.”

The code and unit tests are available in my GitHub repository.

Part 1: The LinkedListNode class
The list node is simply the data and a reference to the next node. It’s stored in its own source file and is a class. The member variables holding the data and next are initialised in the __init__ method.

class LinkedListNode:

    def __init__(self, inData, inNext):
        """Construct a new Linked List Node"""
        self.data = inData
        self.next = inNext

Part 2: The LinkedList class
The linked list class has a first and last node reference and a size. We import the LinkedListNode class from its source file.

from com.danielacton.datastructures.LinkedListNode import LinkedListNode

class LinkedList:

    def __init__(self):
        """Construct a new LinkedList. The first node and last node are the same. Size is 0"""
        self.firstNode = LinkedListNode(None, None)
        self.lastNode = self.firstNode
        self.size = 0

Part 3: The add() method(s)
The add method replaces the lastNode reference with the node being added and makes the old last node reference the new node as the next node in the list. There are 2 add methods, one to add a single node and one to add multiple nodes (with a Python list being used to pass values to add in the latter method).

def add(self, data):
        """Add a node to the list"""
        node = LinkedListNode(data, None)
        node.data = data;

        if self.firstNode.data == None:
            self.firstNode = node
            self.lastNode = node
        else:
            self.lastNode.next = node
            self.lastNode = node

        self.size += 1

    def add_many(self, list_of_data):
        """Add a list of nodes to the linked list"""
        for x in list_of_data:
            self.add(x)

Part 4: The remove() method(s)
The remove method iterates the list looking for the node to delete. We actually look ahead in the list because we need to loop around the deleted node by having the previous node point to the following node as its next node. There are 2 remove methods, one to remove a single node and one to remove multiple nodes (with a Python list being used to pass values to remove in the latter method).

def remove(self, data):
        """Remove a node from the list"""
        currentNode = self.firstNode
        wasDeleted = False

        if self.size == 0:
            pass

        # The first node is being removed
        if data == currentNode.data:
            # This is the case where we have only one node in the list
            if currentNode.next == None:
                self.firstNode = LinkedListNode(None, None)
                self.lastNode = self.firstNode
                self.size = self.size - 1
                return

            # Here there are more than one nodes in the list
            currentNode = currentNode.next
            self.firstNode = currentNode
            self.size = self.size - 1
            return;

        while True:

            if currentNode == None:
                wasDeleted = False
                break

            # Check if the data of the next is what we're looking for
            nextNode = currentNode.next
            if nextNode != None:
                if data == nextNode.data:
                    # Found the right one, loop around the node
                    nextNextNode = nextNode.next
                    currentNode.next = nextNextNode

                    nextNode = None
                    wasDeleted = True
                    break

            currentNode = currentNode.next

        if wasDeleted:
            self.size = self.size - 1;

    def remove_many(self, list_of_data):
        """Remove a list of nodes from the linked list"""
        for x in list_of_data:
            self.remove(x)

Part 5: The helper method(s)
The to_string(), contains(), index_of and get_size() methods are provided to make things more useful.

def to_string(self):
        """Get a string representation of the list"""
        result = ""
        currentNode = self.firstNode
        i = 0

        result = result + "{"

        while currentNode != None:
            if i > 0:
                result = result + ","

            dataObj = currentNode.data

            if dataObj != None:
                result = result + dataObj

            currentNode = currentNode.next

            i = i + 1

        result = result + "}"
        return result

    def contains(self, data):
        """Check whether a node is in the list or not"""
        currentNode = self.firstNode

        while currentNode != None:
            if currentNode.data == data:
                return True
            else:
                currentNode = currentNode.next

        return False

    def index_of(self, data):
        """Find the position of a node in the list"""
        currentNode = self.firstNode
        pos = 0

        while currentNode != None:
            if (currentNode.data == data):
                return pos
            else:
                currentNode = currentNode.next
                pos = pos + 1

        return -1    

    def get_size(self):
        """Get the size of the list"""
        return self.size