XOR linked list

Key takeaways

XOR linked list belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect XOR linked list to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of XOR linked list from memory before moving on to harder problems.

Reference excerpt

An XOR linked list is a type of data structure used in computer programming. It takes advantage of the bitwise XOR operation to decrease storage requirements for doubly linked lists by storing the composition of both addresses in one field. While the composed address is not meaningful on its own, during traversal it can be combined with knowledge of the last-visited node address to deduce the address of the following node.

Description An ordinary doubly linked list stores addresses of the previous and next list items in each list node, requiring two address fields:

... A B C D E ... –> next –> next –> next –> <– prev <– prev <– prev <–

An XOR linked list compresses the same information into one address field by storing the bitwise XOR (here denoted by ⊕) of the address for previous and the address for next in one field:

... A B C D E ... ⇌ A⊕C ⇌ B⊕D ⇌ C⊕E ⇌

More formally:

link(B) = addr(A)⊕addr(C), link(C) = addr(B)⊕addr(D), ...

When traversing the list from left to right: supposing the cursor is at C, the previous item, B, may be XORed with the value in the link field (B⊕D). The address for D will then be obtained and list traversal may resume. The same pattern applies in the other direction. i.e. addr(D) = link(C) ⊕ addr(B) where

link(C) = addr(B)⊕addr(D)

so

addr(D) = addr(B)⊕addr(D) ⊕ addr(B) addr(D) = addr(B)⊕addr(B) ⊕ addr(D)

since

X⊕X = 0 => addr(D) = 0 ⊕ addr(D)

since

X⊕0 = X => addr(D) = addr(D)

The XOR operation cancels addr(B) appearing twice in the equation and all we are left with is the addr(D). To start traversing the list in either direction from some point, the address of two consecutive items is required. If the addresses of the two consecutive items are reversed, list traversal will occur in the opposite direction.

Theory of operation The key is the first operation, and the properties of XOR:

X⊕X = 0 X⊕0 = X X⊕Y = Y⊕X (X⊕Y)⊕Z = X⊕(Y⊕Z) The R2 register always contains the XOR of the address of current item C with the address of the predecessor item P: C⊕P. The Link fields in the records contain the XOR of the left and right successor addresses, say L⊕R. XOR of R2 (C⊕P) with the current link field (L⊕R) yields C⊕P⊕L⊕R.

If the predecessor was L, the P(=L) and L cancel out leaving C⊕R. If the predecessor had been R, the P(=R) and R cancel, leaving C⊕L. In each case, the result is the XOR of the current address with the next address. XOR of this with the current address in R1 leaves the next address. R2 is left with the requisite XOR pair of the (now) current address and the predecessor.

Features Two XOR operations suffice to do the traversal from one item to the next, the same instructions sufficing in both cases. Consider a list with items {…B C D…} and with R1 and R2 being registers containing, respectively, the address of the current (say C) list item and a work register containing the XOR of the current address with the previous address (say C⊕D). Cast as System/360 instructions: X R2,Link R2 <- C⊕D ⊕ B⊕D (i.e. B⊕C, "Link" being the link field in the current record, containing B⊕D) XR R1,R2 R1 <- C ⊕ B⊕C (i.e. B, : the next record)

End of list is signified by imagining a list item at address zero placed adjacent to an end point, as in {0 A B C…}. The link field at A would be 0⊕B. An additional instruction is needed in the above sequence after the two XOR operations to detect a zero result in developing the address of the current item, A list end point can be made reflective by making the link pointer be zero. A zero pointer is a mirror. (The XOR of the left and right neighbor addresses, being the same, is zero.)

Drawbacks General-purpose debugging tools cannot follow the XOR chain, making debugging more difficult; The price for the decrease in memory usage is an increase in code complexity, making maintenance more expensive; Most garbage collection schemes do not work with data structures that do not contain literal pointers; Not all languages support type conversion between pointers and integers, XOR on pointers is not defined in some contexts; While traversing the list, the address of the previously accessed node is needed to calculate the next node's address and the pointers will be unreadable if one isn't traversing the list—for example, if the pointer to a list item was contained in another data structure; XOR linked lists do not provide some of the important advantages of doubly linked lists, such as the ability to delete a node from the list knowing only its address or the ability to insert a new node before or after an existing node when knowing only the address of the existing node. Computer systems have increasingly cheap and plentiful memory, therefore storage overhead is not generally an overriding issue outside specialized embedded systems. Where it is still desirable to reduce the overhead of a linked list, unrolling provides a more practical approach (as well as other advantages, such as increasing cache performance and speeding random access).

Variations The underlying principle of the XOR linked list can be applied to any reversible binary operation. Replacing XOR by addition or subtraction gives slightly different, but largely equivalent, formulations:

Addition linked list ... A B C D E ... ⇌ A+C ⇌ B+D ⇌ C+E ⇌

This kind of list has exactly the same properties as the XOR linked list, except that a zero link field is not a "mirror". The address of the next node in the list is given by subtracting the previous node's address from the current node's link field.

Subtraction linked list ... A B C D E ... ⇌ C-A ⇌ D-B ⇌ E-C ⇌

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with XOR linked list

Start with the simplest possible case. Write down what XOR linked list claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to XOR linked list before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about XOR linked list ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of XOR linked list

In research: XOR linked list appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses XOR linked list in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: XOR linked list is common in secondary-school and first-year university syllabi. It links to neighbouring topics Binary arithmetic, Linked lists, so understanding it makes those chapters shorter.
In everyday life: Look for XOR linked list outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study XOR linked list in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what XOR linked list means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain XOR linked list out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is XOR linked list in simple terms?

An XOR linked list is a type of data structure used in computer programming. It takes advantage of the bitwise XOR operation to decrease storage requirements for doubly linked lists by storing the composition of both addresses in one field.

Why does XOR linked list matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study XOR linked list?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on XOR linked list.