I am currently working on a class project involving linked lists and python. Currently, I am trying to create a prepend function for said linked list. My current code is throwing a recursion error. Here is my code:
Node definition:
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)
Here is the List function w/ append and broken prepend function:
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
The recursion error occurs at line 29 which is the setNext function:
def setNext(self, next) self.next = next
Advertisement
Answer
There are several issues:
The setters and getters are overkill. See this answer… it is more pythonic to just use the attributes directly for simple classes. When your code works, it could be a final step to define properties, but it shouldn’t be there when you are still having problems.
Your code accesses several attributes that are not defined on
Node
, such ashead
, andnote
.When the list is empty, and a node is added, both the
head
andtail
attributes must be set, not just one of them.Don’t use PascalCase for methods, but camelCase. So
append
, notAppend
.ยตAllow the
Node
constructor to get data as an argument.
Here is an implementation:
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
As in comments you indicate you don’t get any output, here is some code that tests the above:
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
The output is:
1 2 3 4