Skip to content

Instantly share code, notes, and snippets.

@paniq

paniq/doubly_linked_list_delta_pointer.md

Last active June 8, 2024 07:39
Show Gist options
  • Save paniq/d9ddfcbbfe32e038d319d8a733782ea7 to your computer and use it in GitHub Desktop.
Save paniq/d9ddfcbbfe32e038d319d8a733782ea7 to your computer and use it in GitHub Desktop.
Download ZIP
Doubly linked list with delta pointers
Raw
doubly_linked_list_delta_pointer.md

Doubly linked list with delta pointers:

p[x] = { value, xor(p[x-1], p[x+1]) }

Then, starting at p[-1] = null, p[0] = p_first:

p[n+1] = xor(p[n][1], p[n-1])

To go backwards, exchange p_first with p_last in the above formula.

If for any current node you also remember the previous or next node, you can always extrapolate all other nodes of the list.

Since we no longer need to deal with two separately named fields, link-in/out operations are symmetrical. Hence list reversal is as simple as swapping out p_first and p_last, and changing direction of iteration can simply be done by swapping the cursor elements.

Such a list also affords the completely new use of a ping-pong list, simply by setting a delta pointer to zero, which causes the iterator to switch direction.

This technique is also described here

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment