Is it possible to find the number of elements in a circular doubly linked list?

Question

We have a circular doubly linked list with several elements. Every element has a link to the next element, a link to the previous element and a boolean value (true or false). Four operations are defined for this list:

1. Get the value of the current element;
2. Reverse the value of the current element;
3. Move to the next element;
4. Move to the previous element;

How to find the number of list elements with such conditions? Is it possible?

The idea was to cast all elements to the same value, except one. Counting elements amount of such a list is not a problem, but how can I find out, that all elements are traversed?

Answer 1

You can do this in O(N) time:

N=1
set current value = true
while(current value is true) {
   N = N*2
   set the next N values = false
   go back N elements to get back to the starting element
}
// Now we know that the whole list is false
set current value = true
scan forward until you get to true again, while counting