Re: [SLUG] Data structures

From: Paul M Foster (paulf@quillandmouse.com)
Date: Tue Nov 12 2002 - 00:12:29 EST


On Mon, Nov 11, 2002 at 09:29:53PM -0500, Russell Hires wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hey Everyone,
>
> I've been doing some exploring on the net about data structures. EVERY
> tutorial/explanation/what-have-you tells you what they are, how they work,
> etc., but they do not under any circumstances tell you what you would use
> them for...why would I use a stack, or a linked list, or whatever?

Why you use them obviously depends on what kind of problem you want to
solve. Program long enough, and you'll find a use for each of them. For
example, a linked list is probably one of the most used data structures.
Let's say you're reading lines from a file, and you want to read them
all in, and then do something to each of the lines after the file's all
read. Not knowing how many lines are in the file without reading them
first, you can't really declare an array of strings, because you don't
know how many to allocate. You could just allocate 1000, but if there
are only 100 lines, it's a waste. And if there are 10000, you're
screwed. The solution is a linked list. Every time you read a line, you
make a new linked list structure. That structure contains the line you
read (or a pointer to it), and a pointer or link to the last linked list
structure you allocated. So each structure points to the next one. When
you're all done reading the file, you can go to the top of the linked
list and process the first line. When you're done with that one, you
just follow its link to the next one. Then you process that line. And so
on.

I'm afraid you're going to have to stand in front of the programming
books section at the bookstore, and pore over what's there, to find one
that really goes into all this. Many programming books assume you know
what these things are, and why you'd use them. They simply show you the
implementation details in the language of your choice. But there _are_
books out there (a little more elementary than the rest) which give
examples of using queues, stacks, deques, linked lists and the lot. I
coulda sworn I had a copy of _Data Structures In C_ around here, but I
don't see it. The other tip I'd give is to find a book that explains
these things in the language you're pursuing. Trying to get through a
treatise on data structures in Pascal when you're coding in C is a bear.

If you get stuck, you could probably contact me or Ronan (if he's
willing) or any of a number of other people offlist for assistance.

Paul



This archive was generated by hypermail 2.1.3 : Fri Aug 01 2014 - 19:34:16 EDT