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

Licensed under: CC-BY-SA with attribution

Not affiliated with: Stack Overflow