GATE Overflow Test Series | Data Structures | Test 1 | Question: 10

Question

Which of the following statements is TRUE regarding a doubly linked list?

• A. It is possible to implement a doubly linked list with a single pointer at each node by storing XOR of addresses of previous and next nodes.
• B. It is possible to implement a doubly linked list with a single pointer at each node by storing XOR of addresses of current node and next node
• C. It is possible to implement a doubly linked list with a single pointer at each node by storing XOR of addresses of current node and previous node
• D. We need minimum two pointers at each node for a doubly linked list implementation

Comments

@gatecse  Please explain with an example?

---

I’m not getting the solution to reach the correct option (A).Please explain it with proper example

---

++

Answer 1

In a doubly linked list we need the address of previous as well as next nodes. By using the property of XOR operation, we can do this by storing the XOR of the addresses of the previous and next nodes. For the head and tail nodes, we'll do XOR with $0.$ For every other node, to get the next node address, we will XOR the stored value with the pointer value used to reach that node.
Correct Answer: A

Comments

@samarpita Explanation is already given about A. What is your doubt ?

---

Sir actually the good logic is provided on Wikipedia page which i missed on that time.

---

Very nice ques and very good explanation given in  this wiki
XOR linked list - Wikipedia

Answer 2

Image1: 

Image2: 

Next = 0 means LL has reached right most end. 

Image: 3

Image: 4

 

Let me know if you find something wrong. 

Answer 3

Some misunderstandings of the question in the comments of the above answer, so tried to explain it.

(D) is correct for the above question because by storing only in a single field we will not be able to recreate a doubly linked lists which can traverse in both direction given a pointer to any node. We can only view one previous node from a current node using the XOR value.

(A), (B) and (C) are correct iff each node has a separate data field, addition to the given pointer field.

Explanation-

Let’s assume,

• We have a singly linked list of three nodes with each having address = X, Y, Z.
• For convenience we will use [X], [Y], [Z] to refer to the nodes rather than the address.
• [Y] is the current node for whom i want to store both previous node address X and next node address Z.

Reason for A:

1. We will store the value of (X XOR Z) in the data part of [Y]. So, (Y→ Data) = (X XOR Z).
2. We will store the address of next node [Z] in the single pointer part of [Y]. So, (Y→ Pointer) = Z.
3. If i want to get the address of the previous node of [Y] we can do (Y → Data) XOR (Y → Pointer), which will give us ((X XOR Z) XOR X) = X.
4. If i want to get the address of the next node of [Z] we can do (Y → Pointer), which will give us Z.

 

Reason for B:

1. We will store the value of (Y XOR Z) in the data part of [Y]. So, (Y→ Data) = (Y XOR Z).
2. We will store the address of previous node [X] in the single pointer part of [Y]. So, (Y→ Pointer) = X.
3. If i want to get the address of the previous node of [X] we can do (Y → Pointer), which will give us X.
4. If i want to get the address of the next node of [Y] we can do (Y → Data) XOR Y, which will give us ((Y XOR Z) XOR Y) = Z.

Reason for C:

1. We will store the value of (Y XOR X) in the data part of [Y]. So, (Y→ Data) = (Y XOR X).
2. We will store the address of next node [Z] in the single pointer part of [Y]. So, (Y→ Pointer) = Z.
3. If i want to get the address of the previous node of [Y] we can do (Y → Data) XOR Y, which will give us ((Y XOR X) XOR Y) = X.
4. If i want to get the address of the next node of [Y] we can do (Y → Pointer), which will give us Z.

Do, remember that P XOR Q XOR P will always yield Q.