efrat wrote: > 1. What exactly is a Python list? If one writes a[n], then is the > complexity Theta(n)? If this is O(1), then why was the name "list" > chosen? If this is indeed Theta(n), then what alternative should be > used? (array does not seem suited for teaching purposes.)
A Python list is an array of object references that has some empty slots (or one empty slot?) for growing quickly to the right. If you want to make a chained structure, then perhaps you know LISP? This is what the basic machinery of LISP looks like in Python: def cons(a,b) return [a,b] def car(structure) return structure[0] def cdr(structure) return structure[1] Python lists are more powerful than you would think! You don't need classes or OOP to create linked lists or tree structures in Python. Remember that O(1) is not neccesarily faster than O(N)! Unless your linked list is very big, you will get something called a 'cache miss' inside your CPU. Thus it is usually more efficient to work with dynamic arrays. Further, you can create hybrid array-list structures (e.g. Java's ArrayList) that outperform lists and arrays with respect to adding new elements. But they will have to be tuned to your particular hardware architecture. Growing a linked list node by node is an excercise for fools (and DSA students?) It may look good in DSA textbooks, but it is extremely inefficient on real world computers. Python's lists are implemented as dynamic arrays internally to be efficient on the kind of data we normally work with. Not only do small dynamic arrays grow faster than small lists, they also index much faster. Why are they called "lists" then? Because Guido want you to look at them conceptually as lists. That is what they are. If you want real 'fixed size' arrays like Fortran and Matlab, then you should add 'NumPy' to your Python (http://www.scipy.org). Your science and engineering students will find NumPy, SciPy and Matplotlib (http://matplotlib.sourceforge.net) valuable, so direct them to those sources. -- http://mail.python.org/mailman/listinfo/python-list
