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.

>Solution :

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