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.

Improve this question
$\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$
    – Navjot Singh
    Commented Sep 30, 2018 at 22:16
  • $\begingroup$ It is double linked circular list $\endgroup$
    – heresthebuzz
    Commented 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$
    – Navjot Singh
    Commented Sep 30, 2018 at 22:19
  • $\begingroup$ Its asking how many bytes does it cost $\endgroup$
    – heresthebuzz
    Commented Sep 30, 2018 at 22:20
  • $\begingroup$ It means that a single pointer takes k bytes $\endgroup$
    – heresthebuzz
    Commented Sep 30, 2018 at 22:21

1 Answer 1

Reset to default
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$.

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