Questions on Using Python to Teach Data Structures and Algorithms

[sturlamolden]

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.