Subtraction edge

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged with XOR linked list. (Discuss)

A subtraction edge is a particular form of link address in a linked list. It has some similarity to the XOR edge in that:

• The resulting list may be traversed in either direction, i.e. it is double threaded.
• A single link field performs double duty.
• The same end-of-list treatments apply.

It differs from the XOR edge in that:

• The link field is the difference of the addresses of the left and right successors in the list (vs XOR).
• Slightly different instruction sequences are required for the two directions of traversal.
• The list as a whole is inherently relocatable.

This last is significant. If the whole list is contained in a single block of storage, say a record, it may be written to external media and read later into a different location and the list within remains valid without change.