zz: Great hack I just learned for linked lists

[Ted Nelson <ted@xxxxxxxxxx>]

Hi folks--

(I still won't be reading email for a couple more days)--

At the reception after the Dougfest last week (the 30th
 anniversary of Engelbart's great presentation),
 a game programmer told me a great efficiency hack for 
 linked lists.  He said it's well known among game programmers
 but not otherwise.  (Some of you no doubt know it already,
 but hey, if I can light just one candle ...)

Two items point at each other mutually.  Stored with each
 is the same number: 

A series of items need to be chained for fast doubly-linked
 retrieval.  This can be stored as a list, in which each item
 is the XOR of the addresses of two consecutive items.
 Since it is assumed that you have one of the two addresses
 in hand, the other one you want is the XOR of the one
 you already have.

(This doesn't help a lot with the insertion and deletion of items,
 but that we somehow do differently.)

THIS MAY NOT HELP US, of course, since the problem is that
 each cell is potentially on numerous linked lists (ranks),
 and WHETHER it participates in a dimension is not yet
 immediately known.  This is why we currently use hash
 databases.  However, maybe we could figure some way
 to crank this up for greater efficiency ...

(Mark-Jason, I may be way behind you, I know you said
 it could be done with (I think) three columns, this whole
 chunk of info could be superfluous.)

Ciao for niaow, T

________________________________________________________
Theodor Holm Nelson, Visiting Professor of Environmental Information,
 Keio University, Shonan Fujisawa Campus, Fujisawa, Japan _____
http://www.sfc.keio.ac.jp/~ted/   ______
Permanent Address: Project Xanadu, 3020 Bridgeway #295, Sausalito CA 94965
_____  World Wide Fax +1-415-332-0136   World Wide Voicemail:
+1-415-331-4422 _____ PERMANENT E-MAIL: ted@xxxxxxxxxx
_________________________________________________________ 
Quotation of the day, 19 December 98:
"Denial is the longest river in the world."  TN94