Reply to:   Re: [FB] Linked Lists
I've been reading the arguments for and against linked lists, and I thought I'd throw my two cents in.  I think Rick made a good point about inserting an item at the beginning of a huge single-chunk of memory.  It might be painful on slow computers to blockmove the huge back-end of the "chunk" to make room.  On the other hand, it may also be painful on slow computers to find the 955th item of a 1000 item linked list if you have to walk the whole list just to get there.
What about this...Supposed you combine the two ideas.  Make one XREF@ array where each item is 4 bytes.  When you need to create new record items, create a new handle (or pointer) and store the address in the XREF@ array at that item number.  This way you would have individual records in memory, but one master XREF@ array of the address to each chunk of memory.  Then if you needed to insert an item into slot #5 of a 1000 item list, just create your handle (or pointer) and store the address in the master XREF@ array in slot #5.  The most memory you would ever have to move is 4*(the number of following records)....not so bad.  Then the other problem would be solved to.  To find item #95, just go to slot #95 in your XREF@ array to get the address to the handle (or pointer).  No need to walk a list.
Makes sense to me.

Rob


Rick Brown wrote:
>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
>
>
>--
>To unsubscribe, send ANY message to <futurebasic-unsubscribe@...>
>
>
>RFC822 header
>-----------------------------------
>
> RECEIVED: from SF_Database by POP_Mailbox_-1305027154 ; 29 SEP 98 18:55:42 UT
> Received: from ASSOCIATE.COM by mail.agendas.com
>      with SMTP (QuickMail Pro Server for MacOS 1.0.2); 29 SEP 98 18:55:35 UT
> Received: (qmail 6453 invoked by alias); 29 Sep 1998 21:54:05 -0400
> Mailing-List: contact futurebasic-help@...; run by ezmlm
> Reply-To: futurebasic@...
> Delivered-To: mailing list futurebasic@...
> Received: (qmail 6441 invoked from network); 29 Sep 1998 21:54:02 -0400
> Received: from falcon.inetnebr.com (@199.184.119.1)
>   by stewart.pnet.msen.com with SMTP; 29 Sep 1998 21:54:02 -0400
> Received: from 206.222.199.9 (lin-hs4-009.inetnebr.com [206.222.199.9])
> 	by falcon.inetnebr.com (8.8.8/8.8.8) with SMTP id UAA27442
> 	for <futurebasic@...>; Tue, 29 Sep 1998 20:50:37 -0500 (CDT)
> Message-ID: <36117545.9C9@...>
> Date: Tue, 29 Sep 1998 19:03:20 -0500
> From: Rick Brown <rbrown@...>
> X-Mailer: Mozilla 3.01-C-MACOS8 (Macintosh; I; PPC)
> MIME-Version: 1.0
> To: futurebasic@...
> References: <199809290526.XAA19077@...>
> Content-Type: text/plain; charset=us-ascii
> Content-Transfer-Encoding: 7bit
> Subject: Re: [FB] Linked Lists
>