[Tutor] lists

[alan.gauld@bt.com]

> Linked lists are created using pointers in lanquages like C and C++.
> Nodes are accessed in a linear fashion. However, the design makes the
> removal or insertion of nodes very efficient.
> 
> You do not need linked lists in Python. In fact it would be very
> difficult to create (if not impossible), because Python does not have
> pointers. 

C/C++ pointers are simply memory addresses however a pointer 
in a pure CS terms is a reference to an object, Thus Python 
does indeed have pointers. A node simply becomes a list 
containing the data and a reference to the next node(or None)

root = [None,None]
def addNode(node, list): # prepends node
    node[1] = list
    list = node
    return list

for i in range(5):
    root = addNode([i,None],root)

#print list
n = root
while n[1] != None:
   print n[0],
   n = n[1]

produces:

4,3,2,1,0

You can also use the trick C programmers have used for years 
where they want very fast linked lists - create a large 
array then use the array index of the next item as the pointer.
This also works in Python using a big list.

Alan g.
Author of the 'Learning to Program' web site
http://www.freenetpages.co.uk/hp/alan.gauld