Проблема с реализацией рекурсивного метода Add для класса Linked-List

Question

Требуется рекурсивно реализовать метод add для класса связанного списка. Я не могу заставить мой код работать. Это то, что я до сих пор:

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

    def add(self, val, current_node=0):

        if current_node == 0:
            current_node = self.head

        if current_node is None:
            current_node = Node(val)
        else:
            self.add(self, val, current_node.next)

Где я ошибся с этой реализацией?

Answer 1

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

Сказав, что для профессоров характерно требовать алгоритмов, которые не подходят для рекурсии, чтобы быть рекурсивно реализованными. Играя вместе, я бы написал внутреннего помощника, который обрабатывает реальную рекурсию. Это позволяет избежать неудобного параметра по умолчанию, который может сбить с толку вызывающего абонента и позволить ему нарушить контракт функции.

def add(self, val):
    def add_recursively(curr, prev):
        if curr:
            add_recursively(curr.next, curr)
        else:
            if prev:
                prev.next = Node(val)
            else:
                self.head = Node(val)

    add_recursively(self.head, None)

Основная проблема при первоначальной попытке заключается в следующем:

if current_node is None:
    current_node = Node(val)

Без ссылка на предыдущий узел в цепочке, current_node на самом деле не привязана ни к чему, используя вышеуказанную операцию, поэтому она просто собирает мусор при возврате функции.

Если вам разрешено использовать итерацию , это более естественный подход:

def add(self, val):
    curr = self.head
    prev = None

    while curr:
        prev, curr = curr, curr.next

    if prev:
        prev.next = Node(val)
    else:
        self.head = Node(val)

Вот минимальный, полный пример использования:

class Node:
    def __init__(self, val, next_node=None):
        self.val = val
        self.next = next_node

    def __str__(self): 
        return str(self.val)

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

    def add(self, val):
        curr = self.head
        prev = None

        while curr:
            prev, curr = curr, curr.next

        if prev:
            prev.next = Node(val)
        else:
            self.head = Node(val)

    def __str__(self): 
        nodes = []
        curr = self.head

        while curr:
            nodes.append(curr.val)
            curr = curr.next

        return "[" + " -> ".join(nodes) + "]"

if __name__ == "__main__":
    llist = LinkedList()
    llist.add("bananas")
    llist.add("apples")
    llist.add("cranberries")
    print(llist) # => [bananas -> apples -> cranberries]

Помимо этого, рассмотрите сохранение ссылки на узел self.tail для вашего LinkedList учебный класс. Это сделало бы операции добавления O (1) вместо O (n).