I am thinking of a particular datastructure, but don't know the name of it.
A sequence of elements may be modeled by a collection of some X, where each X consists of:
- The element, serialized as a bunch of bytes.
- [a] The hash of the previous X in the sequence, based on the bytes of both parts of that X in a predictable way or [b] some mechanism to denote no such X exists, i.e. that this is the first element.
Given a database that contains (at least) all relevant Xs, and a lookup mechanism by hash, we can take a single X and reconstruct the sequence of elements from it.
What is the general name (if it exists) of this datastructure in the literature? I.e.
- What is the general name of X?
- What is the general name of a sequence of Xs.
Note that although this looks like (and is inspired by) a blockchain or git commit object, it is more general: any list sequence could be so rewritten.
In comparison with the blockchain / git, the above does not make any statement about distributed databases, timestamps or contents of each element. It also notably differs from git at least in the sense that it is single-parent.