CODEWITHSUNDEEP
pythondata-structuressingly-linked-listrecursive-datastructures
KamuiYato
KamuiYato

Reputation: 33

Recursive Implementation of a Singly Linked List

Hello I am trying to do this exercise:

Give a recursive implementation of a singly linked list class, such that an instance of a nonempty list stores its first element and a reference to a list of remaining elements. Hint: View the chain of nodes following the head node as themselves forming another list.

Here is my code:

class SinglyLinkedList:
    '''A base class providing a single linked list representation'''

    class _Node:
        """non public class for storing a singly linked node"""
        __slots__ = '_element', '_next'  # streamline memory usage

        def __init__(self, element, next):
            self._element = element
            self._next = next

    def __init__(self):
        self._head = self._Node(None, None)
        self._head._next = self._head
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0
    
    def append(self,element,curr = self._head):
        if curr._next == None:
            curr._next = SinglyLinkedList._Node(element,None)
        else:
            self.append(element,curr._next)

First I would like to know if this implementation is correct, and also when I run this code I get the error:

<ipython-input-33-e95376bc1d2f> in SinglyLinkedList()
     22         return self._size == 0
     23 
---> 24     def append(self,element,curr = self._header):
     25         if curr._next == None:
     26             curr._next = SinglyLinkedList._Node(element,None)

NameError: name 'self' is not defined

I think it's because I am using self._head for a default value for the argument curr but I need to do this, so the user won't have to specify it explicitly, so how can I solve this issue please?

Upvotes: 0

Views: 115

Answers (1)

trincot
trincot

Reputation: 350756

I don't think you need to define two classes for this. It would be strange if you would assign a SinglyLinkedList instance to a _next attribute, which then again has a _head attribute.

Just stick to the Node class:

class Node:
    def __init__(self, element, next=None):
        self._element = element
        self._next = next

    def append(self, element):
        if self._next is None:
            self._next = Node(element)
        else:
            self._next.append(element)

    def prepend(self, element):
        return Node(element, self)
        
    def __iter__(self):
        yield self._element
        if self._next is not None:
            yield from self._next

    def __repr__(self):
        return "->".join(map(repr, self))

Demo run:

a = Node(4).prepend(3).prepend(2).prepend(1)
print(a)

Upvotes: 1

Related Questions