Recursion Depth Exceeded - Python Doubly-Linked List
-
12-12-2019 - |
题
I'm in the process of creating a FIFO implemented as a doubly-linked list, but I'm at a loss as to why I'm receiving a recursion error. I've posted my code and the error I received below. Any help would be much appreciated!
"""DLList.py"""
class DLList(object):
"""A doubly-linked list
attributes: nl = node list"""
def __init__(self, nl=[]):
self.nl = nl
def __str__(self):
return str(self.nl)
def __len__(self):
return len(self.nl)
def append(self, node):
if not isinstance(node, DLNode):
raise TypeError
try:
node.pn = self.nl[-1]
node.pn.nn = node
self.nl.append(node)
except:
self.nl.append(node)
def pop(self):
rn = self.nl.pop(0)
try:
self.nl[0].pn = None
except:
pass
return rn
class DLNode(object):
"""A node in a doubly-linked list.
attributes: self.pn = previous node, self.data = data, self.nn = next node"""
def __init__(self, data):
self.pn = None
self.data = data
self.nn = None
def __str__(self):
return '[%s, %s, %s]' % (self.pn, self.data, self.nn)
a = DLNode(17)
b = DLNode(15)
c = DLNode(12)
d = DLNode(46)
e = DLNode(46)
ages = DLList()
ages.append(a)
ages.append(b)
ages.append(c)
ages.append(d)
ages.append(e)
print ages.pop()
I received this error:
File "C:\python\swampy-2.0\DLList.py", line 43, in __str__
return '[%s, %s, %s]' % (self.pn, self.data, self.nn)
RuntimeError: maximum recursion depth exceeded
The thing is, I never intended to use recursion, and I can't figure out why I've entered into a recursive loop. ages.pop() is meant to return an instance of DLNode.
解决方案
When you print the node, you are trying to print self.pn and self.nn. Each of those is a reference to another node, which when printed will try to print its next node and previous node, and so on, ad infinitum. You are asking to print an infinite hall of mirrors of nodes.
You have nothing keeping track of what has already been printed, so the recursion will continue forever.
其他提示
Maybe I recommend using collections.deque
instead? You can read its documentation in the library. Unless you are writing your implementation as an academic exercise, deque
is probably better.