Python Linked List Append
I Made an Append Method for an Unorderedlist() Class That Works Fine in My Idle Window but When Its Assigned to the University's Test of: My_List =...
I made an append method for an UnorderedList() class that works fine in my IDLE window but when its assigned to the University's test of:
my_list = UnorderedList()
my_list.append(13)
for num in my_list:
print(num, end=" ")
print()
it returns an error: AttributeError: Nonetype object has no attribute 'getNext'.
Here is the append method:
def append(self,item):
current = self.head
while current.getNext() != None:
current = current.getNext()
current.setNext(Node(item))
Here is the rest of my classes and code:
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
class UnorderedList:
def __init__(self):
self.head = None
self.count = 0
def append(self,item):
current = self.head
while current.getNext() != None:
current = current.getNext()
current.setNext(Node(item))
Why is the test returning that error and how I can fix my append method?
4 Answers
The problem is here in the append method:
def append(self,item):
current = self.head
while current.getNext() != None:
current = current.getNext()
current.setNext(Node(item))
In the first iteration, the value of current is self.head, which is set to None initially, and you don't check for it.
So instead, alter this and introduce checks for this condition ad below:
def append(self,item):
current = self.head
if current:
while current.getNext() != None:
current = current.getNext()
current.setNext(Node(item))
else:
self.head = Node(item)
PS: you are also using a variable self.count, which you are not updating. You might want to update the same as well.
your append method works fine but it traverses the list until it finds the last node - which makes it O(n). If you keep track of the last node, you can make an append which is O(1):
def append_O1(self, item):
temp = Node(item)
last = self.tail
last.setnext(temp)
self.tail = temp
self.length += 1
To enable this your list class constructor should be:
class unorderedList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0
Adding little more elaborated append methods
Method to insert at the beginning
def inserAtBeginning(self, item):
newNode = Node(item)
newNode.setdata(item)
if self.listLength() == 0:
self.head = newNode
else:
newNode.setnext(self.head)
self.head = newNode
Method to insert at the end
def insertAtEnd(self, item):
newNode = Node(item)
newNode.setdata(item)
current = self.head
while current.getnext() != None:
current = current.getnext()
current.setnext(newNode)
Method to insert at the specified position
def insertAtPos(self, pos, item):
if pos > self.listLength() or pos < 0:
return None
if pos == 0:
self.inserAtBeginning(item)
else:
if pos == self.listLength():
self.insertAtEnd(item)
else:
newNode = Node(item)
newNode.setdata(item)
current = self.head
count = 0
while count < pos - 1:
count += 1
current = current.getnext()
newNode.setnext(current.getnext())
current.setnext(newNode)
This O(n) implementation should work for an empty list too :
def append(self,item):
current = self.head
if current == None:
self.head = Node(item)
else:
while current.getNext() != None:
current = current.getNext()
current.setNext(Node(item))
David Miller brings 15 years of experience in global economics, personal finance strategy, and market dynamics. He specializes in turning complex economic trends into actionable insights for everyday readers.
