On Wed 20 Nov 2013 at 15:32:20 -0800, Dennis Ferguson wrote:
> If one were starting this from scratch [...]
Ever since I grokked the elegance of Lists in AmigaOS, I've always
wondered why other list implementations do it differently.
A list is double linked, and it has dummy first and last nodes (which
aren't part of the data and consist just of the next and prev pointers).
They are elegantly combined in the list header, which consists of 3
pointers:
mlh_Head which points to the first real node,
mlh_Tail which is always NULL
mlh_TailPred which points to the last real node.
Each node in the list starts with a ln_Next and a ln_Prev pointer.
When the list is empty,
mlh_Head points to mlh_Tail
mlh_Tail is always NULL
mlh_TailPred points to mlh_Head.
The first dummy node consists of mlh_Head and mlh_Tail, i.e. its ln_Prev
is NULL, and the last dummy node consists of mlh_Tail and mlh_TailPred,
where its ln_Next is NULL.
This initially confusing situation eliminates all special cases for
node insertion and removal (and traversal isn't made more complicated).
This is more extensively explained in
http://wiki.amigaos.net/index.php/Exec_Lists_and_Queues .
-Olaf.
--
___ Olaf 'Rhialto' Seibert -- The Doctor: No, 'eureka' is Greek for
\X/ rhialto/at/xs4all.nl -- 'this bath is too hot.'
Attachment:
pgpPfYq3NI6mm.pgp
Description: PGP signature