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