Pointer algorithm

In Computer Science, a pointer algorithm (sometimes called a pointer machine, or a reference machine; see the article Pointer machine for a close but non-identical concept) is a type of algorithm that manages a linked data structure. This concept is used as a model for lower-bound proofs and specific restrictions on the linked data structure and on the algorithm's access to the structure vary.

Tarjan and La Poutré used this model to prove lower bounds on the amortized complexity of a disjoint-set data structure^[1]^[2].

^ Tarjan, Robert E. (1979). "A class of algorithms which require nonlinear time to maintain disjoint sets". Journal of Computer and Systems Sciences. 18: 110–127.
^ La Poutré, Johannes A. (1990). "Lower bounds for the union-find and the split-find problem on pointer machines". Proc. 22nd Annual ACM Symposium on the Theory of Computing. ACM. pp. 34–44.

[1] Tarjan, Robert E. (1979). "A class of algorithms which require nonlinear time to maintain disjoint sets". Journal of Computer and Systems Sciences. 18: 110–127.

[2] La Poutré, Johannes A. (1990). "Lower bounds for the union-find and the split-find problem on pointer machines". Proc. 22nd Annual ACM Symposium on the Theory of Computing. ACM. pp. 34–44.

[1]

[2]