### 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)`. 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!

1
174
11/11/2008 7:31:21 AM

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:

• 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")
``````
68
5/23/2017 12:18:16 PM

For some needs, a deque may also be useful. You can add and remove items on both ends of a deque at O(1) cost.

``````from collections import deque
d = deque([1,2,3,4])

print d
for x in d:
print x
print d.pop(), d
``````