InterviewSolution
| 1. |
In a standard Doubly Linked List, two address fields are required to contain the addresses of previous and next nodes. Can you create a doubly linked list using only one space for the address field with every node? |
|
Answer» Yes, there is a memory-saving version of the Doubly Linked List that uses only one space for the address FIELD in each node. Because the list uses the bitwise XOR operation to save space for one address, it is known as the XOR Linked List or Memory Efficient. Instead of storing actual memory addresses, each node in the XOR linked list stores the XOR of previous and NEXT node addresses. In the XOR REPRESENTATION, let's call the address variable npx (XOR of next and previous). We can traverse the XOR Linked List in both forward and reverse DIRECTIONS while traversing it. We must remember the address of the previously visited node when traversing the list in order to DETERMINE the address of the next node. Node W: Node X: Node Y: Node Z: Calculation: npx(Y) XOR add(X) |
|