#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