====== Singly Linked List ======

//**This page will be revised in the future.**//

===== License =====

** The files presented below are Copyright 2005 Terence J. Grant. They are __NOT__ public domain and may only be used with the permission of the author. Do not copy, do not republish nor rebroadcast. **

Sorry if this seems restrictive, but I've had my research republished (and reattributed) without permission before; so I am very serious about this.

===== Introduction =====

Last year (2005), during summer, and part of fall, I began work on what would have been called "The Geary Street Library." Essentially this is what LibTate would have been-- a library targetted toward game development, if it were coded purely in C.

The drawbacks soon became obvious; most of my time was implementing simple data structures, and although this was a tremendous learning experience, it did nothing for the progression of the library itself.

However, this did lead into a great research discovery for me; proving code and concept correctness, and visual proof techniques using mathematical models. I won't go into more details right now, but for the time being I'll present a few proofs for some common data structures, with the proofs themselves being based on the concept of mathematical induction.

Now I'll admit, they're a little hard to follow at the time, but this is only because they were designed on a white board(much bigger than a scanned piece of paper) and then transferred to a piece of paper, which was then scanned.

So for the time being, you can peruse my proofs; in the near future I'll clean them up and repost them, but for now you're stuck with these:

  * Proofs:
    * {{:proofs:slistinsertafterproof.pdf|SList InsertAfter Proof}}
    * {{:proofs:slisteraseafterproof.pdf|SList EraseAfter Proof}}
  * Misc:
    * {{:proofs:preliminarylistdefinition.pdf|Preliminary SList Definition}}
    * {{:proofs:highlevelslistdesign.pdf|High Level SList Design}} - Essentially this is the result of the proofs above.

I don't have alot of proofs on scanned, but its easy enough to come up with them once you know how. I'll expand upon them at a later date.
 --- //[[tjgrant@tatewake.com|Terence J. Grant]] 04/20/2006 01:50//