Insert a node before another node in singly linked list in Python?

Question

I did see this post here [java] and am attempting a similar solution, but the noted thread did not fully answer my question)

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.

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.

You'll see in my if statement, I'm hoping to compare node.next.value to my targetNode (note that targetNode is a value) -- why is my node.next.value throwing me the following error? if node.next.value == targetNode: AttributeError: 'NoneType' object has no attribute 'value'

# 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 + ' <--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)

Please note: 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 node.next with the targetNode object.

• twk: Why did someone down vote me for asking this question? What's wrong with my question above and why can't I ask something like this?

Answer 1

As you suggest yourself, the problem seems to be that you create a new node using your target node, node.next == Node(targetNode) as this will never be true.

I assume that targetNode is a Node object, in which case you should simply use node.next == targetNode.

Another problem with your code is that you do not check if the first node is the target node. Thus, you would not be able to insert a node before the head Node using the insertBefore function.

The following code is a rewrite of your insertBefore function which inserts a new node with the specified value before a given node.

def insertBefore(self, targetValue, 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:
 # search nodes
 if node.value == targetValue:
 newNode.next = self.head
 self.head = newNode
 while node.next is not None:
 if node.next.value == targetValue:
 print ">>> ",node.value,' <--this was node before target'
 newNode.next = node.next
 node.next = newNode
 return
 else:
 node = node.next
 print 'Your target node of {} was not found in the list!'.format(targetNode.value)

If you want targetNode to be the value of the target node, you will need to compare node.next.value with targetNode. Note that this would insert the value before the first occurrence of the target value. Thus, you might want to turn you list into a set instead.

• twk: I actually tried node.next.value == targetNode (targetNode is a value and not an object), but that didn't work for me, as I was getting an error that node.next.value is not defined (which was weird to me...)...I know that node.next and node.value are valid, but for some reason node.next.value was throwing an error...I know I'm so close and I'd love to understand why it's not working :)
• twk: I had thought the same thing but your answer gives me the following error: if node.next.value == targetNode: AttributeError: 'NoneType' object has no attribute 'value'
• Jonas: Could you show how you call your function? if targetNode is a value and not a node then your naming is a bit unclear. Also if you values as target for you insert before then you will only be able to insert befor the first occurrence of that value in your list.
• twk: I've added the solution that I was able to figure out below, I call my insertBefore() function as follows: names = SinglyLinkedList() names.insertBefore('Tim','John') (this is for a linked list where I'm wishing to insert 'John' before the node 'Tim'.) targetNode is a value, perhaps targetValue would be more appropriate.
• Jonas: Okay, I have now updated the code, so that it uses the value of the nodes instead of the actual node. Your solution still have the problem that it does not check if the head of the list is the target node, thus you are unable to insert a node in the beginning of the list. Again, I want to say that insertBefore is only well defined as long as your list do not contain any duplicates.

Answer 2

Here's how I was able to find a solution to my question:

 def insertBefore(self, targetValue, 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 = False
 # search nodes
 while node:
 if node.next == None:
 break
 if node.next.value == targetValue:
 found = True
 newNode.next = node.next
 node.next = newNode
 break
 else:
 node = node.next
 if found != True:
 print 'Your target node of {} was not found in the list!'.format(targetValue)

Note, as Jonas pointed out in his comments, the above mentioned solution only works if there are no duplicates in the node list.

Answer 3

This is my solution of your problem.

def addBefore(self, nextData, data):
 newNode = Node(data, None)
 if self.head.data == nextData:
 newNode.next = self.head
 self.head = newNode
 return
 ptr = self.head
 while ptr is not None:
 if ptr.data == nextData:
 newNode.next = ptr
 parPtr.next = newNode
 break
 else:
 parPtr = ptr
 ptr = ptr.next