Subj : Re: "Faking a linked list" using arrays and sorting that list using an insertion sort...
To   : comp.programming
From : Gene
Date : Tue Oct 04 2005 07:57 pm

Using indices instead of pointers is not "faking" at all.  Lots of new
students of data structures are surprised to learn that all the linked
list algorithms they are learning can be implemented just as easily by
allocating records from an array and using indices in place of
pointers.  In fact, when early FORTRAN was king, that's how _all_
linked structure algorithms (lists, trees, graphs, ...) were
implemented.

In fact, when memory was more expensive, using 2-byte indices in place
of 4-byte pointers was a popular way to save space.  GCC once used this
trick.  Of course it fails if you have more than 64K records to
address.

The algorithm you are proposing is just sorting a linked list.  You are
using indices instead of pointers, but any algorithm that works for one
will work for the other.  Mergesort is often used for this purpose.
It's a natural!  It's less well known that Quicksort translates nicely
to a linked list version.  Double links are not required for either
algorithm.  In fact it's easiest to sort using only "next" links and
then fix up the "prev" links at the end if they're needed for some
other purpose.  And of course insertion sort works fine with a linked
list, although the code looks a tad different than the array version.
Write a routine that inserts a single element in the correct position
of a list that's already sorted.  Now just pop elements one-by-one off
the original list and insert them into an (initially empty) sorted one.

Finally, the other writers are absolutely correct.  You are killing a
fly with a sledgehammer.  If all you are trying to do is avoid copying,
forget the linked list approach. Just make an array of pointers or
indices and sort those while using them to refer to the record keys for
comparisons.

.