python - python中单链表类的递归实现

Question

前段时间我决定学习算法，但靠我自己来做并不是一件容易的事，所以我正在阅读 Goodrich 的Python 中的数据结构和算法一书，但我'我坚持练习 C-7.27

Give a recursive implementation of a singly linked list class, such that an instance of a nonempty list stores its first element and a reference to a list of remaining elements. Hint: View the chain of nodes following the head node as themselves forming another list.

我之前用函数做过递归，但在类级别上它对我来说有点抽象。我有这个基本结构，但我不知道如何继续。

class SinglyLinkedList:
    '''A base class providing a single linked list representation'''

    class _Node:
        """non public class for storing a singly linked node"""
        __slots__ = '_element', '_next'  # streamline memory usage

        def __init__(self, element, next_el):
            self._element = element
            self._next = next_el

    def __init__(self):
        self._header = self._Node(None, None)
        self._header._next = self._header
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

据我所知，_Node._next 应该携带 SinglyLinkedList 类，如下所示:

def append(self, e):
    newest = _Node(e, SinglyLinkedList())

但现在要用递归方式修饰它，这样我就可以把它想象成一个整体。有什么可以帮助我的吗？

Answer 1

首先:在单向链表中，最后一个节点不应该链接到任何东西；使用 None 来指示列表的结尾。在您的代码中，最后一个节点链接回自身。

使用实例递归意味着您仍然会调用相同的方法，但在另一个实例上，而不是在 self 上使用全局函数或相同的方法。

然后，为了追加到链表，您将在下一个节点上调用 append()，递归终止条件是在没有下一个节点的节点上处理追加/em>(例如列表末尾):

class _Node:
    """non public class for storing a singly linked node"""
    __slots__ = '_element', '_next'  # streamline memory usage

    def __init__(self, element, next_el):
        self._element = element
        self._next = next_el

    def append(self, element):
        if self._next is not None:
            self._next.append(element)
        self._next = SinglyLinkedList._Node(element, None)

您还需要向 SinglyLinkedList 类添加一个 append() 方法，以启动递归并调整长度。

顺便说一下，对于空列表，您需要从 SinglyLinkedList.__init__ 中的 self._head = None 开始。附加时处理这种情况；空列表 -> 创建第一个节点，非空 -> 递归:

def append(self, element):
    if self._head is None:
        self._head = self._Node(element, None)
    else:
        self._head.append(element)
    self._size += 1

请注意，您不必在 SinglyLinkedList 类中“嵌套”_Node；它只会让您自己的代码更难听到引用该类。我必须在 _Node.append() 中使用 SinglyLinkedList._Node() 来引用该类；另一种方法是使用 type(self)()。