How can I create a linked list in Python?
bdesth.quelquechose at free.quelquepart.fr
Wed Jan 17 22:05:02 CET 2007
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 ?-)
> 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 ?
> 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
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...
More information about the Python-list