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!
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 if lst else lst cdr = lambda lst: lst 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")
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:
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")