How can I create a linked list in Python?

[sturlamolden]

Bruno Desthuilliers wrote:

> Implementing linked lists in Python is not a great deal - it just
> doesn't make much sens.

It does make sence, as there are memory constraints related to it.
Python lists are arrays under the hood. This is deliberately. Dynamic
arrays grows faster than lists for the common "short list" case, and
because indexing an array is O(1) instead of O(N) as it is for linked
lists. You can easily break the performance of Python lists by adding
objects in the middle of a list or appending objects to the end of long
lists. At some point the list can not grow larger by a simple realloc,
as it would crash with other objects on the heap, and the whole list
must be replaced by a brand new memory segment.

Also linked lists are an interesting theoretical concept in computer
science. Understanding how dynamic datastructures work and their
limitations are a key to understanding algorithms and how computers
work in general.

The simplest way of implementing a linked list in Python is nesting
Python lists. One may e.g. type something like:

#create
mylist = []

# push
mylist = [someobject, mylist]

# pop
mylist = mylist[1]

#iterate
cur = mylist
while cur:
   cur = cur[1]

This is actually single linked list that behaves like a stack, i.e. the
last added element sits on top and one needs to iterate the list to get
to the first.

Those who know Lisp should be familiar with the concept of creating
dynamic data structures form nesting lists; it may be more unfamiliar
to C and Pascal programmers, as these languages do not support such
constructs. In Python one may also use a more explicit solution
involving classes for expressing linked lists, which would be more
familiar to C and Pascal programmers. In any case, making linked lists
are trivial in Python.