Python Linked List Append

Question

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?

Answer 1

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.

• Newbie: I think the append function works now but It is now returning: Error: "UnorderedList" object is not iterable. How do I make my list iterable?
• Anshul Goyal: @Newbie it wasn't an iterable in the first place, the for loop wouldn't work in its current form. You can define a custom __iter__ method to fix that. Anyway, that would be a separate question, so you can ask a new one regarding your implementation about the same.
• Newbie: Ok I will have to research how to do that. Thank you
• Anshul Goyal: @Newbie Just edited my last comment. Also, if that helped, don't forget to accept and upvote :)
• Newbie: I have tried making an iter method but the while loop does not end. Any help? I can only post a question in 90 minutes.

Answer 2

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

Answer 3

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)

Answer 4

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))