单向链表的递归实现

Question

你好，我正在尝试做这个练习：

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):
            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 作为参数 curr 的默认值，但我需要这样做，因此用户不必明确指定它，所以如何我可以解决这个问题吗？

Answer 1

我认为您不需要为此定义两个 class。如果您将 SinglyLinkedList 实例分配给 _next 属性，然后又具有 _head 属性，那将很奇怪。

只要坚持 Node class:

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)

单向链表的递归实现

Recursive Implementation of a Singly Linked List

python

data-structures

singly-linked-list

recursive-datastructures