Skip to content
Advertisement

Adding a Prepend Method to a Linked List Class

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 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
User contributions licensed under: CC BY-SA
9 People found this is helpful
Advertisement