Re: hashing

[dewar@gnat.com (Robert Dewar)]

"chris.danx" <chris.danx@ntlworld.com> wrote in message news:<1b2t8.507$na.19833@news8-gui.server.ntli.net>...
> p.s. does anyone have any uses for circular lists?  Tom 
> Swans Tp5.5 book mentions them, what are they used for?  > Just curious...

Lots and lots of good uses for circular lists. I regard
them as one of the fundamental data strucures for queues.


Consider the following. Implement a circular list where
the tail of the list points to the head (singly linked).

Now point the head pointer to the LAST item on the list,
not the FIRST. That way, since the LAST is linked to the
FIRST you have immediate access to both and it is easy
to remove the head or add to the tail, without needing
double links, or a separate pointer to the head and tail.

There are many uses, but in the operating systems I wrote
for Honeywell, all queues were represented this way (space
was very important in those systems which were for machines
that by todays standards had small memories -- the large
members of the family had 32K bytes of memory, and these
were full featured real time executives and time sharing
operating systems :-)