# Circular Doubly Linked List find length with single pointer

I have pointer to circular doubly linked list with random values of 0 or 1.
Example: [{prev,0,next},{prev,0,next},{prev,1,next},{prev,0,next}...]
I have a single pointer to the first item of the list. I need to find the length of the list without to create any additional pointers.
In addition, I can change the values of each node between 0 to 1 or 1 to 0.

I thought about Josephus Circle algorithm - with no success.

My main problem is that I don't even know what end of a circle/circular list is.
If you think about that, you will understand it is not an easy question.

• (I don't know if I arrive to the end of the list I don't even know what end of a circle/circular list is.) You may need to change direction, not limited to your thinking. It may help to think of Turing. – greybeard Apr 25 at 23:35
• @greybeard I changed the direction. How can Turing help here? – motis10 Apr 25 at 23:38
• Are you looking for any algorithm at all, no matter how efficient? Do you have requirements on how efficient it must be? Do you have a pointer to the start of the list (so you can keep a pointer to the start of the list and a separate pointer that you modify)? – D.W. Apr 25 at 23:55
• I have a single pointer to the start of the list. But I can't add separate pointer. The efficienct should be the best it can – motis10 Apr 26 at 0:00
• Sorry, I don't understand. Can you have one pointer that is to the start of the list and is never modified but can be read later, and a second pointer that you modify in each step of the algorithm? Can you tell us where you encountered this problem? Can you credit the original source of the problem? – D.W. Apr 26 at 0:21

I think the following algorithm would do it:

1. Start by setting the value in the first node to $$1$$.
2. Follow next pointers until you encounter a node with value $$1$$, while keeping a counter $$c$$ of how many nodes you have encountered.
3. Set the value of the node to $$0$$ and follow prev pointers for $$c$$ steps
• If the value of the node (which should be the first node) is now $$0$$, the list has $$c-1$$ elements,
• otherwise, follow next pointers for $$c$$ steps and continue with step 2.
• @D.W. Are you sure? It's looks promising as you said. – motis10 Apr 26 at 16:29
• @motis10, I was confused. Sorry. – D.W. Apr 26 at 16:31
• @AcId and complexity is O(n(n+1)) = O(n^2). Right? – motis10 Apr 26 at 18:12
• In the worst case (when every node has value $1$) you cycle back an forth across the list in every step, so I would say that the worst time complexity is $\sum_{i = 1}^n 2 i = n (n + 1) = \mathcal{O}(n^2)$. In the best case (every node has the value $0$) we only go back through the list once, so the best case complexity is $2n$. – AcId Apr 26 at 18:15

One of your comments suggests that you are interested in an ‘efficient’ solution -
assuming a non-empty list correctly doubly linked:

0. let $$toSet = 1$$ and set current item to $$0$$

1. $$toSet$$ times, follow the $$next$$ link and set to $$1$$
2. $$toSet - 1$$ times, follow the $$prev$$ link
3. up to $$toSet$$ times,
• follow the $$prev$$ link,
• if item is $$1$$, the number of $$prev$$s followed since last change of direction is the number of items,
else set to $$1$$
4. double $$toSet$$
5. $$toSet$$ times, follow the $$prev$$ link and set to $$0$$
6. $$toSet - 1$$ times, follow the $$next$$ link
7. up to $$toSet$$ times,
• follow the $$next$$ link,
• if item is $$0$$, the number of $$next$$s followed since last change of direction is the number of items,
else set to $$0$$
8. double $$toSet$$ and repeat from 1

The number of items set and potentially inspected doubles with each "half-iteration".
The number of items checked is exactly the number $$n$$ of items in the list.
The number of items set varies from $$3n-1$$ for $$n = 2^i$$ to $$2n$$ for $$n = 2^{i + 1} - 1$$.

ToDo: find
a simple pattern of length growth between ("half-")iterations that works for every list length, too, and
a list length where #sets + #follows + #compares is smaller than for doubling as above

• I do not believe your algorithm is correct. Running the algorithm on an example with a list of size $3$ gives the result $2$ in step $7)$. – AcId Apr 28 at 11:16
• @AcId: I had translated this to and from Java before posting. While 3 hasn't been one of my test cases, 1, 7, 8 and 9 were, in addition to larger ones. Just added 3 with no problem - how can we sort this out? – greybeard Apr 28 at 19:58
• (Hm. One point where I thought I might/would get overly explicit is number of $prev$s/$next$s followed: since last change of direction, not start of procedure.) – greybeard Apr 28 at 20:36
• Perhaps the Java code doesn't match what you've written here, as I also get a result 2 when running on a list of size 3. First we do lines 0-3, and the list is [1,1,x]. After line 4, toSet = 2. After line 6, the list is [1,0,0], and we're pointing at the last item in the list. Step 7 first sets the list to [0,0,0], then terminates after following the second next link, and outputs 2. – D.W. Apr 29 at 1:01
• @greybeard : So in step $3$ (resp. $7$) you have to also count the links followed in step $2$ (reps. $6$)? I don not think this is very clear from your answer. Perhaps consider editing to make this point clear. – AcId Apr 29 at 8:28