We will discuss definitions (briefly) of sparse arrays, stacks, queues, trees (especially the binary flavor), and bitvectors. We will show how these may be implemented in Mathematica and will give simple but effective examples of each in use. In many cases we will also see, by way of contrast, equivalent simple code that is ineffective on sizable problems precisely because it ignores these basic techniques; think of this as a sort of morality play.
One will observe that some examples in subsequent sections make use of common techniques. For example, one sparse array example also uses a stack, and the queue implementation uses sparse arrays. This gives further credence to the claim that these simple methods are in some sense fundamental.
References for the techniques presented herein include:
(1980) Data Structure Techniques, Standish, Thomas. Addison Wesley.
(1974) The Design and Analysis of Computer Algorithms, Aho, Alfred, Hopcroft, John, Ullmann, Jeffrey. Addison Wesley.