Data structures in Python - Linked Lists

Pyhton-linked-lists.txt

Though I consulted several resources regarding linked lists, this proved to be the one where the idea "clicked", and it is where the below code
and "cargo" terminology come from. http://openbookproject.net/thinkcs/python/english3e/linked_lists.html 

A linked list is a collection of data comprised of nodes. Each node is either empty or it contains "cargo" and a reference to
the next node in the list (for a singly linked list) or references to the next node and the previous node (for a doubly linked
list). The advantage to linked lists is that we do not have to allocate memory to them; the nodes will add themselves to 
memory wherever they have room. Insertions are super fast [O(1)] as are removals because we typically work from the ends. The trade off is that the entire list has to be traversed to find the data being requested, so all find operations are O(n). There are no external references to locations in a linked list (unlike an array which is indexed and is contiguous in memory). 

This is the most basic form of a node in a linked list:
class Node:
  def __init__(self, cargo=None, next=None):
     self.cargo = cargo
     self.next = next
     
  def __str__(self):
    return str(self.cargo)

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

This inserts three integers into three locations that are patterned after the Node class above. It will be more useful if we
are able to retrieve more than one item that we already know the location of (i.e. let's add links).

node1.next = node2
node2.next = node3

This is OK for brute force creation of the most basic of linked lists. As it is we can search for a Node if we know it's there, but we can't return a list or remove a Node. 

A little functional panache will make things easier for searching and updating the list. From the top we'll establish all the properties of the Node: 

class Node:
  def __init__(self, cargo=None, next=None):
     self.cargo = cargo
     self.next = next
     
  def getCargo(self):
    return self.cargo
  
  def setCargo(self, val):
    self.cargo = val
    
  def nextNode(self):
    return self.next
    
  def setNextNode(self,val):
    self.next = val

# Next we need to be able to make and modify the linked list itself
# this prints as a STACK or first-in last-out (FILO)/ Last In First Out (LIFO) implementation

  def __init__(self,head=None):
    self.head = head
    self.size = 0
  
  def getSize(self):
    return self.size
    
  def addNode(self, cargo): # Typically stacks call this a push
    newNode = Node(cargo, self.head)
    self.head = newNode
    self.size += 1
    return True
    
  def printNodes(self):
    current = self.head
    while current:
      print(current.cargo)
      current = current.nextNode()

# Alias LinkedList as myList to make things slightly easier      
myList = LinkedList()
myList.addNode(4)
myList.addNode(50)
myList.addNode(37)
myList.printNodes() # 37 50 4

# Let's simply discover whether a value exists in the linked list (True or False). This is done by traversing through each
node and comparing node.cargo to the value in question. 

def findNode(self,value):
  current = self.head
  #as long as there is a 'self' this process will continue
  while current: 
    #compare the cargo to the value 
    if current.getCargo() == value:
      return True
    current = current.nextNode()
  return False

# Finally let's remove a node from the list. We'll need to keep track of where we are (current) and where we've been (previous) 
# This removal step begins with a search, so the worst case scenario is this will take O(n) time.

def removeNode(self, value): # Typically this operation is called pop
    previous = None
    current = self.head
    
    while current:
      if current.getCargo() == value:
        if previous:
          previous.setNextNode(current.nextNode())
        else:
          self.head = current.nextNode()
        return True
        
      previous = current
      current = current.nextNode()
      
    return False
    
    
# Time to make this a more traditional linked list where each new node is added as a tail
# This prints as a First In First Out (FIFO) structure, also called a QUEUE
# Making the Node class stays the same

class Node:
  def __init__(self, cargo):
     self.cargo = cargo
     self.next = None
     
  def getCargo(self):
    return self.cargo
  
  def setCargo(self, val):
    self.cargo = val
    
  def nextNode(self):
    return self.next
    
  def setNextNode(self,val):
    self.next = val
    
# but now we need a tail
class LinkedList: 
  def __init__(self):
    self.head = None
    self.tail = None
    self.size = 0
  
  def getSize(self):
    return self.size
    
# Specifically it is the adding of nodes that is different. 
# Adding a node to the tail is called "enqueueing" while removing the head node is "dequeueing"

  def addNode(self, cargo):
    
    # make sure the cargo is in the correct format as a Node
    cargo = Node(cargo)
            
    if ( self.head == None ):
      self.head = cargo
    else:
      self.tail.next = cargo
      
    self.tail = cargo
    return True

  def printNodes(self):
    current = self.head
    while current:
      print(current.cargo)
      current = current.nextNode()

# Finding and removing work the same as before: 

def findNode(self,value):
  current = self.head
  while current: 
    #compare the cargo to the value 
    if current.getCargo() == value:
      return True
    current = current.nextNode()
  return False

def removeNode(self, value):
    previous = None
    current = self.head
    
    while current:
      if current.getCargo() == value:
        if previous:
          previous.setNextNode(current.nextNode())
        else:
          self.head = current.nextNode()
        return True
        
      previous = current
      current = current.nextNode()
      
    return False
    
# The Doubly Linked List (DLL) adds a reference to the previous Node

class Node:
  def __init__(self, cargo):
     self.cargo = cargo
     self.next = None
     self.prev = None
     
  def getCargo(self):
    return self.cargo
  
  def setCargo(self, val):
    self.cargo = val
    
  def nextNode(self):
    return self.next
    
  def setNextNode(self,val):
    self.next = val
    
  def prevNode(self):
    return self.prev
    
  def setPrevNode(self,val):
    self.prev = val

# Now we have to consider some edge cases as well as keep track of where we are

class DoublyLinkedList: 
  def __init__(self):
    self.head = None
    self.tail = None
    self.size = 0
  
  def getSize(self):
    return self.size
    
  def addNode(self, cargo):
    newNode = Node(cargo)
    if (self.head == None):
      self.head = self.tail = newNode
    else:
      newNode.prev = self.tail
      newNode.next = None
      self.tail.next = newNode
      self.tail = newNode
    self.size += 1
    
  def removeNode(self, value):
    currentNode = self.head 
    
    while currentNode is not None:
      if currentNode.cargo == value:
        if currentNode.prev is not None:
          currentNode.prev.next = currentNode.next
          currentNode.next.prev = currentNode.prev
        else:
          self.head = currentNode.next
          currentNode.next.prev = currentNode.prev
          
      currentNode = currentNode.next
      self.size -= 1
      
  def printNodes(self):
    currentNode = self.head
    
    while currentNode is not None:
      print(" prev: {}\n cargo: {}\n next: {} ".format(
      currentNode.prev.cargo if hasattr( currentNode.prev, "cargo") else None,
      currentNode.cargo,
      currentNode.next.cargo if hasattr( currentNode.next, "cargo") else None))
      
      currentNode = currentNode.next
    return True