单链接列表的递归实施

Question

您好，我试图进行此练习：

给出单链接列表类的递归实现， 非空列表的实例存储其第一个元素和一个 参考其余元素列表。提示：查看链 遵循头部节点的节点本身会形成另一个列表。

这是我的代码：

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):
            self._element = element
            self._next = next

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

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0
    
    def append(self,element,curr = self._head):
        if curr._next == None:
            curr._next = SinglyLinkedList._Node(element,None)
        else:
            self.append(element,curr._next)

首先，我想知道此实现是否正确，而且当我运行此代码时，我会收到错误：

<ipython-input-33-e95376bc1d2f> in SinglyLinkedList()
     22         return self._size == 0
     23 
---> 24     def append(self,element,curr = self._header):
     25         if curr._next == None:
     26             curr._next = SinglyLinkedList._Node(element,None)

NameError: name 'self' is not defined

我认为是因为我使用self.__head for默认值对于参数curr，但我需要执行此操作，因此用户不必明确指定它，所以我该如何解决此问题？

Answer 1

我认为您不需要为此定义两个类。如果您将singlylinkedlist实例分配给_Next属性，那将很奇怪，然后再次具有_head属性。

只需坚持节点类：

class Node:
    def __init__(self, element, next=None):
        self._element = element
        self._next = next

    def append(self, element):
        if self._next is None:
            self._next = Node(element)
        else:
            self._next.append(element)

    def prepend(self, element):
        return Node(element, self)
        
    def __iter__(self):
        yield self._element
        if self._next is not None:
            yield from self._next

    def __repr__(self):
        return "->".join(map(repr, self))

演示运行：

a = Node(4).prepend(3).prepend(2).prepend(1)
print(a)