Why is it called jumping?

Each update can move a working pointer beyond its immediate successor, increasing the distance covered by subsequent steps.

Does it always modify the original list?

No. A working copy can preserve the original links while the algorithm changes its temporary representation.

Is it always faster than sequential traversal?

No. Available parallelism, memory behavior, overhead and input size determine practical performance.

AI Glossary / Data engineering and architecture / Advanced

Pointer jumping

Definition

Pointer jumping is a parallel algorithmic technique that repeatedly replaces a link with a link farther along the same chain, often the current successor's successor. By doubling how far information can travel in each coordinated round, it can shorten dependency chains in linked structures.

What it means

A linked list is naturally followed one node at a time. If the next address is known only after reading the current node, simply adding processors does not make a single ordinary traversal independent.

Pointer jumping changes the representation used during the computation. Nodes simultaneously learn about more distant successors. Associated values, such as distance to the end, can be combined as links are shortened.

The technique is not the same as arbitrarily skipping data. Information needed for the answer must be preserved in the accumulated values or the underlying structure. It is also distinct from a processor merely predicting an address or prefetching memory: the algorithm explicitly changes its working links.

How it works

For a simple list-ranking variant, each node stores a working successor and a distance contribution. A node with a successor begins with distance one; the final node begins with distance zero. In each round, a node with a successor adds that successor's current distance and changes its link to the successor's current successor.

All updates must use the intended prior-round values. Separate old and new arrays are an understandable way to express this synchronously. Uncoordinated in-place writes can mix different rounds and invalidate the argument.

As the links jump farther, the remaining chains shrink. The straightforward parallel list-ranking approach has logarithmic depth but can perform O(n log n) total work for n nodes. That distinction matters: fewer dependent rounds do not necessarily mean less total computation than a sequential traversal.

Endpoint handling and input assumptions must be explicit. Cycles do not have an ordinary distance to a list's end.

Three practical examples

A parallel list-ranking procedure determines each node's distance from the tail without relying solely on one sequential walk.
A rooted-forest computation repeatedly follows parent links farther upward to propagate information toward roots.
A larger parallel graph algorithm uses a pointer-jumping subroutine to simplify linked intermediate structures before later processing.

Think of it this way

Think of people in a line initially knowing only the person immediately ahead. In a coordinated exchange, each learns whom that neighbor knows, extending the reach of their information. Repeated exchanges can cover increasingly large portions of the line.

The analogy assumes orderly rounds and valid endpoints. It does not mean people can ignore whose information belongs to which round, nor does it guarantee that a physical communication network makes all exchanges equally cheap.

Worked example

Ranking a four-node list

Take A → B → C → D → end. Initial distances are A = 1, B = 1, C = 1 and D = 0.

Using the old values for the first round, A jumps to C and receives distance 2. B jumps to D and receives distance 2. C reaches the end with distance 1. D remains at the end with distance 0.

In the second round, A adds C's distance 1 to its current 2 and reaches the end with distance 3. B adds D's zero and finishes with 2. The final distances are therefore 3, 2, 1 and 0.

These are edge distances to the tail, not counts including the node itself. A different ranking convention can use different initialization, so the meaning of the output must accompany the algorithm.

Illustrative case study

A fictional graph-processing team implements pointer jumping for a chain-based preprocessing stage. Its first parallel version updates links in place while neighboring workers are still reading them. Small examples sometimes appear correct, but the execution no longer follows the intended round-by-round reasoning.

The team separates prior-round reads from next-round writes and adds checks for malformed chains and cycles. It compares resulting ranks with a simple sequential reference on varied small inputs before evaluating large runs.

The lesson is that the apparent simplicity of replacing a pointer hides an important coordination requirement. Parallel speed should be assessed only after the computed distances have a clear and consistently enforced meaning.

Common misconceptions and mistakes

Pointer jumping means discarding intermediate information. Required contributions must be accumulated or otherwise preserved.
Logarithmic depth means linear total work. The basic list-ranking variant can do O(n log n) work even with O(log n) depth.
Any linked graph can be treated like an acyclic list. Cycles and branching structures require appropriate algorithms and different correctness arguments.

Business use

Pointer jumping usually appears inside technical infrastructure rather than as a feature business users select directly. It can matter in parallel graph processing, scientific software and other workloads with linked dependencies.

For an implementation decision, examine memory access and communication as well as theoretical rounds. Many scattered reads can be expensive, especially when pointers cross memory or machine boundaries. Extra working arrays also consume capacity.

An AI coding assistant may reproduce the update formula while omitting synchronous semantics, endpoint checks or the rank convention. Review those details against a trusted small example. A faster result with inconsistent distances is not an optimization, and a theoretically shallow algorithm may still lose to a simpler method for small workloads.

Check your understanding

Why must A use C's distance from the appropriate previous round rather than an arbitrary value being updated concurrently?

Answer: The accumulated distance and successor link must describe the same covered segment. Mixing rounds can break that relationship and invalidate the computed rank.

Related terms

Parallel algorithm
Synchronization
List ranking
linked list
work and span
rooted forest
pointer chasing
data race

Learn next

Read linked lists and work - span analysis. Trace two rounds on a five-node chain using separate old and new tables, then compare the final distances with an ordinary sequential traversal.

Sources

Carnegie Mellon Scandal project, Parallel algorithms on sequences and strings: https://www.cs.cmu.edu/~scandal/nesl/alg-sequence.html. Primary algorithm description and work–depth bounds for Wyllie's list ranking.

Uzi Vishkin, Parallel Computing lecture notes: https://users.umiacs.umd.edu/~vishkin/PUBLICATIONS/classnotes.pdf. Primary teaching material on pointer jumping.

MIT Algorithm Engineering, Parallel Algorithms lecture: https://jshun.csail.mit.edu/6506-f25/lectures/lecture2.pdf. Primary teaching material. The four-node trace and team case are original illustrations.

Previous: Pointer-generator network Next: Pointwise product