title: Insert a node before another node in singly linked list in Python?
body: <p>I did see this post <a href="https://stackoverflow.com/questions/7198508/given-a-node-how-can-i-find-previous-node-in-a-singly-linked-list">here</a> [java] and am attempting a similar solution, but the noted thread did not fully answer my question)</p>
  
  <p>I need to work with singly linked lists and want to try and perform an insertBefore() method. I understand that doubly-linked lists have a previous attribute, while singly linked lists do not, so I understand this might be better accomplished using doubly-linked lists, but this was the requirements of the assignment and I'm trying to solve things.</p>
  
  <p>So far below: I've got my Node class setup along with my SinglyLinkedList class. I've also got my insertBefore() method, which is my goal and where I'm getting stuck.</p>
  
  <p>You'll see in my if statement, I'm hoping to compare <code>node.next.value</code> to my <code>targetNode</code> (note that targetNode is a value) -- why is my node.next.value throwing me the following error? <code>if node.next.value == targetNode: AttributeError: 'NoneType' object has no attribute 'value'</code></p>
  
  <pre><code># this is our node object
  class Node(object):
      def __init__(self, value, next=None):
          self.value = value
          self.next = next
  
  # this is our singly linked list object
  class SinglyLinkedList(object):
      def __init__(self):
          self.head = None
          self.tail = None
  
      def insertBefore(self, targetNode, value):
          # create new node
          newNode = Node(value)
          # find target node to insert
          node = self.head
          if node == None:
              print 'There aren\'t any nodes to insert before!'
          else:
              found = None
              # search nodes
              while node:
                  if node.next.value == targetNode:
                      found = True
                      print node.value + ' &lt;--this was node before target'
                      beforeInsert = node
                      afterInsert = node.next
                      beforeInsert.next = newNode
                      newNode.next = afterInsert # sets new node's next to target node
                      node = node.next # continues through while loop
                  else:
                      node = node.next
              if found != True:
                  print 'Your target node of {} was not found in the list!'.format(targetNode)
  </code></pre>
  
  <p><em>Please note</em>: I was able to get this to work for an insertAfter() method (not included in the snippet above), but am struggling to match up the <code>node.next</code> with the <code>targetNode</code> object.</p>