CODEWITHSUNDEEP
pythondata-structureslinked-listtraversal
adi.
adi.

Reputation: 97

Problem in traversing a linked list after finding the middle node

I'm just starting to learn Algorithms and Data Structures in Python and I've come across this linked list problem. Overall I've managed to find the middle node the naive way but I don't understand why after the list is traversed it doesn't output the last print command.

This is the traverse function:

def traverse(self):
        actual_node = self.head

        print("----------")
        while actual_node is not None:
            print(actual_node.data)
            actual_node = actual_node.next
        print("----------") # This is not displayed in the output

Here is the entire program:

# Linked List Question
# Construct an algorithm that's able to find the middle node and traverse the list


class Node:
    def __init__(self, data):
        self.data = data
        self.next = Node

class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def insert_start(self, data):
        self.size += 1
        new_node = Node(data)

        if not self.head:
            self.head = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    def size_of_linkedList(self):
        return self.size

    def traverse(self):
        actual_node = self.head

        print("----------")
        while actual_node is not None:
            print(actual_node.data)
            actual_node = actual_node.next
        print("----------")



    def middle_node(self):
        actual_node = self.head
        sizeofNode = 0

        while actual_node is not None:
            if sizeofNode == self.size // 2:
                print("This is the middle node: " + str(actual_node))
                print("This is the middle node data: " + str(actual_node.data))
                break
            else:
                actual_node = actual_node.next
                sizeofNode += 1

if __name__ == "__main__":

    linked_list = LinkedList()

    linked_list.insert_start(0)
    linked_list.insert_start(1)
    linked_list.insert_start(2)
    linked_list.insert_start(3)
    linked_list.insert_start(4)
    linked_list.insert_start(5)
    linked_list.insert_start(6)

    print("The size of the list is:  %d" % linked_list.size_of_linkedList())
    linked_list.middle_node()
    linked_list.traverse()

These are the errors I receive:

Traceback (most recent call last):
  File "linkedListQ1.py", line 66, in <module>
    linked_list.traverse()
  File "linkedListQ1.py", line 33, in traverse
    print(actual_node.data)
AttributeError: type object 'Node' has no attribute 'data'

This is the output:

The size of the list is:  7
This is the middle node: <__main__.Node object at 0x7fb6ee6d1d00>
This is the middle node data: 3
----------
6
5
4
3
2
1
0

The problem with the program besides the errors is that the print("----------") doesn't get executed after the last element of the node. Could someone explain what is it that I'm doing wrong and offer code snippets. Thank you in advance.

Upvotes: 1

Views: 75

Answers (1)

Stef
Stef

Reputation: 15525

This is a simple typo - it should be self.next = None rather than self.next = Node in the .__init__ method.

Note the fun error message - it says "AttributeError: type object 'Node' has no attribute 'data'" and not "AttributeError: 'Node' object has no attribute 'data'". (Well; at least I think it's fun.)

Upvotes: 1

Related Questions