(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
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 14 August 2008.
HTML page formatted Fri Mar 25 16:20:34 2011.
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.,
U.S. National Institute of
Standards and Technology. 14 August 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/pointerJumping.html
