Claudiu Claudiu - 2 months ago 26
Python Question

Python Linked List

What's the easiest way to use a linked list in python? In scheme, a linked list is defined simply by

'(1 2 3 4 5)
. Python's lists,
[1, 2, 3, 4, 5]
, and tuples,
(1, 2, 3, 4, 5)
, are not, in fact, linked lists, and linked lists have some nice properties such as constant-time concatenation, and being able to reference separate parts of them. Make them immutable and they are really easy to work with!

Answer

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

Linked lists have no practical value in Python. I've never used a 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")