0

I'm trying to learn how to create linked lists. This is my first time doing this and the reason of code failure may be something basic I'm missing.

That being said, I am unable to figure out even after using vs code's debugger. It simply stops at the end of the append method when it is called the second time.

I am using recursion to traverse to the tail. Could that be a the problem?

class Node:

    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node


class LinkedList:

    def __init__(self):
        self.head = None

    def __repr__(self):

        if not self.head:
            return 'Linked list is empty'

        linked_list = self.head.data

        if self.head.next == None:
            return linked_list

        current = self.head

        while current.next != None:
            linked_list += '\n|\nV' + current.data

        return linked_list

    def append(self, value):

        if not self.head:
            self.head = Node(data=value)
            return

        tail = self.tail()

        tail.next = Node(data=value)

    def tail(self):

        tail = self._traverse_to_tail(self.head)

        while tail.next != None:
            tail = self._traverse_to_tail(tail)

        return tail

    def _traverse_to_tail(self, current_node, recursion_count=0):
        print(current_node.data)
        if recursion_count > 997:
            return current_node

        if current_node.next == None:
            return current_node

        current_node = current_node.next
        recursion_count += 1

        return self._traverse_to_tail(current_node, recursion_count)


if __name__ == '__main__':
    ll = LinkedList()

    ll.append('foo')
    ll.append('baz')

    print(ll)
5
  • self._traverse_to_tail() finds the last node, why do you need the while loop after calling that? Commented Sep 28, 2021 at 18:42
  • 1
    Don't use recursion to find the tail. You can use a while loop just like the one you have in append(). Commented Sep 28, 2021 at 18:45
  • assuming my linked list is longer than 1000 nodes self._traverse_to_tail() would raise a 'RecursionError'. I did not want to change the recursion limit so the while loop ensures I am at the last node regardless of the length of linked list. Commented Sep 28, 2021 at 18:47
  • If you don't use recursion, you don't need a limit. Commented Sep 28, 2021 at 18:49
  • The while loop in __repr()__ never updates current, so it's an infinite loop. Commented Sep 28, 2021 at 18:51

1 Answer 1

1

The problem is you have an infinite loop in the __repr__() function, because you never increment current.

    def __repr__(self):

        if not self.head:
            return 'Linked list is empty'

        linked_list = self.head.data

        if self.head.next == None:
            return linked_list

        current = self.head

        while current.next != None:
            current = current.next
            linked_list += '\n|\nV' + current.data

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.