Fix Python – Python Linked List

Here is some list functions based on Martin v. Löwis’s representation:

cons   = lambda el, lst: (el, lst)
mklist = lambda *args: reduce(lambda lst, el: cons(el, lst), reversed(args), None)
car = lambda lst: lst[0] if lst else lst
cdr = lambda lst: lst[1] if lst else lst
nth = lambda n, lst: nth(n-1, cdr(lst)) if n > 0 else car(lst)
length  = lambda lst, count=0: length(cdr(lst), count+1) if lst else count
begin   = lambda *args: args[-1]
display = lambda lst: begin(w("%s " % car(lst)), display(cdr(lst))) if lst else w("nil\n")

where w = sys.stdout.write

Although doubly linked lists are famously used in Raymond Hettinger’s ordered set recipe, singly linked lists have no practical value in Python.

I’ve never used a singly linked list in Python for any problem except educational.

Thomas Watnedal suggested a good educational resource How to Think Like a Computer Scientist, Chapter 17: Linked lists:

A linked list is either:

• the empty list, represented by None, or

• a node that contains a cargo object and a reference to a linked list.

  class Node: 
    def __init__(self, cargo=None, next=None): 
      self.car = cargo 
      self.cdr = next    
    def __str__(self): 
      return str(self.car)
  
  def display(lst):
    if lst:
      w("%s " % lst)
      display(lst.cdr)
    else:
      w("nil\n")