Sifan Xu Sifan Xu - 3 years ago 156
Python Question

Python: NoneType AttributeError when implementing priority queue with linked nodes

class Node:
def __init__(self, data=None, priority='L', next=None):
self.data = data
self.priority = priority
self.next = next

def __str__(self):
return str(self.data)

class P_Queue:
def __init__(self, head=None):
self.head = head
self.length = 0

def enqueue(self, node):
newNode = Node(node.data, node.priority)
if (self.head == None):
self.head = newNode
elif (self.head and self.head.priority == 'L' and newNode.priority == 'H'):
newNode.next = self.head
self.head = newNode
elif (self.head and self.head.priority == 'H' and newNode.priority == 'H'):
last = self.head
while (last.next and last.next.priority == 'H'):
last = last.next
if (last.next and last.next.next):
newNode.next = last.next.next
last.next = newNode
else:
last = self.head
while last.next:
last = last.next
last.next = newNode
self.length += 1

def dequeue(self):
node = self.head
print("next head: ")
print(self.head.next)
self.head = self.head.next
self.length = self.length - 1
return node

def is_empty(self):
return self.length==0

def main():
node0 = Node(0, 'L')
node1 = Node(1, 'H')
node2 = Node(2, 'H')

queue = P_Queue()

queue.enqueue(node0)
queue.enqueue(node1)
queue.enqueue(node2)

print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())

main()


The problem occurs for the last line of the displayed code at the while statement in queue(), I get the error "'Nontype' object has no attribute property.", but only for queue(node1)

However, according to my print statements (output: H) for node0 = Node(0, 'H'), I clearly have a value of 'H' for that attribute (priority) and it does not contain a 'None' value so it's just mindboggling to me.

Please help... and if anyone has a good resource for learning how to implement a priority queue with a linked list for beginners that would be great too. Thank-you so much I'm dying here.

Traceback below:

next head: 2
1
next head: None
2
next head:
Traceback (most recent call last):
File "assignment1_3 queues.py", line 62, in <module>
main()
File "assignment1_3 queues.py", line 60, in main
print(queue.dequeue())
File "assignment1_3 queues.py", line 39, in dequeue
print(self.head.next)
AttributeError: 'NoneType' object has no attribute 'next'


------------------
(program exited with code: 1)

Press any key to continue . . .

Answer Source

Your while loop works. You keep forwarding your last = last.next until you reach NoneType. Before you progressing your last to last.next, verify there is a node there. I've modified this part of your code:

    elif (self.head.priority == 'H' and newNode.priority == 'H'):
        last = self.head
        print(self.head.priority)
        print(last.priority)
        while last.priority == 'H' and last.next:  # <-- check last.next 
                                                         exists before pointing to it
            last = last.next
        if last.next and last.next.next:  # <-- same thing here
            newNode.next = last.next.next
        last.next = newNode

and this is the output:

>>> main()
H
H
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download