This project contains implementations of linked data structures. The purpose
of this project is to establish a catalog of implementation techniques for these
elements. There are two structural aspects of each data type: the node structure
and the header structure. The node structure dictates how nodes are linked
together to create the data structure. The header structure dictates how the
the list aggregates nodes to control the implementation.

== Linked Lists ==
Linked lists are a classical linked data structure. There are only two possible
node structures for linked lists:

 * Singly or forward linked nodes
 * Doubly or bidirectionally linked nodes.

A quick note on naming... A singly linked list is referred to as /forward list/
whereas a doubly linked list is simply referred to as a list. We adopt this
terminology from the C++ Standard Library.

The header structure for these lists varies on the kind of list being
implemented. Discusson of these data structures are taken from EoP.

For singly linked lists, we have:

 * Basic - The header contains the first node or null.
 * Circular - The header contains the last node or null. The last node points
   to the first.
 * Paired - the header contains a pointer to the first and last node.

For doubly linked lists we have:

 * Circular - The header contains the first node or null. The previous pointer
   of the list points to the last element.
 * Dummy - The header points to an extra node that "resides" between the first
   and last node.
 * Two-Pointer - The header contains a dummy that points to the first and last
   elements of the list, but does not reside between them.

I'm not entirely sure of the benefits of the two-pointer header. It seems
roughly analgous to the paired implementation above... It might be worth mining
out the Wikipedia article on linked lists for more information and other
approaches (e.g., XOR linking).

We need to address the issue of counted lists also (size and splice tradeoffs).

== Trees ==
Trees are the other classical linked data structure. Like lists, we can divide
analysis of the design space into link structure and header structure. For the
most part, however, the header structure is relatively trivial, and we typically
consider only a pointer to the root.

The link structure is by far the most complex. We say that a node with no more
than n children is an n-ary node. We say that a node that can contain an
arbitrary number of children is a multinode. An n-ary node can be complete,
having exactly n children or "degenerate", having less than n children.

Note that the notion of partial n-ary nodes can complicate the implementation
of basic traversal algorithms.

A node with a parent pointer is bidirectionally traversable. In most cases of
n-ary tree implementations (i.e. with n > k for small k) traversal algorithms
must locate the offset of the sibling link for its parent in order to compute
the next sibling. The parent pointer can be "anchored" with a reference
indicating it's own offset.