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. This model has been used extensively with problems related to the disjoint-set data structure. Thus, Tarjan and La Poutré used this model to prove lower bounds on the amortized complexity of a disjoint-set data structure (La Poutré also addressed the interval split-find problem).
Blum used this model to prove a lower bound on the single operation worst-case time of disjoint set data structure. Blum and Rochow proved a worst-case lower bound for the interval union-find problem.
Wikipedia contributors, "Pointer algorithm", Wikipedia, revision 1316943286, retrieved 20 November 2026, source, CC BY-SA 4.0.