How can I create a linked list in Python?

[bearophileHUGS at lycos.com]

Gary Herron:
> If you really want a list (as Python defines a list - with all the methods) then you should use Python's lists.  They are quite efficient and convenient:

In CPython they are dynamic arrays, they aren't lists. Try adding
elements at the beginning of a list compared to adding elements at the
beginning or in the middle of a python "list" and you will see the
efficiency differences.


> The concept of a linked list if a figment of languages with pointer data types.

You may manage a list with a language without pointers, like *basic*
(for students) Scheme. Creating a List data type for Python is possible
too, without true pointer like ones found in Pascal.


>However, you're much better off if you can use Python's list data structure rather
>than try to emulate an outdated concept in a modern language.

Simple lists today aren't much efficient because their pointers break
cache locality, they may cause cache trashing, so they may be slower
than smarter and more localized structures, like short double linked
arrays, etc.
But I think lists aren't outdated, they are a mathematical concept too,
and they are quite used still.
If you want to learn some Computer Science, it's positive to know what
linked lists are.
If you want to implement algorithms that must process LOT of things,
you may find pointers and lists quite necessary today too, see for
example:
http://citeseer.ist.psu.edu/knuth00dancing.html
http://en.wikipedia.org/wiki/Dancing_Links
Python and its data structures aren't the right solutions for all
purposes.

Bye,
bearophile