An XOR linked list is a data structure similar to a regular doubly linked list , however, only one composite address is stored in each element — the result of the XOR operation on the addresses of the previous and next list elements.
In order to navigate the list, you must have the addresses of two consecutive elements.
Performing an XOR operation on the address of the first element and the composite address stored in the second element gives the address of the element following these two elements.
Performing an XOR operation on a composite address stored in the first element and the address of the second element gives the address of the element preceding these two elements.
Content
- 1 comparisons
- 1.1 With a doubly linked list
- 2 disadvantages
- 3 Use
- 4 See also
- 5 notes
- 6 References
Comparisons
With a doubly linked list
A classic doubly linked list stores the addresses of the previous and next list items separately, which require two pointers to store:
... ABCDE ... –> next –> next –> next –> <– prev <– prev <– prev <–... ABCDE ... –> next –> next –> next –> <– prev <– prev <– prev <–
The overhead of the XOR-linked list is two times less, since it stores only one “address” - XOR pointers to the previous and next elements:
... ABCDE ... <–> A⊕C <-> B⊕D <-> C⊕E <->... ABCDE ... <–> A⊕C <-> B⊕D <-> C⊕E <->
Weaknesses
Among the shortcomings we can mention a more complex implementation, the inability to use a standard garbage collector , difficulties in debugging the program [1] .
Usage
It is used quite rarely, since there are good alternatives, such as an expanded linked list .
See also
- Exclusive OR exchange algorithm
- Data type
Notes
Links
- An example implementation in C ++. April 15, 2011
- Prokash Sinha, A Memory-Efficient Doubly Linked List // Linux Journal , Dec 01, 2004
- Implementation of Enhanced Singly Linked List Equipped with DLL Operations: An Approach towards Enormous Memory Saving / International Journal of Future Computer and Communication, Vol. 3, No. April 2, 2014