ISRO2008-76

Question

The minimum number of fields with each node of doubly linked list is

• A. 1
• B. 2
• C. 3
• D. 4

Answer 1

When question comes like this we should think as a question asking person. I suppose this was meant in an easy way, where we have one data node and two pointers and hence we get 3 fields.

With XOR linked list, we can use just one pointer instead of 2 and similarly strictly speaking we do not need a data node also. So, we can get even 1 here. But lets be simple and mark answer as 3.

Answer 2

By quoting from Wiki "An XOR linked list is a data structure used in computer programming. It takes advantage of the bitwise XOR operation to decrease storage requirements for doubly linked lists."

Read it here: https://en.wikipedia.org/wiki/XOR_linked_list

You just need to have one field for storing the address. Another field for storing the data. I think the answer should be 2. 

Though I have read about the XOR linked lists during the interview preparations, I have not implemented it.

Answer 3

i think answer will be 2. it should have 2 compulsary field . the previous node pointer and the pointer to next field. data may or may not be present.

Comments

then what its use?

---

i want to it. i may use it as i want . suppose i want to store 1,2,3,4,5,6... and i want to find the maximum number.. so instead of storing 1,2,3 in the data field i just create the nodes. and as i will traverse like this.

while(head->next!=NULL)

head=head->next;

count++;

i will get the maximum.

---

According to your answer, data can remain empty. But field creation in node is necessary. Each node has compulsory 3 field in doubly linked list although it has empty data or any data.

So, I think answer should be 3.

Answer 4

I think ,the answer is 1. A double linked list that uses only one address field is called  XOR linked list or memory efficient doubly linked list.

https://en.wikipedia.org/wiki/XOR_linked_list

Comments

then who's going to store the data?