How can I recursively add to a linked list in Python?

Question

I have trouble using recursion with linked lists. I want to be able to add another node to an ordered linked list.

I have this class:

class Link:
    def __init__(self,value,next=None):
        self.value = value
        self.next  = next

Below is the recursive function, that so far doesn't do much except identifying base cases

Note: it's not a method in Link, it's a separate function:

def add(ll, v):
    if ll == None:
        return Link(v)
    else:
         ll.next = add(ll.next,v)
         return ll

Example: I have this linked list A:

1->3->8->12->None

I call add(A, 10) which should add 10 in the right order.

1->3->8->10->12->None

How should I modify my code to make that work?

Answer 1

Recursion is a functional heritage and so using it with functional style yields the best results. We start with the smallest bits first -

# linked_list.py

empty = None

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

def to_str(ll = empty):
  if not ll:
    return "None"
  else:
    return f"{ll.value}->{to_str(ll.next)}"

# main.py

from linked_list import node, to_str

t = node(1, node(3, node(8, node(12))))
print(to_str(t))
# 1->3->8->12->None

Now we implement add -

# linked_list.py
empty = # ...

class node: # ...

def to_str(ll = empty): # ...

def add(ll = empty, v = 0):
  if not ll:
    return node(v)
  elif ll.value >= v:
    return node(v, ll)
  else:
    return node(ll.value, add(ll.next, v))

# main.py

from linked_list import node, to_str, add

t = node(1, node(3, node(8, node(12))))
print(to_str(t))
# 1->3->8->12->None

t2 = add(t, 10)
print(to_str(t2))
# 1->3->8->10->12->None

Now we see how to make bigger bits by combining smaller bits. We could make a linked_list class to bundle it up -

# linked_list.py

empty = # ...

class node: # ...

def to_str(ll = empty): # ...

def add(ll = empty, v = 0): # ...

class linked_list:
  def __init__(self, root = empty):
    self.root = root
  def __str__(self):
    return to_str(self.root)
  def add(self, v):
    return linked_list(add(self.root, v))

Now we can use linked_list in object-oriented style but still get the persistent benefits of functional style -

#main.py

from linked_list import linked_list

t = linked_list().add(1).add(3).add(8).add(12)
print(t)
# 1->3->8->12->None

print(t.add(10))
# 1->3->8->10->12->None

print(t)
# 1->3->8->12->None

Maybe we could expand our linked_list module by defining from_list and to_list -

# linked_list.py

empty = # ...

class node: # ...

def to_str(ll = empty): # ...

def add(ll = empty, v = 0): # ...

def from_list(l = []):
  if not l:
    return empty
  else:
    return node(l[0], from_list(l[1:]))

def to_list(ll = empty):
  if not ll:
    return []
  else:
    return [ ll.value ] + to_list(ll.next)

class linked_list:
  def __init__ # ...
  def __str__ # ...
  def add # ...

  def from_list(l):
    return linked_list(from_list(l))

  def to_list(self):
    return to_list(self.root)

# main.py

from linked_list import linked_list

t = linked_list.from_list([ 1, 3, 8, 12 ])
print(t)
# 1->3->8->12->None

print(t.add(10))
# 1->3->8->10->12->None

print(t.add(11).to_list())
# [1, 3, 8, 11, 12]

Answer 2

You need an extra base case, to stop the recursion when you find a value that is not less than the one you want to insert in order:

elif v <= ll.value:
    return Link(v, ll)

So the complete code could be:

class Link:
    def __init__(self,value,next=None):
        self.value = value
        self.next  = next

    def values(self):
        yield self.value
        if self.next:
            yield from self.next.values()

def add(ll, v):
    if ll is None:
        return Link(v)
    elif v <= ll.value:
        return Link(v, ll)
    else:
        ll.next = add(ll.next, v)
        return ll

# example list
A = Link(1, Link(3, Link(8, Link(12))))
# add 10 to it:
A = add(A, 10)
# print list
print(list(A.values()))