Implementing Linked Lists in Python 2.x

NOTE: PLEASE PARDON THE EXCESSIVE <DIV> TAGS IN THE CODE PORTIONS… THIS POST IS UNFINISHED

Today, I’ll implement the first of several elementary data structures in Python– linked lists. The goal here is not to create anything novel or efficient, but rather to master foundational building blocks for my future incursions into Data Structures and Algorithms. This approach follows the advice provided in the introduction of The Little Schemer. The author uses the example of his college photography course to point out that ritualization of less glamorous technical knowledge is prerequisite to true creativity in a craft like programming.

I’ll start by consulting several familiar resources to understand the details of singly linked lists, which I’ll refer to from this point simply as linked lists. To my understanding, a linked list allows for the storage of a linear array of items (nodes). A reference to the address of the next node follows each item. The nodes need not be physically ordered in memory. Ordering is not relevant in tracing the path of items in the array. This property makes linked lists easier to modify than co-located arrays (e.g., C arrays). At the same time, accessing item at index of a linked list may require O(n) time because the items preceding item i must be accessed sequentially to find item i (compared to constant time for a linear pre-set array).

This diagram from Stanford’s CS Library does a great job illustrating the linked list concept:

parlante

The figure above can be traced as follows. The stack and heap distinction will be disregarded in this Python implementation, since no actual pointers will be used (more on this choice later). The array reads linearly: First, a pointer at the head directs the observer towards the first element of the list. The observer sees the value, which here is an integer of value 1 at the first node. The memory slot immediately following the integer value indicates the location of the next element. At this element node, another value/pointer pair will be found. This pattern continues recursively until the last node’s pointer field contains a null character, at which point the observer understands that the reading is terminated.

Following the advice of a friend, I decided to embrace Python’s strengths and limitations as a high-level interpreted language, specifically with regards to object-oriented support and lack of pointer access. My list is implemented as an interaction between two generic objects, a node and a wrapper for the head node. These roughly correspond to the head (shown on the heap side) and the three node instances (stack side) shown in the diagram, although, again, the concepts of stack and heap have no place in my design.

Here’s the first class, Node:

class Node:
''' element of linked list with tail as reference to next element'''

def __init__(self, head, tail=None):
self.head = head #node content
self.tail = tail #simulates pointer, reference to next item

I will assume the reader is familiar with the details of class implementation in Python. Each instance of node serves as an element of the linked list. This nuclear data structure knows only of its immediate sequential successor by means of tail reference. That is, the linked list is implemented in manner that makes each node unaware of any other node in the world but that node referenced at its tail address. No pointer support is allowed, so this node is simply an abstraction– one that holds a value and a reference to the next item. The tail is by default set to “None”, simulating what would be a NULL character in the C implementation.

What follows is a piecewise overview of the linked list object, with which the client interfaces.

class LinkedList:
def __init__(self,firstNode=None):
self.firstNode = firstNode
The linked list starts life as a reference to None, the Python equivalent to C’s NULL. If this remains the case, the following method, isEmpty(), will evaluate to True.
def isEmpty(self):
if (self.firstNode == None): return True
else: return False
Head resembles the Haskell function, returning the value of the leading entry of the list:
def head(self):
return self.firstNode
On the other hand, a tail function, returns xs for x:xs. That is, all elements following the first are returned.

def tail(self):
''' returns xs for x:xs'''
if (self.isEmpty()): return None
else: return LinkedList(self.firstNode.tail)
def last(self): #does this work?
'''recursively yields the list node of the linked list'''
if self.firstNode.tail == None: return firstNode
else: return self.tail
def cons(self,newFirstNode):
'''perlim: replaces head with new head'''
#assert type(newFirstNode) == Node instance
newFirstNode.tail = self.firstNode
self.firstNode = newFirstNode
return None
def push(self): pass
''' release first element'''
handle = self.firstNode #check propriety of term
self.firstNode = self.firstNode.tail
return handle
def length(self): pass
'''recursively find length of link list'''
if (self.firstNode.tail == None): 1
else: 1 + length(self)
Advertisements
Implementing Linked Lists in Python 2.x