Блог

Главная - Вопросы по программированию - Невозможно добавить в связанный список на python

Невозможно добавить в связанный список на python

#python #python-3.x #recursion #linked-list

Вопрос:

Я пытаюсь научиться создавать связанные списки. Это мой первый раз, когда я делаю это, и причиной сбоя кода может быть что-то основное, чего мне не хватает.

Это, как говорится, я не могу понять даже после использования отладчика vs code. Он просто останавливается в конце метода добавления, когда он вызывается во второй раз.

Я использую рекурсию для перехода к хвосту. Может ли это быть проблемой?

 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)

Комментарии:

1. self._traverse_to_tail() находит последний узел, зачем вам нужен while цикл после его вызова?

2. Не используйте рекурсию, чтобы найти хвост. Вы можете использовать while цикл, подобный тому, который у вас есть append() .

3. предположение, что мой связанный список длиннее 1000 узлов self._traverse_to_tail() , вызовет «ошибку рекурсии». Я не хотел изменять ограничение рекурсии, поэтому while цикл гарантирует, что я нахожусь на последнем узле независимо от длины связанного списка.

4. Если вы не используете рекурсию, вам не нужно ограничение.

5. while Цикл в __repr()__ никогда не обновляется current , так что это бесконечный цикл.

Ответ №1:

Проблема в том, что у вас бесконечный цикл в __repr__() функции, потому что вы никогда не увеличиваете 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
Метки: