向链表类添加Prepend方法

Question

我目前正在做一个涉及链表和python的类项目。目前，我正试图为所述链表创建一个前置函数。我当前的代码抛出了一个递归错误。下面是我的代码:

节点定义:

class Node:
def __init__(self):
self.data = None
self.previous = None
# introduce a 'next' node for doubly linked list
self.next = None
def get(self):
return self.data
def getPrev(self):
return self.previous
def setPrev(self, previous):
self.previous = previous
def set(self, data):
self.data = data
def getNext(self):
return self.next
def setNext(self, next):
self.next = next
node = property(get, set)
prev = property(getPrev, setPrev)
next = property(getNext, setNext)

下面是带有/append和破前置的List函数:

class SList:
def __init__(self):
self.tail = None
# introduce 'head' node for double link
self.head = None
# appends to tail of list
def Append(self, data):
pdata = Node()
pdata.node = data
if self.tail is None:
self.tail = pdata
else:
pdata.prev = self.tail
self.tail = pdata
# prepends to head of list
def Prepend(self, data):
pdata = Node()
pdata.note = data
if self.head is None:
self.head = pdata
pdata.step = self
else:
previous = self.head
previous.step = pdata
pdata.head = previous
pdata.step = self
self.head = pdata

递归错误发生在第29行，即setNext函数:

def setNext(self, next)
self.next = next

Answer 1

有几个问题:

• setter和getter都是多余的。看看这个答案…直接为简单类使用属性更符合python的风格。当您的代码正常工作时，定义属性可能是最后一步，但是当您仍然有问题时，它不应该在那里。

• 您的代码访问Node上未定义的几个属性，例如head和note。

• 当列表为空，添加节点时，必须同时设置head和tail属性，而不能只设置其中一个。

• 对于方法不要使用PascalCase，而是使用camelCase。所以是append，不是Append。µ

• 允许Node构造函数获取数据作为参数。

这是一个实现:

class Node:
def __init__(self, data):  # Use argument
self.data = data
self.previous = None
self.next = None
class SList:
def __init__(self):
self.tail = None
self.head = None
def append(self, data):
node = Node(data)  # use argument
node.previous = self.tail
if self.head is None:  # list is empty
self.head = node  #  need to set head too!
else:
self.tail.next = node  #  need to link both directions
self.tail = node
def prepend(self, data):
node = Node(data)
node.next = self.head
if self.head is None:
self.tail = node
else:
self.head.previous = node
self.head = node

正如您在注释中指出的那样，您没有得到任何输出，下面是测试上述内容的一些代码:

lst = SList()
lst.append(3)
lst.append(4)
lst.prepend(2)
lst.prepend(1)
node = lst.head
while node:
print(node.data, end=" ")
node = node.next

输出为:

1 2 3 4

Answer 2

为了避免无限递归，使用不同的属性名称(例如_next)来存储值，如下所示:

def setNext(self, next);
self._next = next