CODEWITHSUNDEEP
pythonalgorithmclassrecursion
jan sobieski
jan sobieski

Reputation: 11

Recursive implementation of a singly linked list class in python

Sometime ago I decided to learn algorithms but doing it on my own is not easy task, so I'm in the middle of reading a book Data Structures and Algorithms in Python by Goodrich but I'm stuck on exercise C-7.27

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.

I did recursions before with functions but on class level it is a little bit to abstract for me. I have this base structure and I don't know how to carry on.

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_el):
            self._element = element
            self._next = next_el

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

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

As I understand _Node._next should carry SinglyLinkedList class something like this:

def append(self, e):
    newest = _Node(e, SinglyLinkedList())

But now to dress it up in recursion so I can picture it as a whole. Can any help me with it?

Upvotes: 1

Views: 926

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1123770

First of all: in a singly linked list the last node should not link to anything; use None to indicate the end of a list. In your code the last node links back to itself.

Recursion using instances just means that you'll call the same method still, but on another instance rather than use a global function or the same method on self.

For appending to a linked list then, you'd call append() on the next node, and the recursion termination condition is handling appending at the node that has no next node (e.g. the end of the list):

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

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

    def append(self, element):
        if self._next is not None:
            self._next.append(element)
        self._next = SinglyLinkedList._Node(element, None)

You'll need to add a append() method to the SinglyLinkedList class too that kicks off the recursion, and adjusts the length.

You'll want to start with self._head = None in SinglyLinkedList.__init__ for an empty list, by the way. Handle that case when appending; empty list -> create first node, non-empty -> recurse:

def append(self, element):
    if self._head is None:
        self._head = self._Node(element, None)
    else:
        self._head.append(element)
    self._size += 1

Note that you don't have to 'nest' _Node inside the SinglyLinkedList class; it only makes referencing the class harder hear for your own code. I had to use SinglyLinkedList._Node() inside _Node.append() to reference the class; the alternative would be to use type(self)().

Upvotes: 1

Related Questions