3.9 Doubly Linked List is memory efficient
In the usual implementation, we need to keep a next pointer pointing to the next item in the list and a prev pointer pointing to the previous item.
That is to say, the elements in a doubly linked list implementation consist of data, a pointer to the next node and a pointer to the previous node in the list as shown below.
Conventional Node Definition
1 2 3 4 5 6 7 | public class DLLNode{ private int data; private DLLNode next; private DLLNode prev; ............... } |
We now have an alternative implementation of the ADT doubly linked list, with insert, traverse, and delete operations. This implementation is based on the difference of pointers. Each node uses only one pointer to traverse the list.
It is also known as XOR Linked List
New Node Definition
1 2 3 4 5 6 | public class ListNode{ private int data; private ListNode ptrdiff; ............... } |
The pointer ptrdiff contains the difference between the pointer to the next node and the pointer to the previous node. Pointer difference is calculated using exclusive-or . operation
( ) (⊕)
ptrdiff = pointer to previous node
pointer to next node
The main point of the head node is
of NULL and the next node of head.
Similarly, the ordinal point of the end node is
of the previous node (before to the last node) and NULL.
For example, consider the following linked list.
In the example above,
- The next pointer of A is: NULL
- B’s next pointer is: A
- C’s next pointer is:
- D’s next pointer is: C
Why does it work?
To find the answer to this question, let’s look at the properties of ⊕:
- X X = 0
- X 0 = X
- X ⊕ Y = Y ⊕ X (symmetric)
- (X ⊕ Y) ⊕ Z = X ⊕ (Y ⊕ Z) (transitive – transitive)
For the above example, let’s assume that we are at node C and want to go to node B.
We know that the ptrdiff of node C is defined as B ⊕ D.
If we want to move to B, doing ⊕ on the third point of C with D will give B.
This is due to the fact that,
Similarly, if we want to go to D, then we have to apply ⊕ to the ptrdiff of C with B to get D.
From the above discussion, we can see that just by using a single pointer we can move back and forth.
Memory-efficient doubly-linked lists can be implemented with minimal impact on time efficiency.
Note : I am not implementing here because if we need to get XOR of two addresses, we need to cast the memory address to integer, which is not possible in java. It can be implemented using C/C++, if you want to learn more, you can refer here