Linked lists and recursion in python

Question

I am newbie in programming and starting out in Python. My question is regarding linked lists, I wrote a class for the linked list, what I need to do is to have a function with an input as a reference pointing towards the head of the list. 'linked_list.head' as I understand, with linked_list being the name of the list in question. Specifically using recursion, I am trying to find the length of the list as the output of this function. Here's my code, I don't quite understand how I could move to the next node and return the number of nodes with recursion in this case.

import re
def special_match(strg, search=re.compile(r'[^A-Za-z.]').search):
    return not bool(search(strg))

class node:
    def __init__(self, data, next):
        self.data = data
        self.next = next

    def get_data(self):
        return self.data

    def set_data(self,value):
        self.data = value

    def get_next_node(self):
        return self.next

    def set_next_node(self,val):
        self.next = val

class linked_list:

    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def add_first(self,e):
        newest = node(e,None)
        newest.next = self.head
        self.head = newest
        self.size = self.size+1
        if self.size == 1:
            self.tail = newest

    def add_last(self,e):
        newest = node(e,None)
        if self.size > 0:
            self.tail.next = newest
        else:
            self.head = newest
        self.tail = newest
        self.size = self.size+1

    def remove_first(self):
        if self.size == 0:
            print('The linked list is empty')
        elif self.size == 1:
            answer = self.head.data
            self.head = None
            self.tail = None
            self.size -= 1
            return answer
        else:
            answer = self.head.data
            self.head = self.head.next
            self.size = self.size - 1
            return answer

    def remove_last(self):
        if self.size == 0:
            print('The linked list is empty')
        elif self.size == 1:
            answer = self.tail.data
            self.head = None
            self.tail = None
            self.size -= 1
            return answer
        else:
            temp  = self.head
            while(temp.next is not None):
                temp = temp.next
            temp.next = None


    def node_number(self,reference):
        reference = str(reference)
        count = 0
        temp = self.head
        if special_match(reference) == True:
            count =+ 1
            temp = temp.next
            return self.node_number  
        else:
            print('You have made wrong input')

    def printe(self):
        curr = self.head
        while curr:
            print(curr.data)
            curr = curr.get_next_node()
        if self.size == 0:
            print('The list is empty')

Answer 1

Recursion is a functional heritage and so using it with functional style will yield the best results. In your program, you have implemented a linked list using imperative style mutable nodes- that is, the values of data and next can change over time. While this might feel like an intuitive approach, I'd like to focus on an immutable implementation that frees us from crippling state complexity. In this answer, we will implement all linked list functions using recursive forms expressed with functional styles.

We start with simple node and linked_list classes. This time we skip creating get_* and set_* functions as you have done. There's other ways to do this kind of thing in Python as we'll see in a minute

class node:
  def __init__ (self, left, right):
    self.left = left
    self.right = right


class linked_list:
  def __init__ (self, node = None):
    self.node = node

Next we define primitive properties for our list: is_empty, head, and tail

class linked_list:
  def __init__ (self, node = None):
    self.node = node

  @property
  def is_empty (self):
    return self.node is None

  @property
  def head (self):
    if self.is_empty:
      raise Exception ("cannot get head of an empty list")
    else:
      return self.node.left

  @property
  def tail (self):
    if self.is_empty:
      raise Exception ("cannot get tail of an empty list")
    else:
      return self.node.right

Now the use of a node is completely abstracted, and we can write higher level list behaviors by using our new properties

class linked_list:
  ... 

  def length (self):
    if self.is_empty:
      return 0
    else:
      return 1 + self.tail.length ()

Above, we see it's very easy to talk about our list thru use of its properties. Before we go further, let's see how we can construct lists and visualize them using print. For object-to-string conversion, we use __str__

class linked_list:
  ... 

  def add_first (self, x):
    return linked_list (node (x, self))

  def __str__ (self):
    if self.is_empty:
      return "None"
    else:
      return str (self.head) + " -> " + str (self.tail)

ls = linked_list().add_first(3).add_first(2).add_first(1)
print (ls)
# 1 -> 2 -> 3 -> None

print (ls.length ())
# 3

Remember, because we've built an immutable linked list, add_first does not change the list it was called upon

ls = linked_list().add_first(3).add_first(2).add_first(1)
print (ls)
# 1 -> 2 -> 3 -> None

print (ls.add_first (0))
# 0 -> 1 -> 2 -> 3 -> None

print (ls)
# 1 -> 2 -> 3 -> None

Before we move on, let's make it easier to construct our linked lists. We add a static build function which allows us to construct a list of a varying number of inputs

class linked_list:
  ...

  @staticmethod
  def build (x = None, *rest):
    if x is None:
      return linked_list ()
    else:
      return linked_list (node (x, linked_list.build (*rest)))

print (linked_list.build (1,2,3))
# 1 -> 2 -> 3 -> None

Now, let's look at your remove_first and remove_last functions now

class linked_list:
  ...

  def remove_first (self):
    if self.is_empty:
      raise Exception ("cannot remove first element of an empty list")
    else:
      return self.tail

  def remove_last (self):
    if self.is_empty:
      raise Exception ("cannot remove last element of an empty list")
    elif self.tail.is_empty:
      return self.tail
    else:
      return linked_list (node (self.head, self.tail.remove_last ()))

ls = linked_list.build (1,2,3)
print (ls)
# 1 -> 2 -> 3 -> None

print (ls.remove_first ())
# 2 -> 3 -> None

print (ls.remove_last ())
# 1 -> 2 -> None

print (ls)
# 1 -> 2 -> 3 -> None

And node_number

class linked_list:
  ...

  def node_number (self, index = 0):
    if self.is_empty:
      raise Exception ("index out of bounds")
    elif index is 0:
      return self.head
    else:
      return self.tail.node_number (index - 1)

ls = linked_list.build ("a", "b", "c")

print (ls.node_number (0))
# "a"

print (ls.node_number (1))
# "b"

print (ls.node_number (10))
# Exception: index out of bounds

And a add_last freebie

class linked_list:
  ...

  def add_last (self, x):
    if self.is_empty:
      return self.add_first (x)
    else:
      return linked_list (node (self.head, self.tail.add_last (x)))

ls = linked_list.build (1, 2, 3)
print (ls)
# 1 -> 2 -> 3 -> None

print (ls.add_last (4))
# 1 -> 2 -> 3 -> 4 -> None

print (ls)
# 1 -> 2 -> 3 -> None

Full program demonstration at repl.it

Answer 2

I'd set it up where the length function is actually part of the Node class rather than the Linked_List class. The Linked_List class would have a length function too, but all it would do is to call the length function of the head node of the list.

Then, each node would just return the length of it's next instance plus 1.

Answer 3

The recursion should have a base case where the code checks if the next attribute is None. If so, the function returns the current count. If not, the counter is incremented and the function length is called as a method of the next attribute, to be able to continue the progression of the recursion along the links, which can be written as:

|val1|pointer| -> |val2|pointer| -> |val3|pointer| -> |val4|pointer| -> |val5|None|

First, below is a simpler linked list class construct for demonstration:

class Node:
   def __init__(self, val=None):
      self.head = val
      self.next = None 
   def length(self, count = 0):
      if self.next is None:
         return count + 1 if self.next is None and self.head else count
      return self.next.length(count + 1)
   def insert(self, v):
      if self.head is None:
         self.head = v
      else:
         if self.next is None:
           self.next = Node(v)
         else:
           self.next.insert(v)
   @classmethod
   def regular_transform(cls, node, nodes = []):
      '''for easier visulization'''
      return nodes+[node.head] if not node.next else cls.regular_transform(node.next, nodes+[node.head])

n = Node()
for i in [56, 232, 424, 2, 11]:
  n.insert(i)
print(Node.regular_transform(n))
print(n.length())

Output:

[56, 232, 424, 2, 11]
5