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