[Tutor] lists [Twisted Linked Lists]

[Paul Sidorsky]

Danny Yoo wrote:

> Hmmm... it might be good to see what linked lists would look like if we
> DIDN't have pointers... *grin*

This reminds me of one of the things that got me so interested in Python
in the first place.  

I first met Python in Data Structures class, where they teach us Python
so we can focus on the data structures and not on memory allocation and
stuff like we'd have to with C/C++.

When they got to trees we were taught the standard class-based approach
to trees, and then the prof showed us a Python approach:

[(key, data), leftsubtree, rightsubtree]

No pointers, no classes, just the stock Python data types.  Being a
long-time C guy this concept just blew me away.  It was foreign.  It was
new.  It was even a bit naughty.  And I liked it.  (Whew, it's getting
hot in here!)

Anyhow the point is that one could, if one were in a suitably deranged
state of mind, build a linked list this way.  A linked-list is really
just a special type of tree, i.e. with every node having at most one
subtree and direction essentially being irrelevant.  So you could also
build a pointerless singly-linked list using this node structure:

[(key, data), nextnode]

This is significantly different than Danny's implementation since it
combines his NODES and NEXTS into one and uses an incredibly-nested list
instead of a flat list.

For trees this is quite nice since the deeply nested list structure
resembles the deep nesting of a tree.  For linked lists it is of course
completely insane.

Hey, who says there's only one way to do things in Python?!  :-)

-- 
======================================================================
Paul Sidorsky                                          Calgary, Canada
paulsid@shaw.ca                        http://members.shaw.ca/paulsid/