[Tutor] Speaking of Linked Lists...

[Michael P. Reilly]

> 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.

Linked lists (and it's brethren: doublely, circular, etc.) are usually
just concepts to be used for bigger, "more" important (conceptually)
data structures like queues, stacks, sparce matrices and in a different
way, trees.

As an example of how they are used, take an operating system with one
large process table.  Only one process can run on a CPU at any one
time, others will be waiting to for time on the CPU, and others will be
waiting for various devices.  There is one field in each entry in the
process table which points to the "next process waiting" for some
resource (CPU, hard drive, network, etc.).  Following the chain of
processes creates a queue.  A process can be removed from one queue and
placed on another (one stopped waiting for the hard drive and is now
waiting for the CPU) by changing the "next process waiting" field, not
by copying the process entry to a different data structure.

In short, linked lists are generally used when dealing with large
structures, to keep the structures nicely organized by only changing a
few words.

  -Arcege

-- 
------------------------------------------------------------------------
| Michael P. Reilly, Release Manager  | Email: arcege@shore.net        |
| Salem, Mass. USA  01970             |                                |
------------------------------------------------------------------------