Claudiu - 1 year ago 101

Python Question

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

`[1, 2, 3, 4, 5]`

`(1, 2, 3, 4, 5)`

Answer Source

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