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?

Anshul Goyal · Accepted Answer · 2015-02-04 07:00:20Z

10

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.

answered Feb 4, 2015 at 7:00

Anshul Goyal

78k42 gold badges161 silver badges196 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Newbie Over a year ago

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 Over a year ago

@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 Over a year ago

Ok I will have to research how to do that. Thank you

Anshul Goyal Over a year ago

@Newbie Just edited my last comment. Also, if that helped, don't forget to accept and upvote :)

Newbie Over a year ago

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.

mik · Accepted Answer · 2017-03-10 19:13:28Z

1

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

answered Mar 10, 2017 at 19:13

mik

1108 bronze badges

Comments

Yashwanth Kata · Accepted Answer · 2017-04-02 15:17:14Z

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)

Dhaval Mohandas · Accepted Answer · 2018-08-11 12:09:42Z

1

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

answered Aug 11, 2018 at 12:09

Dhaval Mohandas

736 bronze badges

Collectives™ on Stack Overflow

Python Linked List Append

4 Answers 4

5 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

5 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related