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... -- http://mail.python.org/mailman/listinfo/python-list
