Singly Linked List

This page will be revised in the future.

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.

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:
  • SList InsertAfter Proof
  • SList EraseAfter Proof
• Misc:
  • Preliminary SList Definition
  • 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. — Terence J. Grant 04/20/2006 01:50