pointer jumping

(definition)

Definition: In a linked structure, replacing a pointer with the pointer it points to. Used for various algorithms on lists and trees.

Also known as recursive doubling, shortcutting.

Note: The name "recursive doubling" comes the fact that if all the pointers are jumped at every step, the pointers cover double the distance with each recursion.
From Algorithms and Theory of Computation Handbook, page 47-40, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 14 August 2008.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "pointer jumping", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 14 August 2008. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/pointerJumping.html