Jay wrote:
> I have nothing against linked lists, but for ease of use, understanding, 
> and maintenance, I have just one word (with appologies to the long-timers 
> who have heard me say it too often):
> 
> XREF@
> 
> It gives instant access without "walking" lists. Familiar array format 
> (single- or multi-dimensional). Adjusting handle size is (usually) no 
> more difficult than creating new handles. MUCH simpler if you want to 
> save your records to (or retrieve them from) disk. (Just one handle to 
> write/read.) Saves one master pointer, 12 bytes header space and 8 bytes 
> of links for each record after the first.
> 
> Window-record lists are usually fairly short, and the record itself a bit 
> bulky. An obvious case for a linked list. Another would be variable-size 
> records. For most any other situation, it's XREF@ for me!

I too usually find an XREF@ array to suit my needs better; but there are
certain things that make linked lists preferable at times.  Besides the
issue of variable-size records (which I hadn't even thought about),
there's this:

1) Inserting and deleting items from the linked list is often faster
than doing the same thing with an array.  If you have an array full of
1,000 items and you need to insert a new item into slot #5, (between the
current item #4 and current item #5), then you need to blockmove a
potentially huge chunk of memory (items #5 through #1,000) out of the
way in order to make room for the new item.  If you had implemented this
with linked lists, then the new item #5 can be put anywhere in memory;
to insert it into its proper place in the "chain," you just break the
link between #4 and (old) #5; then link #4 to (new) #5, and link (new)
#5 to (old) #5 (which now becomes #6).  No big blockmoves.

2) Big blockmoves may not be a problem for your fast computer, but there
may be situations where you _must not_ slide the items around in memory:
for example, suppose you have some external pointer which points to item
#17.  Then suppose you need to insert a new item into slot #5 as above. 
You cannot slide items around to make room for the new item, for then
your pointer to item #17 no longer points to the right place.  The
linked list of windows in the MacOS is a perfect example of this.  Once
a window is created, its record _cannot_ be moved in memory, because
applications depend on it staying in one spot.  The only way to keep it
"stationary" and yet allow other windows to be inserted and deleted at
arbitrary positions within the list, is to use a linked list.

- Rick