单向链表的递归实现
Recursive Implementation of a Singly Linked List
你好,我正在尝试做这个练习:
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
的默认值,但我需要这样做,因此用户不必明确指定它,所以如何我可以解决这个问题吗?
我认为您不需要为此定义两个 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)
你好,我正在尝试做这个练习:
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
的默认值,但我需要这样做,因此用户不必明确指定它,所以如何我可以解决这个问题吗?
我认为您不需要为此定义两个 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)