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")