Adding a Prepend Method to a Linked List Class

Question

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

What is your question? Just guessing, you'd probably best make a drawing of the existing list and the one with the new element added to find which references to change and how. — Ulrich Eckhardt, Jul 04 '22 at 18:53
Please add the traceback to your question showing the exact error. Saying "line 29" is almost meaningless when there are no line numbers shown. — martineau, Jul 04 '22 at 20:02
This code has many issues. There are attributes accessed on a `Node` instance that are not defined in the constructor: `.node`, `.note`, `.step`, `.head`, `.prev`... Yet the attributes that **should** be accessed, like `.previous` and `.next` are not accessed nor in `Append`, nor in `Prepend`... Note also how your `Append` has fewer lines of code than `Prepend`, yet they should have the same amount of work to do... And this is just scratching the surface of the problems. Did you run a debugging session at all? — trincot, Jul 04 '22 at 20:02
`Node` is *wildly* overengineered. `__init__` is the only necessary method; all the others can be replaced by directly access to the attributes. — chepner, Jul 04 '22 at 20:04
The problem is that your `next` property recursively references itself; there is no separate instance attribute named `next`. — chepner, Jul 04 '22 at 20:06

score 0 · Answer 1 · answered Jul 04 '22 at 20:11

0

To avoid the infinite recursion, use a different attribute name (e.g. _next) to store the value, like this:

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

answered Jul 04 '22 at 20:11

pts

80,836
20
110
183

trincot · Accepted Answer · 2022-07-05T16:55:06.803

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 as head, and note.
When the list is empty, and a node is added, both the head and tail attributes must be set, not just one of them.
Don't use PascalCase for methods, but camelCase. So append, not Append.µ
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

Thank you so much for your help! Your solution helped fix the recursion issue. However when I try to run the prepend/append code (after creating a list), it doesn't actually save anything. Instead of numbers it outputs None. — alshih3, Jul 05 '22 at 15:41
These methods are not supposed to return anything. They mutate the list. You need more code to actually output something from that list. — trincot, Jul 05 '22 at 15:50
Anyway, I added a section to my answer showing you how you can get output. — trincot, Jul 05 '22 at 16:55
Thank you so much for your help! It turns out I just wrote my output function incorrectly haha! — alshih3, Jul 05 '22 at 17:16

Adding a Prepend Method to a Linked List Class

2 Answers2