[Tutor] Speaking of Linked Lists...

[Wesley J. Chun]

<Úÿ¿¢û

    > From: "Britt Green" <britt_green@hotmail.com>
    > Subject: [Tutor] Speaking of Linked Lists...
    > Date: Tue, 20 Mar 2001 09:08:20 -0800
    >
    > 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.


britt,

excellent question, esp. for newbies.  it almost sounds like
techno-babble until you start think about their application.
but, to answer your question in brief, they can be used for
just about anything where they make sense.

you said in your message that you understand the "how-to" of
coding them.  in daniel's reply, he gave a "how-to" on
visualizing them -- you need to think about them in that way
while you're coding otherwise it's much harder to come up with
the code believe it or not!

now the "why."  dealing with data is one of the main reasons
for creating computer programs.  you are either gathering it,
updating it, maintaining it, searching for it, or deleting it.
now, before i start, this primarily applies to languages where
the programmer is responsible for allocating these "nodes" or
basically memory to contain this data -- it's easy to get
spoiled by Python where this is not necessary!

often times when you're dealing with an unknown amount of data,
for example, a "blackbook" name and adress book application
for you to store contact information for your friends, family,
etc.  you store this data on disk and create a routine to read
all this data into memory.

the problem is, you are not sure how many names and addresses
are in your database so you don't know how much memory to allo-
cate!  a linked list allows you to read in one entry, and check
if there are any more entries to be read.  if so, read in one
more, "hook it up" to the first guy, and repeat.

by the time you're done, you've read everything into memory,
and because they are all hooked together like train cars, you
can go down the list and print them out, search for someone,
etc.  note that in daniel's explantion, you can even choose
*where* to insert them into the list.

it is them possible to not only read in all the data from disk,
but you can even alphabetize the order just by inserting each
entry into the right spot in a linked list!

i hope that was a helpful introduction!  in college, this
material is taught in a class called "Data Structures" and
is usually an undergraduate lower division course which you
take in your 2nd year.  it's a real doozy and will provide
you plenty of sleepless nights in the lab!  i'm sure daniel
can attest to that!!	;-)	(is it still CS 61C?)

cheers!

-wesley

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
Silicon Valley-SF Bay Area Python users group:  http://www.baypiggies.org

"Core Python Programming", Prentice Hall PTR, December 2000
    http://starship.python.net/crew/wesc/cpp/

wesley.j.chun :: wesc@baypiggies.org
cyberweb.consulting :: silicon.valley, ca
http://www.roadkill.com/~wesc/cyberweb/