Message-Id: <199706050619.CAA13562@delorie.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Thu, 05 Jun 1997 02:20:41 -0500
To: Timothy Robb <trobb AT neutrino DOT phys DOT laurentian DOT ca>
From: Conrad Wei-Li Song <conradsong AT mail DOT utexas DOT edu>
Subject: Re: LinkedLists
Cc: djgpp AT delorie DOT com
Precedence: bulk

At 10:58 PM 6/4/97 -0400, you 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
size, and when your array becomes 1/4 full you half its size.  Implementing
stacks and queues in this manner is extremely efficient because of the
loss of many pointer indirections and fewer memory allocations and deletes.
Disadvantage is that inserting and deleting in the middle of the list is
very costly, and large allocations require a contiguous block of memory
(but this becomes a blessing with virtual memory).  You'll then be able
to perform your QuickSort efficiently.

Otherwise, if you're using a linked list structure, you can still get your
n-log-n sort by implementing your linked list as a tree and using a heap
sort.

>My next problem is binary searching through a linked list....
Implement your linked list as a tree and you'll have no problems.

Conrad
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.2

mQCNAzMorW8AAAEEALh5yWIjAha5FzBhDr0ckxp+JtXDcwSxrVC01vavv3JqoH6/
3qeozcoAVQIHcGkRQejm3de7O7IluD8R0v4nDKace3PBROoQXJ16pxO9sXoBXSaD
nc3jlMXepad2KL+kcNo7Pyq/I8gKqlny8oIdwaoJ8AP2wq6IhxOr5o88Yz99AAUR
tC9Db25yYWQgV2VpLUxpIFNvbmcgPGNvbnJhZHNvbmdAbWFpbC51dGV4YXMuZWR1
Pg==
=lcVD
-----END PGP PUBLIC KEY BLOCK-----