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$
6
  • $\begingroup$ It totally depends on your implementation. If you have a singly linked list as circular list then you have only n pointers. $\endgroup$ Sep 30, 2018 at 22:16
  • $\begingroup$ It is double linked circular list $\endgroup$ Sep 30, 2018 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$ Sep 30, 2018 at 22:19
  • $\begingroup$ Its asking how many bytes does it cost $\endgroup$ Sep 30, 2018 at 22:20
  • $\begingroup$ It means that a single pointer takes k bytes $\endgroup$ Sep 30, 2018 at 22:21

1 Answer 1

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$
3
  • $\begingroup$ Doesnt each node has its own previous/after pointers? $\endgroup$ Sep 30, 2018 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$ Sep 30, 2018 at 22:29
  • $\begingroup$ Thanks for making it clear, so my answer is right 😊 $\endgroup$ Sep 30, 2018 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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