Date: Thu, 5 Jun 1997 10:02:41 -0400 (EDT)
From: "Art S. Kagel" <kagel AT ns1 DOT bloomberg DOT com>
To: Orlando Andico <orly AT gibson DOT eee DOT upd DOT edu DOT ph>
Cc: Conrad Wei-Li Song <conradsong AT mail DOT utexas DOT edu>,
        Timothy Robb <trobb AT neutrino DOT phys DOT laurentian DOT ca>, djgpp AT delorie DOT com
Subject: Re: LinkedLists
In-Reply-To: <Pine.SGI.3.93.970605144510.9061A-100000@gibson.eee.upd.edu.ph>
Message-Id: <Pine.D-G.3.91.970605094710.6701B-100000@dg1>
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Precedence: bulk

On Thu, 5 Jun 1997, Orlando Andico wrote:

> > >I've given up on Quick Sorting my list because I will be adding one item
> > >at a time to it and the add function will call the sort function, as a
> > >result Insertion Sort would probably be the best method.
> > >
> > Listen.  If you're not going to be calling a lot of inserts or deletes in
> > the middle of the list consider implementing the list as a self-adjusting
> > array-- that is, when you run out of room in your array, you double its
> [..]
> 
> Forgive me if I'm wrong, but I think the best implementation overall is a
> dynamically-allocated binary tree. Did anyone mention that? you can even
[SNIP]
I agree if you have to keep the list in order as items are added there is 
no other choice than some tree structure, binary or otherwise.  BTW there 
is no efficient way to binary search a linked list since you have to 
follow (seglen)/2 links to find the middle of each segment.  But a binary 
tree gives all of the search advantage of a binary search as long as you 
do not have to process the whole list sequentially.  In that case one of 
the other tree structures, like b+ trees will perform better.

Art S. Kagel, kagel AT bloomberg DOT com