What is an XOR Linked List? Why is it rarely used?

Difficulty: 5/10

pointer arithmetic, memory efficiency, debugging

XOR Linked List

An XOR Linked List is a specialized doubly linked list where each node stores the XOR of the addresses of its previous and next nodes instead of storing two separate references. Given one neighboring address and the stored XOR value, the other address can theoretically be reconstructed.

javascript

1
It can reduce the memory used for two link fields to one XOR field.
2
It requires pointer/address arithmetic that is unsafe or unavailable in many managed languages.
3
It complicates debugging and memory management.
4
Garbage collectors generally do not work naturally with XOR-encoded references.
5
It can be difficult to reason about, maintain, and integrate with modern runtimes.
6
The small memory saving rarely justifies the complexity in modern application software.

Scenario Questions

0-2 years experience

2-5 years experience

1You added an XOR linked list to a feature that walks user sessions and it crashes with a segmentation fault. Walk me through how you would debug the issue.

What is an XOR Linked List? Why is it rarely used?

XOR Linked List

Scenario Questions

Follow-up Questions