An XOR linked list is a memory-efficient variant of a doubly linked list in which each node stores a single field that contains the bitwise exclusive OR (XOR) of the memory addresses (or pointers) of the previous and next nodes. By XOR‑combining the two addresses, the list can be traversed in either direction while using only one pointer per node, thereby reducing the per‑node storage overhead compared with a traditional doubly linked list that maintains separate prev and next fields.
Principle of operation
For a node N with predecessor P and successor S, the stored link value link_N is calculated as
link_N = address(P) XOR address(S)
During traversal, if the address of the previous node prev is known, the address of the next node next can be recovered by XOR‑ing link_N with prev:
next = link_N XOR address(prev)
The same computation in reverse yields the preceding node when moving backward through the list.
Construction and traversal
Typical operations on an XOR linked list require explicit management of raw memory addresses, often using low‑level constructs such as uintptr_t (in C/C++) or Unsafe pointers (in languages that permit pointer arithmetic). Example pseudocode for forward traversal:
prev = NULL
curr = head
while curr != NULL:
next = XOR(prev, curr.link)
process(curr)
prev = curr
curr = next
Insertion and deletion similarly involve updating the XOR values of the affected nodes to reflect the new predecessor‑successor relationships.
Advantages
- Reduced memory consumption: Each node stores a single pointer-sized field rather than two, which can be significant in environments where memory is constrained.
- Potential cache benefits: Fewer fields per node may lead to tighter packing and improved cache locality.
Disadvantages and practical concerns
- Complexity: The need to manipulate raw addresses makes the code harder to read, maintain, and debug.
- Portability: Pointer arithmetic is undefined behavior in many high‑level languages (e.g., Java, Python, standard C++) and may be prohibited by language safety guarantees.
- Safety: Incorrect handling of XOR operations can easily lead to segmentation faults or memory corruption.
- Limited language support: Languages without explicit pointer manipulation (such as managed runtimes) cannot implement true XOR linked lists without unsafe extensions or native interop.
Historical notes
The concept of an XOR linked list was popularized in the early 1990s through discussions on programming forums and textbooks on data structures. It is sometimes attributed to research on space‑efficient data structures, though no single definitive original publication is universally cited.
Use cases
XOR linked lists are primarily of academic interest or employed in specialized low‑level systems where every byte of memory counts, such as embedded firmware or certain kernel‑level data structures. In most high‑level application development, the added complexity outweighs the modest memory savings, leading developers to prefer conventional doubly linked lists or other container abstractions.
References
- J. Bentley, “Programming Pearls,” Communications of the ACM, 1999 – mentions XOR linked lists as an example of pointer tricks.
- D. Knuth, The Art of Computer Programming, Volume 1, 3rd ed., 1997 – includes a brief discussion of space‑saving linked structures.
- Various open‑source implementations in C and C++ (e.g., GitHub repositories titled “xor‑linked‑list”).
