How can I create a linked list in Python?

[Bruno Desthuilliers]

sturlamolden a écrit :
> Bruno Desthuilliers wrote:
> 
> 
>>Implementing linked lists in Python is not a great deal - it just
>>doesn't make much sens.
> 
> 
> It does make sence,

Oh Yec ?-)

sorry...

> 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.

That's certainly true - from a technical POV -, but I never had such a 
problem in now 7 years of Python programming.

> 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.

Indeed. Did I say otherwise ?

> The simplest way of implementing a linked list in Python is nesting
> Python lists. 

Have you considered using tuples ? If you go the FP way, why not use an 
immutable type ?

(snip)

> 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.

But how are Lisp lists implemented then ?-)

I do totally agree that Lispish lists are something one should learn, 
but starting with a low-level procedural language with 'manual' memory 
management is certainly a Good Thing(tm). Well, IMHO at least (FWIW, 
having first learned to implement linked lists in C and Pascal, I had no 
problem understanding Lisp's list).

> 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.
> 
Yes again. Hence my remark...