1
$\begingroup$

I would like to check the answer of this exercise:

A circular doubled linked list with N elements has pointers that cost k bytes each of space in memory. How many bytes do the pointers of this list cost in total?

Researching about circular linked lists, i can assume that each node has 2 pointers. So am i right to say that the answer is 2(n)k bytes?

Thanks.

$\endgroup$
  • $\begingroup$ It totally depends on your implementation. If you have a singly linked list as circular list then you have only n pointers. $\endgroup$ – Navjot Waraich Sep 30 '18 at 22:16
  • $\begingroup$ It is double linked circular list $\endgroup$ – joann2555 Sep 30 '18 at 22:18
  • $\begingroup$ What is question actually asking. It is hard to understand. At first place it says that all pointers take k bytes and then it asks for the same thing $\endgroup$ – Navjot Waraich Sep 30 '18 at 22:19
  • $\begingroup$ Its asking how many bytes does it cost $\endgroup$ – joann2555 Sep 30 '18 at 22:20
  • $\begingroup$ It means that a single pointer takes k bytes $\endgroup$ – joann2555 Sep 30 '18 at 22:21
1
$\begingroup$

The list takes $2*N*k$ bytes in total. A circular linked list is just a simple linked list with its last node's next pointer pointing back towards head. So, no extra pointer is required to make it circular. Hence, the total space is $2*N*k$.

$\endgroup$
  • $\begingroup$ Doesnt each node has its own previous/after pointers? $\endgroup$ – joann2555 Sep 30 '18 at 22:28
  • $\begingroup$ Each node has two pointers. So for N nodes, there are 2N pointers. Point is that we need not any extra space to make it circular. The memory required will always be same as a normal doubly linked list $\endgroup$ – Navjot Waraich Sep 30 '18 at 22:29
  • $\begingroup$ Thanks for making it clear, so my answer is right 😊 $\endgroup$ – joann2555 Sep 30 '18 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.