[Tutor] Speaking of Linked Lists...

[Daniel Yoo]

On Tue, 20 Mar 2001, Britt Green wrote:

> Since the topic of linked lists came up recently, I was hoping someone
> could tell me exactly what they're used for. I understand the how-to
> of coding them, but not the why.

Introductory computer science courses talk about linked lists a lot,
because they're one of the "simpler" data structures.  Here's what one
node of a linked list looks like.


-------------
|      |    |
|      |    |
-------------


Traditionally, the first box stores a little bit of information, and the
second box directs us to the next box.  As an analogy, think about
stringing these nodes together with string:


-------       -------       
|  | -|-------|  | -|----->None
-------       -------      


The second box is responsible for the string.  Usually, the programmer
always has a reference to the first node of a linked list, and by tugging
at the string, the programmer can get at any element in the list.  As soon
as we hit None, we should stop pulling; there's nothing left to look at.
It's somewhat similar to a native Python list, but the mechanisms
underneath are all different.


Linked lists are a "container" --- like lists, they're used to store
things.  What people have found useful about them is that they have a
really simple structure, and it's easy to insert a new node into a list of
items.  If you have two pieces of rope, it's very easy to tie them
together:


one piece of rope            another piece of rope
o------------------o         o------------------o

                  ---->   <------
               bringing them together 


o-------------------------------------------o
           one long piece of rope


Same thing with linked lists; what's involved is changing the "link" part
of a node to tie to something else.



What's cool is that we're not just restricted to "concatenating" lists: we
can even make them loop around!


    o------------------------------o         if you twist this into a
                                             loop:

                                        o-------------
                                        |            |
                                        o-------------

And suddenly, we have a "list" that has no end!  It's the concept of being
able to twist and tie these things together that make linked lists useful.  
After working with these things, computer science curriculums can then
introduce stuff like binary trees and other twisted data structures,
without making heads explode.

Now I'd better get to class.  *grin*  Talk to you later!